Algorytm wyszukiwania różnic w stringach / ciągach znaków

[b0bi]

Witam

Chciałbym się zwrócić do Was o pomoc w opracowaniu algorytmu badania stringów, w tym przypadku byłyby to ciągi liczb w postaci hex.
I tu pojawia się problem, bo nie chodzi mi o znajdowaniu różnic 1:1 jak to robią programy do porównywania plików, które sprawdzałem (w tym HEX) czyli sprawdzanie komórka po komórce, czy występuje ta sama wartość w tych samych miejscach.
Tu chodzi o dynamiczne wyszukiwanie różnic.

Idee działania podsunął mi program WinMerge, lecz jego wadą jest to, że operuje tylko na ciągach tekstowych; co prawda wyświetla kod binarny lecz wszelkie edycje biorą w łeb, gdyż program ten zapisuje tylko ciągi tekstowe pomijając pozostały kod.
Prosiłbym o wszelkie możliwe podpowiedzi, jak podejść do problemu, jaką metodę porównawczą stworzyć, jakie funkcje mogłyby być pomocne?
W załączonym pliku przedstawiłem ogólnie o co by chodziło, co chcę osiągnąć. Problem wczytania danych i zapisu na razie pomińmy, bo w tym momencie ważniejszy jest sam algorytm porównujący.
Jeśli kogoś "przerażają" liczby... niech wyobrazi sobie, że każda liczba to słowo i chodzi o porównanie dwóch tekstów i wykrycie różnicy na zasadzie:
1 zdanie: Ala ma brązowego kota i go nie kocha.
2 zdanie: Ala ma miłego kota o imieniu Filemon i go bardzo kocha.

Oczekiwany efekt:

Kod: Zaznacz cały

Ala ma            Ala ma
brązowego
                  miłego
kota              kota
                  o imieniu Filemon
i go              i go
nie
                  bardzo
kocha.            kocha.

Za wszelkie podpowiedzi będę bardzo wdzięczny.

[Jan_J]

Zadanie nie jest banalne. Dobre algorytmy wyszukiwania wspólnych fragmentów, a także optymalnego rozmieszczenia fragmentów rozpoznanych jako wspólne, wykorzystują miary (nie)podobieństwa zwane odległościami redakcyjnymi oraz technikę programowania zwaną programowaniem dynamicznym. Można o nich poczytać w podręcznikach algorytmiki (nie mylić z podstawami programowania).

Dlatego najpierw poszukałbym gotowego narzędzia dającego się wykorzystać. Radzę sprawdzić: edytor notepad++ wraz z wtyczką compare (http://notepad-plus-plus.org/); edytor gvim (http://www.vim.org); porównywarkę meld (https://live.gnome.org/Meld). Meld jest zrobiony dla GNOME, piszą że instalator dla Windows jest taki sobie, ale nie wiem co to znaczy w praktyce.

W drugim rzucie sprawdziłbym programy narzędziowe nie posiadające interfejsu użytkowego, działające na strumieniach: diff (standard Uniksa; port dla Windows w projekcie Cygwin) oraz Windowsowy fc (jest w standardzie systemu Windows). Oskryptowanie diff-a będzie prostsze niż napisanie komparatora od zera.

Mam nadzieję, że coś z tego da się wybrać.

[b0bi]

Dziękuję Janie za podpowiedzi, gdzie szukać. Zdaję sobie sprawę, że to nie jest łatwe zadanie...
Ostatnio stanąłem przed problemem analizowania kodów hex-owych zaprogramowanych PICów i programy typu hex compare w ogóle nie dają rady.
Szukałem po forach opinii o różnych porównywarkach i najbardziej mi wpasował wspomniany WinMerge. Niestety tylko mogę w nim podejrzeć różnice, a potem wyszukiwać odpowiedniego stringu w Hex edytorze i tam się bawić. Niestety jest to mozolna praca. Jeszcze raz dzięki za podpowiedzi - będę sprawdzał.
Pozdrawiam

[belstar]

Może tu znajdziesz rozwiązanie
http://edu.i-lo.tarnow.pl/inf/alg/001_search/index.php

[b0bi]

Oooo... Dzięki bardzo - bardzo fajna strona

[mg2]

Jan wspomniał o narzedziu "diff". Konkretnie potrzebujesz "wdiff" lub "dwdiff".

Kod: Zaznacz cały

$ cat 1.txt
Ala ma brązowego kota i go nie kocha.

$ cat 2.txt
Ala ma miłego kota o imieniu Filemon i go bardzo kocha.

$ wdiff 1.txt 2.txt
Ala ma [-brązowego-] {+miłego+} kota {+o imieniu Filemon+} i go [-nie-] {+bardzo+} kocha.

Oba znajdziesz w każdej dystrybucji Linuxa. W przypadku Windowsa "wdiff" znajdziesz w projekcie "cygwin".
http://cygwin.com/

PS
http://linux.die.net/man/1/dwdiff

[b0bi]

Dzięki za podpowiedź - oczywiście sprawdzę, czy użyteczne w tym, co chcę osiągnąć.

[b0bi]

Trochę się naszukałem... pościągałem różne programy i pakiet Cygwina, próbowałem Diffem WDiffem, K-Diffem... różnymi comparatorami lecz żaden nie pracował tak, jak tego oczekiwałem.
I już myślałem, że trzeba będzie zabierać się za pisanie algorytmu i przekładać na formuły, kiedy trafiłem na narzędzie Beyond Compare 3, które rozwiązało moje problemy.
Tym samym problem został rozwiązany.
Dziękuję za wszelką pomoc.