Re: [PATCH] diffcore-rename: favour identical basenames

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Jun 22, 2007, 10:39 UTC
Message-ID: <Pine.LNX.4.64.0706221122200.4059@racer.site>
In-Reply-To: <467B777D.C47BFE0E@eudaptics.com>

Hi,

On Fri, 22 Jun 2007, Johannes Sixt wrote:

Show 12 quoted lines

> Johannes Schindelin wrote:
> >         The dangerous thing is that the score can get negative now.
> >  ...
> > +               score = (int)(src_copied * MAX_SCORE / max_size)
> > +                       - levenshtein(src->path, dst->path);
> 
> Does that also mean that you can't ever have a rename with a score of
> 100%?
> 
> (I haven't studied the algorithms and assume that levenshtein(a,b) == 0
> only if a==b, and that without the -levenshtein(...) the score can grow
> to 100%.)

There is a different code path for identical contents. So yes, you can still hit 100%, but it is now much, much harder to hit a score close to 100% [*1*].

The obviously correct way to do this is to have a subscore, and use it _strictly_ only when the score is identical.

I see two ways to do this properly:

- introduce a name_distance struct member, just below the score. This 
  means that estimate_similarity has to "return" two values instead of 
  one, and score_compare gets a bit more complex, too. Or

- change the score to unsigned long, and shift the score to higher bits, 
  adding a constant minus the Levenshtein distance. It is safe to assume 
  that the filenames are shorter than 16384 bytes (PATH_MAX is actually 
  much smaller than that), and even if two filenames of that length are 
  completely different, the distance can not be larger than twice that 
  number, i.e. 16384 deletions + 16384 insertions. Therefore, you could 
  pick 32768 as that constant.

However, I find both solutions ugly. Besides, I am not interested in the feature myself, only the implementation of Levenshtein was interesting, and I thought I just post the code here. So I did only the minimal stuff on top of the interesting one to make it sort of work.

If somebody wants to pick up the ball, be my guest, because I am out of that game.

Ciao, Dscho

Footnote:

*1* Actually, it is not _that_ bad. The score is not a value between 0 and 
    100, IOW it is _not_ what you see in the output of "diff -M". It is an 
    unsigned short between 0 and MAX_SCORE, which is defined in 
    diffcore.h as 60000.0.

    The Levenshtein distance between two filenames cannot be larger than 
    the sum of their lengths, so it should be relatively safe. That is, if 
    you don't have such insanely long paths as e.g. egit. But even there, 
    the paths share most of their directories, and therefore the distances 
    should be much, much smaller in real life.