Hi,
On Fri, 22 Jun 2007, Johannes Sixt wrote:
> 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.
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
