[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andreas Politz
Subject: Re: [PATCH] add 'string-distance' to calculate Levenshtein distance
Date: Sun, 15 Apr 2018 20:17:13 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux)

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]