{"thread":{"id":"30346","subject":"[RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","startedAt":"2012-04-27T08:58:02Z","lastAt":"2012-05-24T20:33:32Z","messageCount":3,"participants":["Matthieu Moy","Zbigniew Jędrzejewski-Szmek"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"190199","messageId":"1335517082-29325-1-git-send-email-Matthieu.Moy@imag.fr","threadId":"30346","inReplyTo":null,"subject":"[RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@imag.fr","sentAt":"2012-04-27T08:58:02Z","receivedAt":"2012-04-27T08:58:02Z","isPatch":true,"sender":{"key":"git@matthieu-moy.fr","avatar":"https://avatars.githubusercontent.com/u/14709?v=4"},"body":"Before this patch, a character deletion has the same cost as 2 swaps, or\n4 additions, so Git prefers suggesting a completely scrambled command\nname to removing a character. For example, \"git tags\" suggests \"stage\",\nbut not \"tag\".\n\nBy setting the deletion cost to 3, we keep it higher than swaps or\nadditions, but prefer 1 deletion to 2 swaps. \"git tags\" now suggests\n\"tag\" in addition to staged.\n\nSigned-off-by: Matthieu Moy \n---\nThe funny thing is: A while ago, I reported that the typo \"git tags\"\nwas not suggesting \"git tag\" as alternative \"did you mean this?\". A\npatch was posted and merged:\n\n http://thread.gmane.org/gmane.comp.version-control.git/101278\n\nAccording to the discussion, I it worked for me. But I can't reproduce\nthis \"works for me\" even going back to the version right after the fix\nabove.\n\n help.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/help.c b/help.c\nindex 14eefc9..fdaa90d 100644\n--- a/help.c\n+++ b/help.c\n@@ -334,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd)\n \t\t}\n \n \t\tmain_cmds.names[i]->len =\n-\t\t\tlevenshtein(cmd, candidate, 0, 2, 1, 4) + 1;\n+\t\t\tlevenshtein(cmd, candidate, 0, 2, 1, 3) + 1;\n \t}\n \n \tqsort(main_cmds.names, main_cmds.cnt,\n-- \n1.7.10.363.g9094b\n"},{"id":"190203","messageId":"4F9A6A4E.2070808@in.waw.pl","threadId":"30346","inReplyTo":"1335517082-29325-1-git-send-email-Matthieu.Moy@imag.fr","subject":"Re: [RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","fromName":"Zbigniew Jędrzejewski-Szmek","fromEmail":"zbyszek@in.waw.pl","sentAt":"2012-04-27T09:43:42Z","receivedAt":"2012-04-27T09:43:42Z","isPatch":true,"sender":{"key":"zbyszek@in.waw.pl","avatar":"https://avatars.githubusercontent.com/u/349618?v=4"},"body":"On 04/27/2012 10:58 AM, Matthieu Moy wrote:\n> Before this patch, a character deletion has the same cost as 2 swaps, or\n> 4 additions, so Git prefers suggesting a completely scrambled command\n> name to removing a character. For example, \"git tags\" suggests \"stage\",\n> but not \"tag\".\n> \n> By setting the deletion cost to 3, we keep it higher than swaps or\n> additions, but prefer 1 deletion to 2 swaps. \"git tags\" now suggests\n> \"tag\" in addition to staged.\n\nHi,\nlooks sensible, but I wonder if the algorithm shouldn't be tweaked even\nfurther. I understand why 'tags' and 'stage' are similar,\nbut if I say 'tagz', git proposes (with your change), both 'stage' and\n'tag'. 'tag' is one deletion away, but 'stage' requires a deletion and a\nreplacement, so should loose to 'tag', I think.\n\nZbyszek\n\n> Signed-off-by: Matthieu Moy \n> ---\n> The funny thing is: A while ago, I reported that the typo \"git tags\"\n> was not suggesting \"git tag\" as alternative \"did you mean this?\". A\n> patch was posted and merged:\n> \n> http://thread.gmane.org/gmane.comp.version-control.git/101278\n> \n> According to the discussion, I it worked for me. But I can't reproduce\n> this \"works for me\" even going back to the version right after the fix\n> above.\n> \n> help.c | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n> \n> diff --git a/help.c b/help.c\n> index 14eefc9..fdaa90d 100644\n> --- a/help.c\n> +++ b/help.c\n> @@ -334,7 +334,7 @@ const char *help_unknown_cmd(const char *cmd)\n> \t\t}\n> \n> \t\tmain_cmds.names[i]->len =\n> -\t\t\tlevenshtein(cmd, candidate, 0, 2, 1, 4) + 1;\n> +\t\t\tlevenshtein(cmd, candidate, 0, 2, 1, 3) + 1;\n> \t}\n> \n> \tqsort(main_cmds.names, main_cmds.cnt,\n"},{"id":"192111","messageId":"vpq62blwc83.fsf@bauges.imag.fr","threadId":"30346","inReplyTo":"4F9A6A4E.2070808@in.waw.pl","subject":"Re: [RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2012-05-24T20:33:32Z","receivedAt":"2012-05-24T20:33:32Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"[ Sorry for the looong delay ]\n\nZbigniew Jędrzejewski-Szmek writes:\n\n> On 04/27/2012 10:58 AM, Matthieu Moy wrote:\n>> Before this patch, a character deletion has the same cost as 2 swaps, or\n>> 4 additions, so Git prefers suggesting a completely scrambled command\n>> name to removing a character. For example, \"git tags\" suggests \"stage\",\n>> but not \"tag\".\n>> \n>> By setting the deletion cost to 3, we keep it higher than swaps or\n>> additions, but prefer 1 deletion to 2 swaps. \"git tags\" now suggests\n>> \"tag\" in addition to staged.\n>\n> Hi,\n> looks sensible, but I wonder if the algorithm shouldn't be tweaked even\n> further. I understand why 'tags' and 'stage' are similar,\n> but if I say 'tagz', git proposes (with your change), both 'stage' and\n> 'tag'. 'tag' is one deletion away, but 'stage' requires a deletion and a\n> replacement, so should loose to 'tag', I think.\n\nFirst, my patch is also an improvement here since it allows showing tags\n(previously, it showed only stage). The idea for showing stage before\ntag is that the cost of deletion is greater than the cost of insertion,\nwhich corresponds to the hypothesis that it's more common to miss one\ncharacter when typing than typing too many. That's probably subjective,\nbut I think it makes sense.\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"}]}