# [RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3) 3 messages from 2012-04-27 to 2012-05-24. Participants: Matthieu Moy, Zbigniew Jędrzejewski-Szmek. Thread: https://gitlist.dev/t/30346 ## Matthieu Moy, 2012-04-27 08:58 Subject: [RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3) Message-ID: <1335517082-29325-1-git-send-email-Matthieu.Moy@imag.fr> URL: https://gitlist.dev/e/1335517082-29325-1-git-send-email-Matthieu.Moy%40imag.fr ``` Before this patch, a character deletion has the same cost as 2 swaps, or 4 additions, so Git prefers suggesting a completely scrambled command name to removing a character. For example, "git tags" suggests "stage", but not "tag". By setting the deletion cost to 3, we keep it higher than swaps or additions, but prefer 1 deletion to 2 swaps. "git tags" now suggests "tag" in addition to staged. Signed-off-by: Matthieu Moy --- The funny thing is: A while ago, I reported that the typo "git tags" was not suggesting "git tag" as alternative "did you mean this?". A patch was posted and merged: http://thread.gmane.org/gmane.comp.version-control.git/101278 According to the discussion, I it worked for me. But I can't reproduce this "works for me" even going back to the version right after the fix above. help.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/help.c b/help.c index 14eefc9..fdaa90d 100644 --- a/help.c +++ b/help.c @@ -334,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd) } main_cmds.names[i]->len = - levenshtein(cmd, candidate, 0, 2, 1, 4) + 1; + levenshtein(cmd, candidate, 0, 2, 1, 3) + 1; } qsort(main_cmds.names, main_cmds.cnt, -- 1.7.10.363.g9094b ``` ## Zbigniew Jędrzejewski-Szmek, 2012-04-27 09:43 Subject: Re: [RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3) Message-ID: <4F9A6A4E.2070808@in.waw.pl> URL: https://gitlist.dev/e/4F9A6A4E.2070808%40in.waw.pl In-Reply-To: <1335517082-29325-1-git-send-email-Matthieu.Moy@imag.fr> ``` On 04/27/2012 10:58 AM, Matthieu Moy wrote: > Before this patch, a character deletion has the same cost as 2 swaps, or > 4 additions, so Git prefers suggesting a completely scrambled command > name to removing a character. For example, "git tags" suggests "stage", > but not "tag". > > By setting the deletion cost to 3, we keep it higher than swaps or > additions, but prefer 1 deletion to 2 swaps. "git tags" now suggests > "tag" in addition to staged. Hi, looks sensible, but I wonder if the algorithm shouldn't be tweaked even further. I understand why 'tags' and 'stage' are similar, but if I say 'tagz', git proposes (with your change), both 'stage' and 'tag'. 'tag' is one deletion away, but 'stage' requires a deletion and a replacement, so should loose to 'tag', I think. Zbyszek > Signed-off-by: Matthieu Moy > --- > The funny thing is: A while ago, I reported that the typo "git tags" > was not suggesting "git tag" as alternative "did you mean this?". A > patch was posted and merged: > > http://thread.gmane.org/gmane.comp.version-control.git/101278 > > According to the discussion, I it worked for me. But I can't reproduce > this "works for me" even going back to the version right after the fix > above. > > help.c | 2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > diff --git a/help.c b/help.c > index 14eefc9..fdaa90d 100644 > --- a/help.c > +++ b/help.c > @@ -334,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd) > } > > main_cmds.names[i]->len = > - levenshtein(cmd, candidate, 0, 2, 1, 4) + 1; > + levenshtein(cmd, candidate, 0, 2, 1, 3) + 1; > } > > qsort(main_cmds.names, main_cmds.cnt, ``` ## Matthieu Moy, 2012-05-24 20:33 Subject: Re: [RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3) Message-ID: URL: https://gitlist.dev/e/vpq62blwc83.fsf%40bauges.imag.fr In-Reply-To: <4F9A6A4E.2070808@in.waw.pl> ``` [ Sorry for the looong delay ] Zbigniew Jędrzejewski-Szmek writes: > On 04/27/2012 10:58 AM, Matthieu Moy wrote: >> Before this patch, a character deletion has the same cost as 2 swaps, or >> 4 additions, so Git prefers suggesting a completely scrambled command >> name to removing a character. For example, "git tags" suggests "stage", >> but not "tag". >> >> By setting the deletion cost to 3, we keep it higher than swaps or >> additions, but prefer 1 deletion to 2 swaps. "git tags" now suggests >> "tag" in addition to staged. > > Hi, > looks sensible, but I wonder if the algorithm shouldn't be tweaked even > further. I understand why 'tags' and 'stage' are similar, > but if I say 'tagz', git proposes (with your change), both 'stage' and > 'tag'. 'tag' is one deletion away, but 'stage' requires a deletion and a > replacement, so should loose to 'tag', I think. First, my patch is also an improvement here since it allows showing tags (previously, it showed only stage). The idea for showing stage before tag is that the cost of deletion is greater than the cost of insertion, which corresponds to the hypothesis that it's more common to miss one character when typing than typing too many. That's probably subjective, but I think it makes sense. -- Matthieu Moy http://www-verimag.imag.fr/~moy/ ```