Re: [RFC/PATCH] Reduce cost of deletion in levenstein distance (4 -> 3)

From: Zbigniew Jędrzejewski-Szmek <zbyszek@in.waw.pl>
Date: Apr 27, 2012, 09:43 UTC
Message-ID: <4F9A6A4E.2070808@in.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:

Show 8 quoted lines

> 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

Show 28 quoted lines

> Signed-off-by: Matthieu Moy <Matthieu.Moy@imag.fr>
> ---
> 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,