Co robi porównywarka tekstu
Narzędzie odpowiada na pytanie, co dokładnie zmieniło się między dwiema wersjami tego samego dokumentu, i wskazuje położenie wszystkich różnic w tekście. Zamiast czytać obie wersje równolegle i wyłapywać zmiany wzrokiem, dostajesz je podświetlone - usunięte fragmenty na czerwono, dodane fragmenty na zielono. To ten sam mechanizm, z którego programiści korzystają od kilkudziesięciu lat pod nazwą diff, przystosowany do tekstu pisanego. Anglojęzyczne nazwy tej klasy narzędzi brzmią diff checker albo text compare. Wersje można wklejać ze schowka, a przy dłuższych materiałach wygodniej pracować z plikami TXT upuszczonymi na pola tekstowe.
Kancelaria chce sprawdzić różnice, które druga strona wprowadziła w projekcie umowy, redaktor zestawia wersję sprzed korekty z wersją po niej, a tłumacz szuka poprawek, które klient wprowadził w tłumaczeniach. Zdarzają się użycia prostsze, na przykład sprawdzenie, czy skopiowany fragment regulaminu jest identyczny z oryginałem. Śledzenie zmian w dokumentach z edytora tekstu pokazuje mniej więcej to samo, ale wymaga włączenia przed edycją przez obie strony, a porównywarka radzi sobie po fakcie, mając do dyspozycji dwa gotowe pliki.
Algorytm najdłuższego wspólnego podciągu
Porównanie sprowadza się do problemu najdłuższego wspólnego podciągu (LCS). Dla dwóch ciągów elementów szukamy najdłuższej sekwencji obecnej w obu, niekoniecznie ciągłej, ale z zachowaniem kolejności. Wszystko poza tą sekwencją jest różnicą, w której elementy pierwszego tekstu zostają zapisane jako usunięcia, a elementy drugiego jako dodania.
Liczymy to metodą programowania dynamicznego. Budujemy tablicę o wymiarach odpowiadających długościom obu tekstów i wypełniamy ją, przechodząc element po elemencie. Gdy dwa elementy są równe, długość wspólnego podciągu rośnie o jeden, w przeciwnym razie bierzemy lepszy z dwóch wcześniejszych wyników. Potem cofamy się po tablicy od końca i odczytujemy, które elementy zostały dopasowane.
Implementacja jest własna, napisana w JavaScripcie od zera na potrzeby tego serwisu. Wiele porównywarek opiera się na gotowej bibliotece diff-match-patch, tutaj kod wczytuje się razem ze stroną i porównanie odbywa się w przeglądarce, bez sięgania po cudze pliki z zewnętrznych serwerów.
Dlaczego długie teksty mają limit
Koszt algorytmu jest iloczynem długości obu tekstów. Dwa teksty po tysiąc słów dają milion komórek tablicy i liczą się w ułamku sekundy, a dwa teksty po sto tysięcy znaków dają dziesięć miliardów komórek, czyli dziesiątki gigabajtów pamięci. Limit wynosi cztery miliony porównań i po jego przekroczeniu narzędzie pokazuje komunikat zamiast zawieszać kartę przeglądarki.
Zanim jednak dojdzie do liczenia tablicy, odcinamy wspólny początek i wspólny koniec obu tekstów. W praktyce działa to bardzo skutecznie, bo poprawka jednego zdania w środku długiego dokumentu zostawia do porównania okolice tej poprawki zamiast całego materiału. Gdy mimo to trafisz na limit, przełącz jednostkę na wiersze - wierszy jest zawsze o rząd wielkości mniej niż znaków. Porównanie całych książek wymaga podziału na rozdziały, bo dwa teksty po pięć tysięcy wierszy to już dwadzieścia pięć milionów porównań.
Trzy jednostki porównania
Tryb słowny jest ustawieniem domyślnym, bo porównanie tekstu ciągłego najlepiej wychodzi wyraz po wyrazie, a zmiana jednego słowa zostaje wtedy pokazana jako zmiana tego słowa zamiast całego akapitu. Tryb wierszy idzie linia po linii i pasuje do materiałów o stałej strukturze, od kodu i plików konfiguracyjnych po listy i pliki log. Tryb znaków porównuje znak po znaku i przydaje się przy krótkich napisach, numerach kont albo kodach rabatowych, gdzie różnica bywa jednocyfrowa.
Wybór trybu wpływa też na wynik procentowy, bo zmienia jednostkę, w której mierzymy podobieństwo. Ten sam materiał może dać 85% w trybie słów i 94% w trybie znaków, bo zmieniony wyraz to jeden element z kilkuset słów, ale tylko kilka znaków z kilku tysięcy. Obie liczby są poprawne, mierzą po prostu co innego.
Białe znaki, wielkość liter i końce wierszy
Dwa pola wyboru pod tekstami zmieniają to, co algorytm uznaje za element identyczny. Zaznaczenie „Ignoruj białe znaki” usuwa z porównania wszystkie odstępy, od pojedynczej spacji po tabulator, więc tekst przeklejony z PDF-u ze złamanymi wierszami przestaje różnić się od tej samej treści w jednym akapicie. Zaznaczenie „Ignoruj wielkość liter” sprowadza obie wersje do małych liter według polskich reguł, więc różnica wielkości liter przestaje być zmianą, a wynik podświetla wyłącznie te miejsca, w których faktycznie zmieniono słowa.
Osobny kłopot sprawiają końce wierszy. Windows kończy wiersz parą znaków CR i LF, systemy z rodziny Unix i macOS samym LF, więc plik przeniesiony z jednego systemu na drugi potrafi pokazać każdy wiersz jako zmieniony, choć treść pozostaje identyczna co do litery. W trybie wierszy nie ma to znaczenia, bo tekst dzielimy na wiersze niezależnie od użytego separatora. W trybie słów i znaków wystarczy włączyć „Ignoruj białe znaki”, żeby różnica zniknęła.
Prywatność przy dokumentach poufnych
Do porównywarki trafiają materiały, których lepiej nikomu nie wysyłać - projekty umów, oferty przetargowe, dokumentacja wewnętrzna, akta z danymi osobowymi. Większość dostępnych w sieci porównywarek wysyła oba teksty na swój serwer i tam wykonuje obliczenia, bo tak jest prościej napisać.
Tutaj porównanie odbywa się w przeglądarce. Przeglądarka porównuje tekst na Twoim urządzeniu i tam trzyma obie wersje aż do zamknięcia karty, więc na naszym serwerze nic nie zostaje. Możesz to zweryfikować bez zaufania nam na słowo. Otwórz narzędzia deweloperskie, przejdź do zakładki „Sieć”, wklej teksty i kliknij „Porównaj” - lista zapytań wychodzących pozostanie pusta. Po wczytaniu strony możesz też odłączyć się od internetu, a porównywarka będzie działać dalej.