Uzytkownik "Wojciech Mula" <w...@g...com> napisal w wiadomosci
news:9454c6a2-86b4-47c9-88ff-0eff83966196@googlegrou
ps.com...
On Sunday, May 5, 2013 1:14:56 AM UTC+2, Borneq wrote:
> Googlaj za "LCS gap penalty"

Dzieki, przyjrze sie
http://www.calstatela.edu/faculty/nwarter/SoCalBSI/L
CS%20and%20Extensions.ppt

do góry

Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości
news:km4545$nl$1@node1.news.atman.pl...
> BTW. Z fragmentów długości 1 złożysz wszytko. Są bezwartościowe.

Chodzi o to że mając złośliwy przykład do porównywania: egaefa - eadega
najdłuższy wspólny podciąg to "eaea", ale każdy znak jest oddzielony
wstawianiem czy usuwaniem lub oboma naraz, tak że ten ciąg jest "pocięty" na
małe fragmenty

do góry

W dniu 2013-05-05 01:54, Borneq pisze:
> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości
> news:km4545$nl$1@node1.news.atman.pl...
>> BTW. Z fragmentów długości 1 złożysz wszytko. Są bezwartościowe.
>
> Chodzi o to że mając złośliwy przykład do porównywania: egaefa - eadega
> najdłuższy wspólny podciąg to "eaea", ale każdy znak jest oddzielony
> wstawianiem czy usuwaniem lub oboma naraz, tak że ten ciąg jest
> "pocięty" na małe fragmenty

A.L. ma racje, piszesz baardzo chaotycznie:/
Przejrzałeś resztę informacji z tego posta, linki
i odnośniki z nich prowadzące?

pzdr
bartekltg

do góry

Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości
news:km486o$6r8$1@node2.news.atman.pl...
> Przejrzałeś resztę informacji z tego posta, linki
> i odnośniki z nich prowadzące?

Właśnie przglądam "Levenshtein distance"

do góry

W dniu niedziela, 5 maja 2013 02:19:15 UTC+2 użytkownik Borneq napisał:
> Właśnie przglądam "Levenshtein distance"

Czy chodzi o takie porównywanie napisów (DNA), które będzie
odporne na braki liter, albo na błędy pisowni? Jeśli tak, to
szukasz miary podobieństwa. W praktyce bywa z tym problem.

Pozdrawiam.

do góry

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?

do góry

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

do góry