Przy porównywaniu używa się algorytmów znajdujących najdłuższy współny
podciąg: Ale czy
longest common subsequence to zawsze jest to o co nam chodzi?
W skrajnych przypadkach otrzymamy przeplot typu:
wstawienie, usunięcie lub modyfikacja
wspolna linia
wspolna linia
wstawienie, usunięcie lub modyfikacja
wspolna linia
wstawienie, usunięcie lub modyfikacja
.......

a tymczasem może istnieje inny sposób, grupujący zarówno wspólne linie jak i
usunięte lub dodane. "Grupujący" czyli taka ścieżka od pocątku do końca
pliku, gdzie następowały by po sobie większe bloki wspólnych czy też
usuniętych/dodanych
Może się okazać że co prawda jak zsumujemy długość wspołnych, będzie
mniejsza niż niż w algorymtie powyżej, ale będzie moze bardziej tym o co
chodziło - typu usunięta lub wstawiona funkcja (już nie mówiąc o bardziej
zaawansowanym sprawdzaniu w rodzaju przeniesienia funkcji w inne miejsce)
Na początku należałoby zdefinować dokładnie, co mielibyśmy maksymalizować
czy były badania na ten temat? czy też może istnieją tego rodzaju algorytmy
ale sa bardzo niewydajne, złożonośc kwadratowa lub jeszcze gorsza?

do góry

On Sat, 4 May 2013 23:03:38 +0200, "Borneq"
<b...@a...hidden.pl> wrote:

>Przy porównywaniu u?ywa si? algorytmów znajduj?cych najd?u?szy wspó?ny
>podci?g: Ale czy
>longest common subsequence to zawsze jest to o co nam chodzi?
>W skrajnych przypadkach otrzymamy przeplot typu:
>wstawienie, usuni?cie lub modyfikacja
>wspolna linia
>wspolna linia
>wstawienie, usuni?cie lub modyfikacja
>wspolna linia
>wstawienie, usuni?cie lub modyfikacja
>.......
>
>a tymczasem mo?e istnieje inny sposób, grupuj?cy zarówno wspólne linie jak i
>usuni?te lub dodane. "Grupuj?cy" czyli taka ?cie?ka od poc?tku do ko?ca
>pliku, gdzie nast?powa?y by po sobie wi?ksze bloki wspólnych czy te?
>usuni?tych/dodanych
> Mo?e si? okaza? ?e co prawda jak zsumujemy d?ugo?? wspo?nych, b?dzie
>mniejsza ni? ni? w algorymtie powy?ej, ale b?dzie moze bardziej tym o co
>chodzi?o - typu usuni?ta lub wstawiona funkcja (ju? nie mówi?c o bardziej
>zaawansowanym sprawdzaniu w rodzaju przeniesienia funkcji w inne miejsce)
>Na pocz?tku nale?a?oby zdefinowa? dok?adnie, co mieliby?my maksymalizowa?
>czy by?y badania na ten temat? czy te? mo?e istniej? tego rodzaju algorytmy
>ale sa bardzo niewydajne, z?o?ono?c kwadratowa lub jeszcze gorsza?

Ale o co chodzi? O porownywanie stringow, czy co?

A.L.

do góry

Uzytkownik "A.L." <a...@a...com> napisal w wiadomosci
news:c8vao8tm7tmpla3cvfrjfgg64dgkhvjp0m@4ax.com...
> Ale o co chodzi? O porownywanie stringow, czy co?

Mam dwa stringi: "egaefa" i "eadega"
LCS da nam
e [-g] a [+d] e [f->g] a
czyli najdluszy podciag ma 4 znaki:"eaea", najmniej edycji liczac pojedyncze
wstawienia i usuniecia

Jednak jest drugi spoób [+ead]ega[-efa]
wspólny ciag ma wprawdzie tylko 3 znaki ega, ale jest w jednej grupie,
daodane i usuniete tez w jednej grupie

do góry

Uzytkownik "Borneq" <b...@a...hidden.pl> napisal w wiadomosci
news:km3vmp$u77$1@node2.news.atman.pl...
> Jednak jest drugi spoób [+ead]ega[-efa]

