**diff options**

author | Johannes Schindelin <Johannes.Schindelin@gmx.de> | 2008-11-20 13:27:27 (GMT) |
---|---|---|

committer | Junio C Hamano <gitster@pobox.com> | 2008-11-24 03:23:34 (GMT) |

commit | 850fb6ff81a151887043b7edd10681640b0e91c1 (patch) | |

tree | aa18591bf1e3eff73b68030e00422c1a5d6b1bac /levenshtein.c | |

parent | 13c6bcd49f8151438aa3302b8764c6f8d42441e2 (diff) | |

download | git-850fb6ff81a151887043b7edd10681640b0e91c1.zip git-850fb6ff81a151887043b7edd10681640b0e91c1.tar.gz git-850fb6ff81a151887043b7edd10681640b0e91c1.tar.bz2 |

Document levenshtein.c

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Diffstat (limited to 'levenshtein.c')

-rw-r--r-- | levenshtein.c | 37 |

1 files changed, 37 insertions, 0 deletions

diff --git a/levenshtein.c b/levenshtein.c index 98fea72..a32f4cd 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) { |