Fri 28 Mar 2014 05:06:15 PM UTC, original submission:
Calculating the Levenshtein distance provided by the package "strings" is a pain.
It is unbelievable slow, not only because it uses the algorithm of Wagner and Fisher, but also because it does this using loops. That leads to calculation times of 10 seconds for simple strings of length 200 and wastes plenty of memory. See for example http://savannah.gnu.org/bugs/?41920 .
Therefore I implemented the algorithm of Berghel and Roach (http://www.berghel.net/publications/asm/asm.php), who improve on Ukkonen (http://www.sciencedirect.com/science/article/pii/S0019995885800462).
Great things first: Now it is possible to calculate
in less than 2 seconds.
The new version is fully compatible with the former version, meaning that
(i) it calculates a specific matrix when asked for
(ii) can apply some specific weights
That comes at the cost of
(i) a new optional input parameter
(ii) not being able to use the new algorithm all the time.
Depending on its preferences, the user now can decide to
(i) use the former algorithm
(ii) use the algorithm of Berghel and Roach, which is almost always better but may have space issues as well
(iii) use a version with m*n runtime but linear memory usage.
I tested the correctness of the new algorithms by running the provided script uncountable times. Please note, that this produces test which are almost worst case for the algorithm by Berghel and Roach.
Please note further, that there exists a version of the algorithm used here, that uses only O(dist) memory (https://code.google.com/p/googlewebtoolkit/source/browse/trunk/dev/core/src/com/google/gwt/dev/util/editdistance/ModifiedBerghelRoachEditDistance.java?r=8928). However, I do not have the time to implement that one.
I really hope this helps and will be applied.
