Investigate further optimizations of the algorithm

hiddentao / fast-levenshtein

Efficient Javascript implementation of Levenshtein algorithm with locale-specific collator support.

MIT License

592 stars 56 forks source link

Investigate further optimizations of the algorithm #1

Closed hiddentao closed 10 years ago

hiddentao commented 11 years ago

We don't need to store the current row, just the last value calculated in the current row. Implement this optimization.

wooorm commented 10 years ago

Just wanted you to know that I've implemented this enhancement in my levenshtein module – It was a bit hard to bend by brain around, but in the end it worked out great. You should implement it too!

hiddentao commented 10 years ago

@wooorm Thanks. I've added in this optimization and imported your benchmark tests (please see the README.md for results).

wooorm commented 10 years ago

Nice job, although bittersweet: now I have to make my module faster! :+1: