# [PATCH] Fix deletion of last character in levenshtein distance 12 messages from 2008-11-18 to 2008-11-20. Participants: Samuel Tardieu, Matthieu Moy, Johannes Schindelin, Junio C Hamano, Jon Loeliger, Sverre Rabbelier. Thread: https://gitlist.dev/t/16381 ## Samuel Tardieu, 2008-11-18 18:53 Subject: [PATCH] Fix deletion of last character in levenshtein distance Message-ID: <20081118185326.12721.71576.stgit@arrakis.enst.fr> URL: https://gitlist.dev/e/20081118185326.12721.71576.stgit%40arrakis.enst.fr ``` 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 --- levenshtein.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/levenshtein.c b/levenshtein.c index db52f2c..98fea72 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) ``` ## Matthieu Moy, 2008-11-18 20:23 Subject: Re: [PATCH] Fix deletion of last character in levenshtein distance Message-ID: URL: https://gitlist.dev/e/vpqiqqkbx7d.fsf%40bauges.imag.fr In-Reply-To: <20081118185326.12721.71576.stgit@arrakis.enst.fr> ``` Samuel Tardieu writes: > Without this change, "git tags" will not suggest "git tag" > (it will only suggest "git status"), and "git statusx" will > not suggest anything. Tested and approved, but I didn't check the code. Thanks, -- Matthieu ``` ## Johannes Schindelin, 2008-11-19 00:53 Subject: Re: [PATCH] Fix deletion of last character in levenshtein distance Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0811190151000.30769%40pacific.mpi-cbg.de In-Reply-To: <20081118185326.12721.71576.stgit@arrakis.enst.fr> ``` Hi, On Tue, 18 Nov 2008, Samuel Tardieu wrote: > diff --git a/levenshtein.c b/levenshtein.c > index db52f2c..98fea72 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) I do not understand: does row2 have more entries than len2? In any case, you will _have_ to guard against accessing elements outside the reserved memory. You'll have to be more convincing to make me agree that this is a good change, and I am pretty certain that other people are less familiar with that particular part of Git's source code than me. Ciao, Dscho ``` ## Samuel Tardieu, 2008-11-19 08:42 Subject: Re: [PATCH] Fix deletion of last character in levenshtein distance Message-ID: <2008-11-19-09-42-45+trackit+sam@rfc1149.net> URL: https://gitlist.dev/e/2008-11-19-09-42-45%2Btrackit%2Bsam%40rfc1149.net In-Reply-To: ``` * Johannes Schindelin [2008-11-19 01:53:45 +0100] | Hi, | | On Tue, 18 Nov 2008, Samuel Tardieu wrote: | | > diff --git a/levenshtein.c b/levenshtein.c | > index db52f2c..98fea72 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) | | I do not understand: does row2 have more entries than len2? Yes it does: int *row2 = xmalloc(sizeof(int) * (len2 + 1)); | In any case, you will _have_ to guard against accessing elements | outside the reserved memory. Why would that be needed? j belongs to [0, len2[, so j+1 is always in [0, len2+1[ which is ok for both row2 and row1. ``` ## Johannes Schindelin, 2008-11-19 09:57 Subject: Re: [PATCH] Fix deletion of last character in levenshtein distance Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0811191053250.30769%40pacific.mpi-cbg.de In-Reply-To: <2008-11-19-09-42-45+trackit+sam@rfc1149.net> ``` Hi, On Wed, 19 Nov 2008, Samuel Tardieu wrote: > * Johannes Schindelin [2008-11-19 01:53:45 +0100] > > | Hi, > | > | On Tue, 18 Nov 2008, Samuel Tardieu wrote: > | > | > diff --git a/levenshtein.c b/levenshtein.c > | > index db52f2c..98fea72 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) > | > | I do not understand: does row2 have more entries than len2? > > Yes it does: int *row2 = xmalloc(sizeof(int) * (len2 + 1)); > > | In any case, you will _have_ to guard against accessing elements > | outside the reserved memory. > > Why would that be needed? j belongs to [0, len2[, so j+1 is always > in [0, len2+1[ which is ok for both row2 and row1. Okay, I understand now, _after_ having looked at the original levenshtein.c. IOW you could have made my task of reviewing your patch much easier. Anyway, here is my Acked-by: Johannes Schindelin Thanks for the bugfix, Dscho ``` ## Junio C Hamano, 2008-11-19 13:13 Subject: Re: [PATCH] Fix deletion of last character in levenshtein distance Message-ID: <7vhc63svsl.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7vhc63svsl.fsf%40gitster.siamese.dyndns.org In-Reply-To: ``` Johannes Schindelin writes: > Okay, I understand now, _after_ having looked at the original > levenshtein.c. > > IOW you could have made my task of reviewing your patch much easier. > > Anyway, here is my > > Acked-by: Johannes Schindelin > > Thanks for the bugfix, In other words, even the original author's head exploded without looking at extra context lines around the patch. It is a sure sign that the original implementation was too scantily described, and that the fix was not explained well in the proposed commit log message (i.e. in what corner cases the original was bad in what way, and how the patch fixes it). I shouldn't have to decipher the original and the fixed version with pencil and paper when re-reviewing Dscho's Ack. ``` ## Samuel Tardieu, 2008-11-20 12:00 Subject: Re: [PATCH] Document levenshtein.c Message-ID: <2008-11-20-13-00-31+trackit+sam@rfc1149.net> URL: https://gitlist.dev/e/2008-11-20-13-00-31%2Btrackit%2Bsam%40rfc1149.net In-Reply-To: ``` * Johannes Schindelin [2008-11-20 13:00:35 +0100] | How about this? I think it still lacks a note about what "deletion" and "insertion" means (is that a character deleted from string1 to obtain string2 or the reverse?). In most implementation, you use the same cost for insertion and deletion so the function is symetrical, but this implementation is more powerful. ``` ## Johannes Schindelin, 2008-11-20 12:00 Subject: [PATCH] Document levenshtein.c Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0811201255120.30769%40pacific.mpi-cbg.de In-Reply-To: <7vhc63svsl.fsf@gitster.siamese.dyndns.org> ``` Signed-off-by: Johannes Schindelin --- On Wed, 19 Nov 2008, Junio C Hamano wrote: > It is a sure sign that the original implementation was too > scantily described, and that the fix was not explained well in the > proposed commit log message (i.e. in what corner cases the original > was bad in what way, and how the patch fixes it). How about this? levenshtein.c | 31 +++++++++++++++++++++++++++++++ 1 files changed, 31 insertions(+), 0 deletions(-) diff --git a/levenshtein.c b/levenshtein.c index db52f2c..298907a 100644 --- a/levenshtein.c +++ b/levenshtein.c @@ -1,6 +1,39 @@ #include "cache.h" #include "levenshtein.h" +/* + * This function implements the Damerau-Levenshtein algorithm to + * calculate a distance between strings. + * + * 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 (likewise "j + 1" for + * string2). + * + * 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, row1[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 "Substition") + * - a (for insertion, AKA "Add") + * - d (as in "Deletion") + */ int levenshtein(const char *string1, const char *string2, int w, int s, int a, int d) { -- 1.6.0.2.763.g72663 ``` ## Johannes Schindelin, 2008-11-20 13:27 Subject: [PATCH v2] Document levenshtein.c Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0811201426100.30769%40pacific.mpi-cbg.de In-Reply-To: <2008-11-20-13-00-31+trackit+sam@rfc1149.net> ``` Signed-off-by: Johannes Schindelin --- On Thu, 20 Nov 2008, Samuel Tardieu wrote: > * Johannes Schindelin [2008-11-20 > 13:00:35 +0100] > > | How about this? > > I think it still lacks a note about what "deletion" and > "insertion" means (is that a character deleted from string1 to obtain > string2 or the reverse?). In most implementation, you use the same > cost for insertion and deletion so the function is symetrical, but > this implementation is more powerful. Second paragraph and last sentence were added. levenshtein.c | 37 +++++++++++++++++++++++++++++++++++++ 1 files changed, 37 insertions(+), 0 deletions(-) diff --git a/levenshtein.c b/levenshtein.c index db52f2c..ebef34b 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 "Substition") + * - 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) { -- 1.6.0.2.763.g72663 ``` ## Jon Loeliger, 2008-11-20 17:21 Subject: Re: [PATCH v2] Document levenshtein.c Message-ID: <1227201710.22668.2.camel@ld0161-tx32> URL: https://gitlist.dev/e/1227201710.22668.2.camel%40ld0161-tx32 In-Reply-To: ``` On Thu, 2008-11-20 at 14:27 +0100, Johannes Schindelin wrote: > Signed-off-by: Johannes Schindelin > + * This implementation allows the costs to be weighted: > + * > + * - w (as in "sWap") > + * - s (as in "Substition") > + * - a (for insertion, AKA "Add") > + * - d (as in "Deletion") > + * Were these supposed to be examples or definitions? The first looks like a definition by example. I'm not sure what "Substition" is besides a misspelling. Is it the definition "Substitution"? Or was it an example "Substitition" poorly spelled? The final two look like straight definitions. Thanks, jdl ``` ## Sverre Rabbelier, 2008-11-20 17:48 Subject: Re: [PATCH v2] Document levenshtein.c Message-ID: URL: https://gitlist.dev/e/bd6139dc0811200948u7d2cf8e9qfaada22d21f6d01c%40mail.gmail.com In-Reply-To: <1227201710.22668.2.camel@ld0161-tx32> ``` On Thu, Nov 20, 2008 at 18:21, Jon Loeliger wrote: > Were these supposed to be examples or definitions? > The first looks like a definition by example. > I'm not sure what "Substition" is besides a misspelling. > Is it the definition "Substitution"? Or was it an > example "Substitition" poorly spelled? > The final two look like straight definitions. Err, I'm pretty sure it's documenting the parameters? -- Cheers, Sverre Rabbelier ``` ## Johannes Schindelin, 2008-11-20 18:31 Subject: Re: [PATCH v2] Document levenshtein.c Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.0811201930250.30769%40pacific.mpi-cbg.de In-Reply-To: <1227201710.22668.2.camel@ld0161-tx32> ``` Hi, On Thu, 20 Nov 2008, Jon Loeliger wrote: > On Thu, 2008-11-20 at 14:27 +0100, Johannes Schindelin wrote: > > Signed-off-by: Johannes Schindelin > > > + * This implementation allows the costs to be weighted: > > + * > > + * - w (as in "sWap") > > + * - s (as in "Substition") > > + * - a (for insertion, AKA "Add") > > + * - d (as in "Deletion") > > + * > > I'm not sure what "Substition" is besides a misspelling. It is a msipeling. Thanks, Dscho ```