Re: [PATCH] add 'string-distance' to calculate Levenshtein distance

[Paul Eggert]

Nathan Moreau wrote:
> What is the difference with the code present in lib/diffseq.h?

lib/diffseq.h uses the Myers-Ukkonen algorithm that scales better for the common 
case where strings are closely related. If the two strings are length N and 
their Levenshtein distance is D (where D is much less than N), then 
lib/diffseq.h is O(N*D) whereas the proposed algorithm is O(N**2).

So yes, it'd be better if the code used lib/diffseq.h rather than rolled its own 
algorithm.