From 13c6bcd49f8151438aa3302b8764c6f8d42441e2 Mon Sep 17 00:00:00 2001 From: Samuel Tardieu Date: Tue, 18 Nov 2008 19:53:26 +0100 Subject: Fix deletion of last character in levenshtein distance Without this change, "git tags" will not suggest "git tag" (it will only suggest "git status"), and "git statusx" will not suggest anything. Signed-off-by: Samuel Tardieu Acked-by: Johannes Schindelin Signed-off-by: Junio C Hamano --- levenshtein.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/levenshtein.c b/levenshtein.c index db52f2c20..98fea723d 100644 --- a/levenshtein.c +++ b/levenshtein.c @@ -25,7 +25,7 @@ int levenshtein(const char *string1, const char *string2, row2[j + 1] > row0[j - 1] + w) row2[j + 1] = row0[j - 1] + w; /* deletion */ - if (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d) + if (row2[j + 1] > row1[j + 1] + d) row2[j + 1] = row1[j + 1] + d; /* insertion */ if (row2[j + 1] > row2[j] + a) -- cgit v1.2.1 From 850fb6ff81a151887043b7edd10681640b0e91c1 Mon Sep 17 00:00:00 2001 From: Johannes Schindelin Date: Thu, 20 Nov 2008 14:27:27 +0100 Subject: Document levenshtein.c Signed-off-by: Johannes Schindelin Signed-off-by: Junio C Hamano --- levenshtein.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) diff --git a/levenshtein.c b/levenshtein.c index 98fea723d..a32f4cdc4 100644 --- a/levenshtein.c +++ b/levenshtein.c @@ -1,6 +1,43 @@ #include "cache.h" #include "levenshtein.h" +/* + * This function implements the Damerau-Levenshtein algorithm to + * calculate a distance between strings. + * + * Basically, it says how many letters need to be swapped, substituted, + * deleted from, or added to string1, at least, to get string2. + * + * The idea is to build a distance matrix for the substrings of both + * strings. To avoid a large space complexity, only the last three rows + * are kept in memory (if swaps had the same or higher cost as one deletion + * plus one insertion, only two rows would be needed). + * + * At any stage, "i + 1" denotes the length of the current substring of + * string1 that the distance is calculated for. + * + * row2 holds the current row, row1 the previous row (i.e. for the substring + * of string1 of length "i"), and row0 the row before that. + * + * In other words, at the start of the big loop, row2[j + 1] contains the + * Damerau-Levenshtein distance between the substring of string1 of length + * "i" and the substring of string2 of length "j + 1". + * + * All the big loop does is determine the partial minimum-cost paths. + * + * It does so by calculating the costs of the path ending in characters + * i (in string1) and j (in string2), respectively, given that the last + * operation is a substition, a swap, a deletion, or an insertion. + * + * This implementation allows the costs to be weighted: + * + * - w (as in "sWap") + * - s (as in "Substitution") + * - a (for insertion, AKA "Add") + * - d (as in "Deletion") + * + * Note that this algorithm calculates a distance _iff_ d == a. + */ int levenshtein(const char *string1, const char *string2, int w, int s, int a, int d) { -- cgit v1.2.1