Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości
news:km4545$nl$1@node1.news.atman.pl...
> http://en.wikipedia.org/wiki/Levenshtein_distance
> http://en.wikipedia.org/wiki/Damerau%E2%80%93Levensh
tein_distance
> prześledz też, jakimi algorytmami nakarmiony jest "diff"

Patrzyłem jak diff działa na dowolnych napisach, w odróżnieniu od
specjalnych przekładów, nie za bardoz daje się wybrać innej ściezki
modyfikacji, która by nie była optymalna w sensie LCS, za to miała inne
cechy.
Natomiast zauważyłem jeszcze coś:, wziąłem napisy wygeneorwane losowo:
aacaacaabbab i acaacbcacccaaab
Diff pokazało:
aacaa caabbab
a caacbcacccaa ab
Tymczasem w ciagu jest aż 5 znaków takich samych w pierwszym i drugim
napisie
aacaac a abbab
acaacbcacccaa ab
Co więcej, jest to tak samo optymalne jak to co daje diff, minimalna liczba
edycji i jest lepszym rozwiązaniem, bo spotyka się przy porównywaniu linii
tekstów, gdzie w przypadku gdy dwie linie są takie same np. linie puste,
pokazuje nie tą różnicę co trzeba.
Tutaj i tak i tak mamy rozwiązanie optymalne, cz dałoby się dostroić
algorytm w ten sposób, aby mając dwa kawałki wspólnego ciągu o długościach
przykładowo 5 i 1 albo 4 i 2 wybierze pierwszą możliwość maksymalizując
długość podciągu dłuższego kosztem krótszego?