Algorytm porównywania tekstu

Algorytm porównywania sekwencji O(NP) jest używany przez silnik diff subversion.

Dla twojej informacji, na poniższej stronie github znajdują się implementacje z różnymi językami programowania.

Https://github.com/cubicdaiya/onp

Jakiś wariant diff może być pomocny, np wdiff

Jeśli zdecydujesz się opracować własny algorytm, będziesz musiał zająć się sytuacją, w której zdanie zostało wstawione. Na przykład dla następujących dwóch dokumentów:

The men are bad. I hate the men

I

The men are bad. John likes the men. I hate the men

Twoje narzędzie powinno być w stanie spojrzeć w przyszłość, aby rozpoznać, że w drugim {[2] } nie zostało zastąpione przez John likes the men, ale zamiast tego jest nietknięte, a przed nim wstawiono nowe zdanie. tj. it powinien zgłaszać wstawianie zdania, a nie zmianę czterech słów, po których następuje nowe zdanie.

Specyficznym algorytmem używanym przez diff i większość innych narzędzi porównawczych jest algorytm różnicy o(ND) Eugene ' a Myera i jego wariacje . Jest to implementacja Javy dostępna w pakiecie java-diff-utils.

Oto dwie prace opisujące inne algorytmy porównywania tekstu, które powinny generować "lepsze" (np. mniejsze, bardziej znaczące) różnice:

• Tichy, Walter F., "the String-to-String Correction Problem with Block Moves" (1983). Informatyka Raporty Techniczne. Przekaz 378.
• W latach 1975-1998 miejscowość administracyjnie należała do województwa siedleckiego.]}

Pierwsza gazeta cytuje drugi i wspomina o tym o swoim algorytmie:

Heckel [3] zwrócił uwagę na podobne problemy z technikami LCS i zaproponował algorytm liniowo-liniowy do wykrywania ruchów bloków. Algorytm wykonuje odpowiednio jeśli w łańcuchach jest kilka zduplikowanych symboli. Jednak algorytm daje w przeciwnym razie słabe wyniki. Na przykład, biorąc pod uwagę dwa ciągi aabb i bbaa , Algorytm heckela nie wykrywa żadnego wspólnego fragmentu.

The pierwszy artykuł został wymieniony w tej odpowiedzi , a drugi w tej odpowiedzi , oba na podobne pytanie SO:

• czy istnieje algorytm podobny do Diffa, który obsługuje ruchomy blok linii? - Przepełnienie Stosu

Trudność polega na wydajnym porównywaniu dużych plików z dobrą wydajnością. Dlatego zaimplementowałem odmianę algorytmu Myers O(ND) diff - który działa dość dobrze i dokładnie (i wspiera filtrowanie oparte na wyrażeniach regularnych):

Algorytm można przetestować tutaj: becke.ch compare tool web application

I trochę więcej informacji na stronie głównej: becke.ch compare tool