|
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.
[Prev in Thread] | Current Thread | [Next in Thread] |