Nalezaloby dobrze zdefiniowac co mamy maksymalizowac, czy nieprzerwany ciag
ma byc najdluzszy? ale wtedy móglby liczyc np 10% calosci i byc jeden, a
reszta bylaby wstawiane/usuwana, czy tez minimalizacja liczby bloków.
W kazdym razie - sumaryczna wielkosc bloków wspólnych musiala by byc duza w
porównaniu z blokami rózniacymi sie.

do góry

On Sat, 4 May 2013 23:48:08 +0200, "Borneq"
<b...@a...hidden.pl> wrote:

>Uzytkownik "A.L." <a...@a...com> napisal w wiadomosci
>news:c8vao8tm7tmpla3cvfrjfgg64dgkhvjp0m@4ax.com...
>> Ale o co chodzi? O porownywanie stringow, czy co?
>
>Mam dwa stringi: "egaefa" i "eadega"
>LCS da nam
>e [-g] a [+d] e [f->g] a
>czyli najdluszy podciag ma 4 znaki:"eaea", najmniej edycji liczac pojedyncze
>wstawienia i usuniecia
>
>Jednak jest drugi spoób [+ead]ega[-efa]
>wspólny ciag ma wprawdzie tylko 3 znaki ega, ale jest w jednej grupie,
>daodane i usuniete tez w jednej grupie

No dobra, ALE JAKI JEST PROBLEM? Czy mozesz napisac pol ludzku o co ci
chodzi?

A.L.

do góry

Uzytkownik "A.L." <a...@a...com> napisal w wiadomosci
news:9r4bo81osj8bufd3g59vgc8oh3iifeb5id@4ax.com...
> No dobra, ALE JAKI JEST PROBLEM? Czy mozesz napisac pol ludzku o co ci
> chodzi?

Problemem jest to ze dla najdluzszy wspólny podciag moze byc pociety na male
czesci nawet dlugosci = 1

do góry

On 2013-05-04, Borneq <b...@a...hidden.pl> wrote:
> Uzytkownik "A.L." <a...@a...com> napisal w wiadomosci
> news:9r4bo81osj8bufd3g59vgc8oh3iifeb5id@4ax.com...
>> No dobra, ALE JAKI JEST PROBLEM? Czy mozesz napisac pol ludzku o co ci
>> chodzi?
>
> Problemem jest to ze dla najdluzszy wspólny podciag moze byc pociety na male
> czesci nawet dlugosci = 1

No i? Dlaczego to ma być problem?

--
Secunia non olet.
Stanislaw Klekot

do góry

W dniu 2013-05-05 01:14, Borneq pisze:
> Uzytkownik "A.L." <a...@a...com> napisal w wiadomosci
> news:9r4bo81osj8bufd3g59vgc8oh3iifeb5id@4ax.com...
>> No dobra, ALE JAKI JEST PROBLEM? Czy mozesz napisac pol ludzku o co ci
>> chodzi?
>
> Problemem jest to ze dla najdluzszy wspólny podciag moze byc pociety na
> male czesci nawet dlugosci = 1

Najpierw mówiłeś o porównywaniu, i wydawało mi się, że pytasz o to:
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"

Teraz mówisz o _sekwencjonowaniu_ (nie porownaniu) DNA.
Powtórzenie i ścisłe sformułowanie zagadnienie od początku
na pewno nie zaszkodzi:)

BTW. Z fragmentów długości 1 złożysz wszytko. Są bezwartościowe.

pzdr
bartekltg

do góry

On Sunday, May 5, 2013 1:14:56 AM UTC+2, Borneq wrote:
> Problemem jest to ze dla najdluzszy wspólny podciag moze byc pociety na male
> czesci nawet dlugosci = 1

Googlaj za "LCS gap penalty"

w.

do góry

On Sun, 5 May 2013 01:14:56 +0200, "Borneq"
<b...@a...hidden.pl> wrote:

>Uzytkownik "A.L." <a...@a...com> napisal w wiadomosci
>news:9r4bo81osj8bufd3g59vgc8oh3iifeb5id@4ax.com...
>> No dobra, ALE JAKI JEST PROBLEM? Czy mozesz napisac pol ludzku o co ci
>> chodzi?
>
>Problemem jest to ze dla najdluzszy wspólny podciag moze byc pociety na male
>czesci nawet dlugosci = 1

Przepraszam, ale za cholere nie rozumiem

A.L.

do góry