Re: [PATCH] Fix deletion of last character in levenshtein distance

Johannes Schindelin [off-list ref] 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 [off-list ref]

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.

Signed-off-by: Johannes Schindelin <redacted>
---
	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 [off-list ref] [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.

Signed-off-by: Johannes Schindelin <redacted>
---

	On Thu, 20 Nov 2008, Samuel Tardieu wrote:

	> * Johannes Schindelin [off-list ref] [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

On Thu, 2008-11-20 at 14:27 +0100, Johannes Schindelin wrote:

Signed-off-by: Johannes Schindelin <redacted>

+ * 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

On Thu, Nov 20, 2008 at 18:21, Jon Loeliger [off-list ref] 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

Hi,

On Thu, 20 Nov 2008, Jon Loeliger wrote:

On Thu, 2008-11-20 at 14:27 +0100, Johannes Schindelin wrote:

quoted

Signed-off-by: Johannes Schindelin <redacted>

quoted

+ * 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