Algorytm porównywania tekstu

Question

Mamy w projekcie wymaganie, aby porównać dwa teksty (update1, update2) i wymyślić algorytm określający liczbę słów i liczbę zdań.

Czy są jakieś algorytmy, z których można go użyć? Nawet nie szukam kodu. Jeśli znam algorytm, mogę go zakodować w Javie. Dziękuję Ci.

Answer 1

Zazwyczaj można to osiągnąć, znajdując numer Longest Common Subsequence (zwykle nazywany problemem LCS). Tak działają narzędzia takie jak diff. Oczywiście, diff jest narzędziem zorientowanym liniowo i wygląda na to, że twoje potrzeby są nieco inne. Jednak przypuszczam, że już zbudowałeś jakiś sposób porównywania słów i zdań.

Answer 2

Jakiś wariantu diff może być pomocne, np wdiff

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

The men are bad. I hate the men

i

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

Twój narzędzie powinno być w stanie patrzeć w przyszłość, aby uznać, że w drugim, I hate the men nie został zastąpiony przez John likes the men ale zamiast tego jest nietknięty i nowe zdanie wstawione przed nim. tj. powinien zgłosić wstawienie zdania, a nie zmianę czterech słów, po których następuje nowe zdanie.

Answer 3

Specyficznym algorytmem używanym przez diff i większość innych narzędzi do porównywania jest An O(ND) Difference Algorithm and Its Variations Eugene'a Myera. Jego implementacja Java jest dostępna w pakiecie java-diff-utils.

Answer 4

An O(NP) Sequence Comparison Algorithm jest używany przez silnik różnicowy subversion.

Dla twojej informacji, istnieją implementacje z różnymi językami programowania samodzielnie na następnej stronie github.

https://github.com/cubicdaiya/onp

Answer 5

Problem pojawia się przy porównywaniu dużych plików sprawnie i dobrej wydajności. Dlatego wprowadziła odmianę Myers O (ND) algorytmu diff - który funkcjonuje całkiem dobrze i dokładne (i obsługuje filtrowanie na podstawie wyrażenia regularnego):

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

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

Answer 6

Oto dwa artykuły opisujące inne algorytmy porównywania tekstu, które powinny generalnie "lepiej" wyprowadzać (np.Mniejsze, znaczące) różnice:

• Tichy, Walter F., "The String-to-String Correction Problem with Block Moves" (1983). Computer Science Technical Reports. Paper 378.
• Paul Heckel, "A Technique for Isolating Differences Between Files", Communications of the ACM, April 1978, Volume 21, Number 4

Pierwszy dokument powołuje drugim i wskazuje to o jego algorytmu:

Heckel [3] wskazano podobny problemy z technikami LCS i zaproponował algorytm liniowo-wapniowy do wykrywania ruchów bloków. Algorytm wykonuje odpowiednio , jeśli w ciągach występuje kilka zduplikowanych symboli. Jednak algorytm daje słabych wyników w przeciwnym razie. Na przykład, biorąc pod uwagę dwa łańcuchy, algorytm Heckela nie wykryje żadnego wspólnego podłańcucha.

Pierwszy dokument został wymieniony w this answer, a drugi w this answer zarówno w podobny SO pytania:

• Is there a diff-like algorithm that handles moving block of lines? - Stack Overflow