W dniu 2013-05-05 22:56, Borneq pisze:
> 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ć

NIe ma nic takiego jak rozwiązanie optymalne, póki precyzyjnie
nie zdefiniujesz problemu. Ściśle nie zadasz szukanej funkcji
do optymalizacji.

Sam o tym pisałeś w pierwszym poście.

> 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?

Na pewno się da;)

pzdr
bartekltg