{"thread":{"id":"16381","subject":"[PATCH] Fix deletion of last character in levenshtein distance","startedAt":"2008-11-18T18:53:26Z","lastAt":"2008-11-20T18:31:35Z","messageCount":12,"participants":["Samuel Tardieu","Matthieu Moy","Johannes Schindelin","Junio C Hamano","Jon Loeliger","Sverre Rabbelier"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"96090","messageId":"20081118185326.12721.71576.stgit@arrakis.enst.fr","threadId":"16381","inReplyTo":null,"subject":"[PATCH] Fix deletion of last character in levenshtein distance","fromName":"Samuel Tardieu","fromEmail":"sam@rfc1149.net","sentAt":"2008-11-18T18:53:26Z","receivedAt":"2008-11-18T18:53:26Z","isPatch":true,"sender":{"key":"sam@rfc1149.net","avatar":"https://avatars.githubusercontent.com/u/44656?v=4"},"body":"Without this change, \"git tags\" will not suggest \"git tag\"\n(it will only suggest \"git status\"), and \"git statusx\" will\nnot suggest anything.\n\nSigned-off-by: Samuel Tardieu \n---\n levenshtein.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/levenshtein.c b/levenshtein.c\nindex db52f2c..98fea72 100644\n--- a/levenshtein.c\n+++ b/levenshtein.c\n@@ -25,7 +25,7 @@ int levenshtein(const char *string1, const char *string2,\n \t\t\t\t\trow2[j + 1] > row0[j - 1] + w)\n \t\t\t\trow2[j + 1] = row0[j - 1] + w;\n \t\t\t/* deletion */\n-\t\t\tif (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d)\n+\t\t\tif (row2[j + 1] > row1[j + 1] + d)\n \t\t\t\trow2[j + 1] = row1[j + 1] + d;\n \t\t\t/* insertion */\n \t\t\tif (row2[j + 1] > row2[j] + a)\n"},{"id":"96095","messageId":"vpqiqqkbx7d.fsf@bauges.imag.fr","threadId":"16381","inReplyTo":"20081118185326.12721.71576.stgit@arrakis.enst.fr","subject":"Re: [PATCH] Fix deletion of last character in levenshtein distance","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@imag.fr","sentAt":"2008-11-18T20:23:02Z","receivedAt":"2008-11-18T20:23:02Z","isPatch":true,"sender":{"key":"git@matthieu-moy.fr","avatar":"https://avatars.githubusercontent.com/u/14709?v=4"},"body":"Samuel Tardieu writes:\n\n> Without this change, \"git tags\" will not suggest \"git tag\"\n> (it will only suggest \"git status\"), and \"git statusx\" will\n> not suggest anything.\n\nTested and approved, but I didn't check the code.\n\nThanks,\n\n-- \nMatthieu\n"},{"id":"96107","messageId":"alpine.DEB.1.00.0811190151000.30769@pacific.mpi-cbg.de","threadId":"16381","inReplyTo":"20081118185326.12721.71576.stgit@arrakis.enst.fr","subject":"Re: [PATCH] Fix deletion of last character in levenshtein distance","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-19T00:53:45Z","receivedAt":"2008-11-19T00:53:45Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 18 Nov 2008, Samuel Tardieu wrote:\n\n> diff --git a/levenshtein.c b/levenshtein.c\n> index db52f2c..98fea72 100644\n> --- a/levenshtein.c\n> +++ b/levenshtein.c\n> @@ -25,7 +25,7 @@ int levenshtein(const char *string1, const char *string2,\n> \t\t\t\t\trow2[j + 1] > row0[j - 1] + w)\n> \t\t\t\trow2[j + 1] = row0[j - 1] + w;\n> \t\t\t/* deletion */\n> -\t\t\tif (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d)\n> +\t\t\tif (row2[j + 1] > row1[j + 1] + d)\n\nI do not understand: does row2 have more entries than len2? In any case, \nyou will _have_ to guard against accessing elements outside the reserved \nmemory.\n\nYou'll have to be more convincing to make me agree that this is a good \nchange, and I am pretty certain that other people are less familiar with \nthat particular part of Git's source code than me.\n\nCiao,\nDscho\n"},{"id":"96129","messageId":"2008-11-19-09-42-45+trackit+sam@rfc1149.net","threadId":"16381","inReplyTo":"alpine.DEB.1.00.0811190151000.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH] Fix deletion of last character in levenshtein distance","fromName":"Samuel Tardieu","fromEmail":"sam@rfc1149.net","sentAt":"2008-11-19T08:42:45Z","receivedAt":"2008-11-19T08:42:45Z","isPatch":true,"sender":{"key":"sam@rfc1149.net","avatar":"https://avatars.githubusercontent.com/u/44656?v=4"},"body":"* Johannes Schindelin [2008-11-19 01:53:45 +0100]\n\n| Hi,\n| \n| On Tue, 18 Nov 2008, Samuel Tardieu wrote:\n| \n| > diff --git a/levenshtein.c b/levenshtein.c\n| > index db52f2c..98fea72 100644\n| > --- a/levenshtein.c\n| > +++ b/levenshtein.c\n| > @@ -25,7 +25,7 @@ int levenshtein(const char *string1, const char *string2,\n| > \t\t\t\t\trow2[j + 1] > row0[j - 1] + w)\n| > \t\t\t\trow2[j + 1] = row0[j - 1] + w;\n| > \t\t\t/* deletion */\n| > -\t\t\tif (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d)\n| > +\t\t\tif (row2[j + 1] > row1[j + 1] + d)\n| \n| I do not understand: does row2 have more entries than len2?\n\nYes it does: int *row2 = xmalloc(sizeof(int) * (len2 + 1));\n\n| In any case, you will _have_ to guard against accessing elements\n| outside the reserved memory.\n\nWhy would that be needed? j belongs to [0, len2[, so j+1 is always\nin [0, len2+1[ which is ok for both row2 and row1.\n"},{"id":"96132","messageId":"alpine.DEB.1.00.0811191053250.30769@pacific.mpi-cbg.de","threadId":"16381","inReplyTo":"2008-11-19-09-42-45+trackit+sam@rfc1149.net","subject":"Re: [PATCH] Fix deletion of last character in levenshtein distance","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-19T09:57:26Z","receivedAt":"2008-11-19T09:57:26Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 19 Nov 2008, Samuel Tardieu wrote:\n\n> * Johannes Schindelin [2008-11-19 01:53:45 +0100]\n> \n> | Hi,\n> | \n> | On Tue, 18 Nov 2008, Samuel Tardieu wrote:\n> | \n> | > diff --git a/levenshtein.c b/levenshtein.c\n> | > index db52f2c..98fea72 100644\n> | > --- a/levenshtein.c\n> | > +++ b/levenshtein.c\n> | > @@ -25,7 +25,7 @@ int levenshtein(const char *string1, const char *string2,\n> | > \t\t\t\t\trow2[j + 1] > row0[j - 1] + w)\n> | > \t\t\t\trow2[j + 1] = row0[j - 1] + w;\n> | > \t\t\t/* deletion */\n> | > -\t\t\tif (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d)\n> | > +\t\t\tif (row2[j + 1] > row1[j + 1] + d)\n> | \n> | I do not understand: does row2 have more entries than len2?\n> \n> Yes it does: int *row2 = xmalloc(sizeof(int) * (len2 + 1));\n> \n> | In any case, you will _have_ to guard against accessing elements\n> | outside the reserved memory.\n> \n> Why would that be needed? j belongs to [0, len2[, so j+1 is always\n> in [0, len2+1[ which is ok for both row2 and row1.\n\nOkay, I understand now, _after_ having looked at the original \nlevenshtein.c.\n\nIOW you could have made my task of reviewing your patch much easier.\n\nAnyway, here is my\n\n\tAcked-by: Johannes Schindelin \n\nThanks for the bugfix,\nDscho\n"},{"id":"96151","messageId":"7vhc63svsl.fsf@gitster.siamese.dyndns.org","threadId":"16381","inReplyTo":"alpine.DEB.1.00.0811191053250.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH] Fix deletion of last character in levenshtein distance","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-11-19T13:13:46Z","receivedAt":"2008-11-19T13:13:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> Okay, I understand now, _after_ having looked at the original \n> levenshtein.c.\n>\n> IOW you could have made my task of reviewing your patch much easier.\n>\n> Anyway, here is my\n>\n> \tAcked-by: Johannes Schindelin \n>\n> Thanks for the bugfix,\n\nIn other words, even the original author's head exploded without looking\nat extra context lines around the patch.\n\nIt is a sure sign that the original implementation was too scantily\ndescribed, and that the fix was not explained well in the proposed commit\nlog message (i.e. in what corner cases the original was bad in what way,\nand how the patch fixes it).\n\nI shouldn't have to decipher the original and the fixed version with\npencil and paper when re-reviewing Dscho's Ack.\n"},{"id":"96222","messageId":"2008-11-20-13-00-31+trackit+sam@rfc1149.net","threadId":"16381","inReplyTo":"alpine.DEB.1.00.0811201255120.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH] Document levenshtein.c","fromName":"Samuel Tardieu","fromEmail":"sam@rfc1149.net","sentAt":"2008-11-20T12:00:31Z","receivedAt":"2008-11-20T12:00:31Z","isPatch":true,"sender":{"key":"sam@rfc1149.net","avatar":"https://avatars.githubusercontent.com/u/44656?v=4"},"body":"* Johannes Schindelin [2008-11-20 13:00:35 +0100]\n\n| \tHow about this?\n\nI think it still lacks a note about what \"deletion\" and \"insertion\" means\n(is that a character deleted from string1 to obtain string2 or the reverse?).\nIn most implementation, you use the same cost for insertion and deletion\nso the function is symetrical, but this implementation is more powerful.\n"},{"id":"96221","messageId":"alpine.DEB.1.00.0811201255120.30769@pacific.mpi-cbg.de","threadId":"16381","inReplyTo":"7vhc63svsl.fsf@gitster.siamese.dyndns.org","subject":"[PATCH] Document levenshtein.c","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-20T12:00:35Z","receivedAt":"2008-11-20T12:00:35Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nSigned-off-by: Johannes Schindelin \n---\n\tOn Wed, 19 Nov 2008, Junio C Hamano wrote:\n\n\t> It is a sure sign that the original implementation was too \n\t> scantily described, and that the fix was not explained well in the \n\t> proposed commit log message (i.e. in what corner cases the original\n\t> was bad in what way, and how the patch fixes it).\n\n\tHow about this?\n\n levenshtein.c | 31 +++++++++++++++++++++++++++++++\n 1 files changed, 31 insertions(+), 0 deletions(-)\n\ndiff --git a/levenshtein.c b/levenshtein.c\nindex db52f2c..298907a 100644\n--- a/levenshtein.c\n+++ b/levenshtein.c\n@@ -1,6 +1,39 @@\n #include \"cache.h\"\n #include \"levenshtein.h\"\n \n+/*\n+ * This function implements the Damerau-Levenshtein algorithm to \n+ * calculate a distance between strings.\n+ *\n+ * The idea is to build a distance matrix for the substrings of both\n+ * strings. To avoid a large space complexity, only the last three rows\n+ * are kept in memory (if swaps had the same or higher cost as one deletion\n+ * plus one insertion, only two rows would be needed).\n+ *\n+ * At any stage, \"i + 1\" denotes the length of the current substring of\n+ * string1 that the distance is calculated for (likewise \"j + 1\" for \n+ * string2).\n+ *\n+ * row2 holds the current row, row1 the previous row (i.e. for the substring\n+ * of string1 of length \"i\"), and row0 the row before that.\n+ *\n+ * In other words, at the start of the big loop, row1[j + 1] contains the\n+ * Damerau-Levenshtein distance between the substring of string1 of length\n+ * \"i\" and the substring of string2 of length \"j + 1\".\n+ *\n+ * All the big loop does is determine the partial minimum-cost paths.\n+ *\n+ * It does so by calculating the costs of the path ending in characters\n+ * i (in string1) and j (in string2), respectively, given that the last\n+ * operation is a substition, a swap, a deletion, or an insertion.\n+ *\n+ * This implementation allows the costs to be weighted:\n+ *\n+ * - w (as in \"sWap\")\n+ * - s (as in \"Substition\")\n+ * - a (for insertion, AKA \"Add\")\n+ * - d (as in \"Deletion\")\n+ */\n int levenshtein(const char *string1, const char *string2,\n \t\tint w, int s, int a, int d)\n {\n-- \n1.6.0.2.763.g72663\n"},{"id":"96237","messageId":"alpine.DEB.1.00.0811201426100.30769@pacific.mpi-cbg.de","threadId":"16381","inReplyTo":"2008-11-20-13-00-31+trackit+sam@rfc1149.net","subject":"[PATCH v2] Document levenshtein.c","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-20T13:27:27Z","receivedAt":"2008-11-20T13:27:27Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nSigned-off-by: Johannes Schindelin \n---\n\n\tOn Thu, 20 Nov 2008, Samuel Tardieu wrote:\n\n\t> * Johannes Schindelin [2008-11-20 \n\t> 13:00:35 +0100]\n\t> \n\t> | \tHow about this?\n\t> \n\t> I think it still lacks a note about what \"deletion\" and \n\t> \"insertion\" means (is that a character deleted from string1 to obtain \n\t> string2 or the reverse?). In most implementation, you use the same\n\t> cost for insertion and deletion so the function is symetrical, but\n\t> this implementation is more powerful.\n\n\tSecond paragraph and last sentence were added.\n\n levenshtein.c | 37 +++++++++++++++++++++++++++++++++++++\n 1 files changed, 37 insertions(+), 0 deletions(-)\n\ndiff --git a/levenshtein.c b/levenshtein.c\nindex db52f2c..ebef34b 100644\n--- a/levenshtein.c\n+++ b/levenshtein.c\n@@ -1,6 +1,43 @@\n #include \"cache.h\"\n #include \"levenshtein.h\"\n \n+/*\n+ * This function implements the Damerau-Levenshtein algorithm to\n+ * calculate a distance between strings.\n+ *\n+ * Basically, it says how many letters need to be swapped, substituted,\n+ * deleted from, or added to string1, at least, to get string2.\n+ *\n+ * The idea is to build a distance matrix for the substrings of both\n+ * strings. To avoid a large space complexity, only the last three rows\n+ * are kept in memory (if swaps had the same or higher cost as one deletion\n+ * plus one insertion, only two rows would be needed).\n+ *\n+ * At any stage, \"i + 1\" denotes the length of the current substring of\n+ * string1 that the distance is calculated for.\n+ *\n+ * row2 holds the current row, row1 the previous row (i.e. for the substring\n+ * of string1 of length \"i\"), and row0 the row before that.\n+ *\n+ * In other words, at the start of the big loop, row2[j + 1] contains the\n+ * Damerau-Levenshtein distance between the substring of string1 of length\n+ * \"i\" and the substring of string2 of length \"j + 1\".\n+ *\n+ * All the big loop does is determine the partial minimum-cost paths.\n+ *\n+ * It does so by calculating the costs of the path ending in characters\n+ * i (in string1) and j (in string2), respectively, given that the last\n+ * operation is a substition, a swap, a deletion, or an insertion.\n+ *\n+ * This implementation allows the costs to be weighted:\n+ *\n+ * - w (as in \"sWap\")\n+ * - s (as in \"Substition\")\n+ * - a (for insertion, AKA \"Add\")\n+ * - d (as in \"Deletion\")\n+ *\n+ * Note that this algorithm calculates a distance _iff_ d == a.\n+ */\n int levenshtein(const char *string1, const char *string2,\n \t\tint w, int s, int a, int d)\n {\n-- \n1.6.0.2.763.g72663\n"},{"id":"96273","messageId":"1227201710.22668.2.camel@ld0161-tx32","threadId":"16381","inReplyTo":"alpine.DEB.1.00.0811201426100.30769@pacific.mpi-cbg.de","subject":"Re: [PATCH v2] Document levenshtein.c","fromName":"Jon Loeliger","fromEmail":"jdl@freescale.com","sentAt":"2008-11-20T17:21:50Z","receivedAt":"2008-11-20T17:21:50Z","isPatch":true,"sender":{"key":"jdl@jdl.com","avatar":"https://gravatar.com/avatar/75ce9a10b151acd2c28ec4ab2136dba7b2ff1634530bd04b155981a749d08a64?d=mp&s=160"},"body":"On Thu, 2008-11-20 at 14:27 +0100, Johannes Schindelin wrote:\n> Signed-off-by: Johannes Schindelin \n\n> + * This implementation allows the costs to be weighted:\n> + *\n> + * - w (as in \"sWap\")\n> + * - s (as in \"Substition\")\n> + * - a (for insertion, AKA \"Add\")\n> + * - d (as in \"Deletion\")\n> + *\n\n\nWere these supposed to be examples or definitions?\nThe first looks like a definition by example.\nI'm not sure what \"Substition\" is besides a misspelling.\nIs it the definition \"Substitution\"? Or was it an\nexample \"Substitition\" poorly spelled?\nThe final two look like straight definitions.\n\nThanks,\njdl\n"},{"id":"96275","messageId":"bd6139dc0811200948u7d2cf8e9qfaada22d21f6d01c@mail.gmail.com","threadId":"16381","inReplyTo":"1227201710.22668.2.camel@ld0161-tx32","subject":"Re: [PATCH v2] Document levenshtein.c","fromName":"Sverre Rabbelier","fromEmail":"alturin@gmail.com","sentAt":"2008-11-20T17:48:55Z","receivedAt":"2008-11-20T17:48:55Z","isPatch":true,"sender":{"key":"alturin@gmail.com","avatar":null},"body":"On Thu, Nov 20, 2008 at 18:21, Jon Loeliger wrote:\n> Were these supposed to be examples or definitions?\n> The first looks like a definition by example.\n> I'm not sure what \"Substition\" is besides a misspelling.\n> Is it the definition \"Substitution\"? Or was it an\n> example \"Substitition\" poorly spelled?\n> The final two look like straight definitions.\n\nErr, I'm pretty sure it's documenting the parameters?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"96277","messageId":"alpine.DEB.1.00.0811201930250.30769@pacific.mpi-cbg.de","threadId":"16381","inReplyTo":"1227201710.22668.2.camel@ld0161-tx32","subject":"Re: [PATCH v2] Document levenshtein.c","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-11-20T18:31:35Z","receivedAt":"2008-11-20T18:31:35Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 20 Nov 2008, Jon Loeliger wrote:\n\n> On Thu, 2008-11-20 at 14:27 +0100, Johannes Schindelin wrote:\n> > Signed-off-by: Johannes Schindelin \n> \n> > + * This implementation allows the costs to be weighted:\n> > + *\n> > + * - w (as in \"sWap\")\n> > + * - s (as in \"Substition\")\n> > + * - a (for insertion, AKA \"Add\")\n> > + * - d (as in \"Deletion\")\n> > + *\n> \n> I'm not sure what \"Substition\" is besides a misspelling.\n\nIt is a msipeling.\n\nThanks,\nDscho\n"}]}