emacs-devel
[Top][All Lists]
Advanced

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

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


From: Paul Eggert
Subject: Re: [PATCH] add 'string-distance' to calculate Levenshtein distance
Date: Sun, 15 Apr 2018 11:53:05 -0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0

On 04/15/2018 12:15 AM, Chen Bin wrote:
As 'org-babel-edit-distance' documented, it will "Return the edit
(levenshtein) distance between strings S1 S2". So the problem here is to
calculate*Levenshtein distance*.

First, I doubt whether the callers care whether the code computes Levenshtein distance, LCS distance, or some other reasonable string-distance measure. Second, the Myers-Ukkonen algorithm does compute Levenshtein distance; see, for example:

Papamichail D, Papamichail G. Improved algorithms for approximate string matching. BMC Bioinformatics. 2009; 10(Suppl 1): S10. https://dx.doi.org/10.1186/1471-2105-10-S1-S10 https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2648743/

I don't offhand know whether diffseq.h uses the original Myers-Ukkonen algorithm or one of Myers's variations with a different distance measure, but if it's the latter and if users really care then we should be able to change the algorithm to match the requirements.




reply via email to

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