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

[Andreas Politz]

Paul Eggert <address@hidden> writes:

> 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).

The Ukkonen algorithm also allows for D to be an input parameter in form
of a maximal distance it should search for.  This makes this observation
even more important, since most callers, I presume, are only interested
in string-pairs with distances below some threshold.

Incidentally the (only) application of the mentioned Org function
(org-babel-edit-distance) uses D=2 (in Emacs 25.3.1).

Andreas