[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).
Andreas
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, (continued)
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/19
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/19
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/20
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, chen bin, 2018/04/20
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Eli Zaretskii, 2018/04/21
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Juri Linkov, 2018/04/21
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Thien-Thi Nguyen, 2018/04/20
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Paul Eggert, 2018/04/15
- Re: [PATCH] add 'string-distance' to calculate Levenshtein distance, Nathan Moreau, 2018/04/14