{"thread":{"id":"30638","subject":"[PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","startedAt":"2012-05-27T16:02:58Z","lastAt":"2012-05-29T18:58:37Z","messageCount":3,"participants":["Matthieu Moy","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"192294","messageId":"1338134578-29011-1-git-send-email-Matthieu.Moy@imag.fr","threadId":"30638","inReplyTo":null,"subject":"[PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@imag.fr","sentAt":"2012-05-27T16:02:58Z","receivedAt":"2012-05-27T16:02:58Z","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 RFC sent earlier [1] didn't receive negative comments, so I think this\nis a good change.\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/196457\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.g7fcd3d.dirty\n"},{"id":"192422","messageId":"7v4nqy6e0k.fsf@alter.siamese.dyndns.org","threadId":"30638","inReplyTo":"1338134578-29011-1-git-send-email-Matthieu.Moy@imag.fr","subject":"Re: [PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-29T18:25:15Z","receivedAt":"2012-05-29T18:25:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matthieu Moy writes:\n\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> Signed-off-by: Matthieu Moy \n> ---\n> The RFC sent earlier [1] didn't receive negative comments, so I think this\n> is a good change.\n>\n> http://thread.gmane.org/gmane.comp.version-control.git/196457\n\nLack of objections is never a good reason to assume it is a good\nchange. In this particular case, I think the reason why you saw\nno comments, either positive or negative, was because nobody came up\nwith a more \"scientific\" way to judge the weighting. Choosing\nbetween \"tag\" and \"stage\" given \"tags\" is just one datapoint, but\ndoes not convince anybody there are not surprising combinations\nwhere this change affects negatively.\n\nI wonder if we can mechanically find a set of parameters that\noptimally separates the built-in commands by computing N^2 distances\n(e.g. compute \"tag\" and all other command names and record\nminimum. Do so for all other commands. Now fudge the parameters and\nrepeat to see if it results in better minimum separation. Something\nlike that).\n\nHaving said all that, until somebody comes up with a better method\nof judging, I'd say that the best thing we could do is to apply this\npatch and see if anybody finds a \"surprising\" case where this leads\nto a regression.\n\nThanks.\n"},{"id":"192428","messageId":"vpqehq224rm.fsf@bauges.imag.fr","threadId":"30638","inReplyTo":"7v4nqy6e0k.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2012-05-29T18:58:37Z","receivedAt":"2012-05-29T18:58:37Z","isPatch":true,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Junio C Hamano writes:\n\n> Lack of objections is never a good reason to assume it is a good\n> change.\n\nThe other reason I forgot to mention is \"I've lived with this patch and\nmy fat fingers for a few weeks, and didn't find weird cases\". But my\nfingers are not _that_ fat, and not necessarily representative ;-).\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"}]}