From: Paul Eggert <eggert@cs.ucla.edu>
To: Chen Bin <chenbin.sh@gmail.com>, Eli Zaretskii <eliz@gnu.org>
Cc: emacs-devel@gnu.org
Subject: Re: [PATCH] add 'string-distance' to calculate Levenshtein distance
Date: Sun, 15 Apr 2018 11:53:05 -0700 [thread overview]
Message-ID: <dccb0ccd-88fa-c8f2-ace0-1a36ce8604c2@cs.ucla.edu> (raw)
In-Reply-To: <87o9il0wka.fsf@gmail.com>
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.
next prev parent reply other threads:[~2018-04-15 18:53 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-04-14 2:35 [PATCH] add 'string-distance' to calculate Levenshtein distance Chen Bin
2018-04-14 7:05 ` Eli Zaretskii
[not found] ` <87lgdq831h.fsf@gmail.com>
2018-04-14 13:24 ` Eli Zaretskii
2018-04-14 16:40 ` Chen Bin
2018-04-14 17:08 ` Eli Zaretskii
2018-04-15 7:15 ` Chen Bin
2018-04-15 14:47 ` Eli Zaretskii
[not found] ` <CAAE-R+-RDWvyrv+uqHszzh6VMH6An3disOw=PyPWaTnUTHDOCw@mail.gmail.com>
[not found] ` <83k1t72b2o.fsf@gnu.org>
2018-04-17 2:43 ` chen bin
2018-04-17 15:44 ` Eli Zaretskii
2018-04-18 7:11 ` chen bin
[not found] ` <CAAE-R+8s++_LRcQCLX60Z=TQeQHdtbM5X1k525bfNnnPSLDvRw@mail.gmail.com>
[not found] ` <83bmei36dw.fsf@gnu.org>
2018-04-17 12:31 ` chen bin
2018-04-19 8:05 ` Eli Zaretskii
2018-04-19 14:55 ` chen bin
2018-04-20 4:37 ` chen bin
2018-04-20 6:01 ` Thien-Thi Nguyen
2018-04-20 10:47 ` chen bin
2018-04-21 7:22 ` Eli Zaretskii
2018-04-21 20:47 ` Juri Linkov
2018-04-28 7:36 ` Eli Zaretskii
2018-05-06 9:53 ` chen bin
2018-04-15 18:53 ` Paul Eggert [this message]
2018-04-14 17:18 ` Nathan Moreau
2018-04-14 17:36 ` Paul Eggert
2018-04-15 18:17 ` Andreas Politz
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=dccb0ccd-88fa-c8f2-ace0-1a36ce8604c2@cs.ucla.edu \
--to=eggert@cs.ucla.edu \
--cc=chenbin.sh@gmail.com \
--cc=eliz@gnu.org \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).