Całkiem niedawno natknąłem się na ciekawy artykuł Petera Norviga zatytułowany How to Write a Spelling Corrector. Przedstawiony w nim program urzeka swoją prostotą i sądzę, że jest znakomitym wprowadzeniem do tematu korekty tekstu jako zagadnienia wchodzącego w skład przetwarzania języka naturalnego. Rezultaty działania zaledwie 30-linijkowego dość łatwego do zrozumienia pythonowego kodu są zdumiewające – wprowadzane wyrazy zawierające literówki są w wielu przypadkach (Norvig pisze o skuteczności rzędu 80-90%) prawidłowo poprawiane. Przykłady? Proszę bardzo:

Jak to się dzieje? Oczywiście na nic zdałby się zaprogramowany algorytm, gdyby brakowało mu odpowiedniej bazy tekstów. W zalinkowanym przykładzie użyty został plik, zawierający nieco ponad milion wyrazów, z czego różnych słów jest w nim około 32 tysiące. W celu poprawy tekstu zaproponowany przez Petera Norviga skrypt dokonuje sprawdzenia wszystkich możliwych wyrazów o odległości Levenshteina od danego słowa równej maksymalnie 2 i wybiera ten, którego występowanie w języku (ustalone na podstawie analizy pliku z ponad milionem słów) cechuje się największą częstotliwością. Nie będę jednak skupiał się w tym wpisie na dokładnym tłumaczeniu zasady działania tego algorytmu korekcji, więc po szczegóły na ten temat zachęcam do lektury oryginalnego tekstu Norviga.

Pierwsze eksperymenty

Gdy wypróbowałem działanie korektora wyrazów od razu pomyślałem, że interesującym byłoby sprawdzenie czy podobną skuteczność można osiągnąć dla języka polskiego. W tym celu rozpocząłem poszukiwania odpowiedniego pliku wejściowego. Teoretycznie można by się pokusić o samodzielne stworzenie na tyle dużego zbioru tekstów, aby nasz poprawiacz błędów dawał jakieś sensowne rezultaty (i początkowo nawet o tym myślałem) – kompilacja książek z projektów typu Wikibooks, jakichś słowników itp. Czy jednak sensownym jest wynajdywać koło na nowo, skoro w internecie można znaleźć gotowe rozwiązania? Reprezentatywne dla danego języka, lub nawet konkretnej dziedziny, zbiory tekstów to tak zwane korpusy i ku mojej radości okazało się, że a w naszym kraju istnieje projekt o nazwie Narodowy Korpus Języka Polskiego (NKJP). Co więcej, w ramach Polskiej Akademii Nauk funkcjonuje Zespół Inżynierii Lingwistycznej, który na publicznych licencjach udostępnia efekty swoich analiz, m.in. n-gramy.

N-gramy to właśnie to, czego szukałem i potrzebowałem. Zbiór wszystkich wyrazów wyekstrahowanych z ogromnego korpusu, a także wszystkich występujących tam par słów, ich trójek, czwórek oraz piątek. Archiwa (w każdym z nich znajduje się tylko jeden plik tekstowy) dostępne są pod tym linkiem, a jeśli jesteście ciekawi ile takie statystyki ważą (po rozpakowaniu) oraz ile linii sobie liczą, to przybywam z odpowiedzią na te pytania:

• 1-gramy – 102 MB – 5 364 398 linii
• 2-gramy – 1.9 GB – 75 395 184 linii
• 3-gramy – 5.0 GB – 170 180 746 linii
• 4-gramy – 7.7 GB – 217 586 930 linii
• 5-gramy – 9.8 GB – 232 439 967 linii

Struktura każdego z plików, zawierających n-gramy oraz liczbę ich użyć w korpusie, prezentuje się zaś następująco:

Jak widać, jest co już całkiem pokaźna ilość danych, umożliwiająca napisanie z ich wykorzystaniem naprawdę sensownego programu. Oczywiście aby odwzorować działanie programu Petera Norviga wystarczy ograniczyć się do unigramów, ale gdy tylko zobaczyłem to przeogromne bogactwo informacji statystycznych w mojej głowie już zakiełkowało pragnienie pobawienia się n-gramami dla n>1.

Poprawianie niedoskonałości

Niestety szybko okazało się, że zdobyte n-gramy są w dosyć surowej postaci, która nieco utrudnia ich użycie w zaplanowany sposób. Po pierwsze, zbiór zawiera sporo wyrazów zawierających znaki należące do innych alfabetów niż łaciński. Aby się o tym przekonać wystarczy wpisać tail -500 1grams – ponieważ pobrane n-gramy z NKJP są posortowane zgodnie z częstotliwością ich występowania, to na samym końcu pliku znajdziemy te, których użyto zaledwie jeden raz. Naszym oczom ukażą się wtedy słowa z języka gruzińskiego, nepalskiego, japońskiego, rosyjskiego i innych, których przecież nie potrzebujemy wykorzystywać w korektorze języka polskiego.

Ok, usunięcie tego typu wyrazów nie jest akurat żadnym problemem, ale niestety to nie jedyna niedoskonałość naszego zbioru n-gramów. Znajdziemy w nim bowiem dość dużo znaków interpunkcyjnych „przyklejonych” do wyrazów. Np. poszukując słowa „programistyczne” zobaczymy taką listę unigramów:

Taka sytuacja generuje pewne problemy, bo jak teraz odpowiedzieć na pytanie ile zostało zliczonych wystąpień wyrazu „programistyczne”? 89? Czy może raczej 139? Pamiętajmy, że analizowanie tego typu przypadków już w czasie działania korektora jest wysoce niewskazane ze względu na wydajność, więc najlepszym rozwiązaniem jest doprowadzić do porządku listę n-gramów jeszcze przed jej użyciem.

Aby to osiągnąć zacząłem zastanawiać się nad skryptem, który dokonałby „zmergowania” ze sobą wszystkich wyrazów, które są tak naprawdę jednym i tym samym słowem, a różnią się jedynie jakimiś doklejonymi znakami interpunkcyjnymi. Z uwagi na rozmiar pliku owo zadanie nie byłoby trywialne i już-już zaczynałem takie pomocnicze narzędzie implementować, ale po poświęceniu jeszcze chwili na głębsze zastanowienie doszedłem do wniosku, że nie to jest istotą mojego ćwiczenia. Nie mam przecież zamiaru robić żadnego super korektora. Postanowiłem więc dać odpocząć perfekcjonizmowi i po prostu usunąłem z pliku z unigramami wszystkie niepasujące wyrazy, oczywiście z pełną świadomością pewnego zaburzenia rzeczywistych statystyk. Skrypt, który posłużył do takiego wyczyszczenia pobranych unigramów nosi nazwę UnigramsFixer.py i znajduje się w katalogu fixing-scripts.

Nieco zasmuciła mnie jeszcze jedna niedoskonałość zbioru, na którym przyszło mi pracować. Otóż niestety zawierał on również wyrazy z błędami ortograficznymi. Liczba zliczonych dla nich wystąpień była wprawdzie niewielka (zazwyczaj równa 1) i w przypadku n-gramów zbudowanych na podstawie większego korpusu tego typu wpisy po prostu się odrzuca, zakładając że są to właśnie różnego rodzaju literówki i pomyłki, ale czyniąc tak w tym przypadku pozbawiłbym się również wielu całkowicie poprawnych wyrazów, których niska częstotliwość występowania w subkorpusie sprawiła, że też legitymują się stojącą przy nich jedynką. O tym, jaką modyfikację wprowadziłem, aby w pewnym stopniu zniwelować ten problem napiszę nieco dalej.

Walka o wydajność

Nie pozostało mi już zatem nic innego, jak tylko wczytać finalny plik z unigramami i uruchomić pierwszą wersję korektora. Ale.. kiedy wczytać? Czy chcemy trzymać wszystkie dane w pamięci operacyjnej? Szybkość działania programu byłaby wtedy naprawdę zadowalająca, ale czy możemy sobie pozwolić na takie wykorzystanie zasobów? A może zamiast używać jednego dużego pliku tekstowego lepiej jakoś go podzielić (np. bazując na pierwszej literze wyrazu) i w odpowiednim czasie ładować do pamięci tylko ten, który w danej chwili jest potrzebny? Z racji, że mój korektor ma charakter wysoce eksperymentalny, zdecydowałem się zaimplementować wszystkie z powyższych rozwiązań i dokonać ich porównania.

Klasy odpowiedzialne za stwierdzanie czy określone słowa są ‚znane’ (tj. znajdują się w słowniku – zbiorze unigramów) umieściłem w pliku KnownWordsProvider.py. Są to:

• KnownWordsProviderUsingRAM – najprostsza z możliwych implementacji. Przy inicjalizacji wczytuje do pamięci operacyjnej cały zbiór unigramów jako słownik, którego kluczami są słowa, a wartościami częstotliwość ich występowania. Wywołanie metody known(words) sprowadza się zatem jedynie do stwierdzenia, czy wszystkie z podanych przez użytkownika słów znajdują się w ww. słowniku.
• KnownWordsProviderUsingBigFile – służy do testowania tego jak bardzo niewydajnym jest trzymanie wszystkich unigramów w jednym sporym pliku i otwieranie go dopiero przy wywołaniu metody known(words). Niewątpliwym atutem takiego podejścia jest znikome w porównaniu z wcześniejszą wersją wykorzystanie RAM-u, bowiem po otwarciu pliku dokonywana jest jedynie iteracja po wszystkich liniach w celu sprawdzenia czy dany wyraz jest tym, którego szukamy.
• KnownWordsProviderUsingMultipleFiles – implementacja, która opiera się na tym, że dane wejściowe programu można przygotować w taki sposób, aby korzystanie z nich było jak najbardziej wydajne. Zamiast posługiwać się plikiem zawierającym wszystkie 1404243 unigramów, dzielimy go wcześniej na 27 mniejszych plików odpowiadających poszczególnym literom alfabetu i umieszczamy w nich wyrazy, które zaczynają się na te litery. Skrypt, który w tym celu stworzyłem to UnigramsSplitter.py. Przy takim podejściu korektor od razu wie w którym pliku szukać słów, a z racji, że pliki te są o wiele mniejsze, program ma szansę działać szybciej.

Przykładowe wyniki pomiarów, jakie udało mi się osiągnąć (podane czasy to średnia z pięciu prób) przedstawiam w tabeli poniżej:

Słowo	RAM	BigFile	MultipleFiles
zaba	1.941 s.	2.926 s.	0.251 s.
pogramowanie	1.970 s.	5.186 s.	2.218 s.
dluzszy teksst zawierajacy lterówki	1.987 s.	12.451 s.	4.101 s.

Wyniki trudno uznać za niespodziewane. Wczytanie wszystkich słów do pamięci sprawia, że czas sprawdzania czy dany wyraz należy do słownika jest zdecydowanie najkrótszy. Ma to znaczenie zwłaszcza, gdy korektor operuje na dłuższych fragmentach tekstu. W przypadku poprawiania pojedynczych słów wygrywa natomiast provider, który wykorzystuje mniejsze pliki, ale zaczyna odstawać gdy poprosimy go o poprawianie fragmentów składających się z wielu wyrazów. Gdy jednak przyjrzeć się bliżej opisywanym tu klasom, szybko można dostrzec, że tak naprawdę w każdej z nich jest sporo miejsca na różnorodne optymalizacje. Np. w KnownWordsProviderUsingMultipleFiles zastosowałem grupowanie sprawdzanych kandydatów na podstawie ich pierwszej litery (patrz metoda split_words_by_first_letter() w pliku NGramsUtils.py). Dlaczego nie pójść o krok dalej i nie zaimplementować np. grupowania kandydatów wszystkich poprawianych słów, aby zredukować liczbę otwarć tego samego pliku?

Na koniec warto jeszcze wspomnieć, że rodzaj „dostarczyciela słów” można wybierać z poziomu argumentów linii poleceń (dokładniej przedstawiłem to pod koniec wpisu). Nie ma zatem żadnych przeciwwskazań, aby własnoręcznie nie porównać ich wydajności!

Literówki polskiego internauty

Świetnie, mamy poprawiony zbiór wyrazów, wydajność różnych implementacji została porównana, ale korektor wcale nie zachwyca swoimi rezultatami tak jak jego angielskojęzyczny odpowiednik:

Nie dość że nie poprawia, to jeszcze na dodatek psuje – można by powiedzieć. Dlaczego korektor proponuje nam takie a nie inne słowa? Przyjrzyjmy się im po kolei:

• ktory – ten wyraz, mimo że jest literówką, po prostu istnieje w naszym zbiorze unigramów.
• zolw – wyraz żółw, chociaż na pozór bliski, jest odległy aż o 3 edycje, stąd nie ma go wśród kandydatów.
• trabic – poprawne słowo – trąbić – jest odległe o 2 edycje, gdy tymczasem w słowniku istnieje wyraz trafic (swoją drogą też będący literówką) odległy o zaledwie jedną edycję.

Sprawdzanie za każdym razem wszystkich słów, które są odległe o 2 lub więcej edycji byłoby dość mało wydajne. Postanowiłem rozwiązać to w inny sposób i poniższą linijkę z metody SpellCorrector._candidates(word):

zamieniłem na:

Oznacza to, że zanim zostanie wyliczony zbiór wyrazów, będących kandydatami na poprawne słowo, sprawdzamy czy do podanego wyrazu daje się zastosować którąś ze zdefiniowanych podmian znaków diakrytycznych (czyli np. a -> ą, o -> ó, s -> ś itd.). Jeśli tak, to używamy go do wyboru wyrazu, cechującego się największą częstotliwością użycia na naszej liście unigramów, nawet jeżeli poprawiany wyraz też jest w słowniku – jest to istotna różnica wobec pierwotnego algorytmu i pozwala zmniejszyć ryzyko zwracania przez korektor błędnych wyrazów znajdujących się w słowniku (innymi słowy jest to częściowe rozwiązanie problemu, o którym pisałem pod koniec sekcji Poprawianie niedoskonałości).

Oczywiście implementacji tej daleko do ideału, ale pokazuje jeden z kierunków, w którym można iść, ulepszając oryginalną postać korektora. Spostrzegawczy Czytelnik być może zauważył już, że obecna wersja pozwala poprawić literę z na ż, ale nie pomaga w zamianie jej na ź – powiedzmy, że dopisanie tej funkcjonalności to „zadanie dodatkowe dla chętnych”. (-; Innym ciekawym ćwiczeniem może być dodanie poprawiania typowych dla naszego języka błędów ortograficznych, takich jak h-ch, ż-rz czy ą-om.

Bigramy wkraczają do gry

To, co udało się zrobić do tej pory, to w gruncie rzeczy jedynie odtworzenie funkcjonalności Norvigowego korektora z uwzględnieniem paru charakterystycznych dla języka polskiego elementów oraz dostosowaniem programu do innej postaci plików wejściowych zawierających dane słownikowe. Dlatego bardzo kusiło mnie, aby zaimplementować używanie bigramów i zobaczyć czy skuteczność korektora poprawi się. Ku mojemu zadowoleniu okazało się, że rzeczywiście – bigramy działają tak jak działać miały, a skutków tego działania nie trzeba długo szukać. Poniżej kilka przykładowych poprawek, dokonywanych przez wersję bez bigramów oraz z bigramami:

• programista komputerwy
  • unigramy: programista komputery
  • unigramy + bigramy: programista komputerowy
    
• wieszac ptanie
  • u: wieszać panie
  • u+b: wieszać pranie
• czerwony kaptre
  • u: czerwony kartce
  • u+b: czerwony kapturek
• wlazl ktek na płtek
  • u: wlazł kotek na płytek
  • u+b: wlazł kotek na płotek

Tym razem nie próbowałem nawet zaciekle walczyć o wydajność. Chciałem uzyskać jedynie satysfakcjonujące wyniki jeśli chodzi o samo poprawianie wyrazów, a żeby jako-tako działało to czasowo, wybrałem technikę wielu plików, dzieląc 2-gigabajtowy plik z bigramami na mniejsze porcje danych. Tym razem nie wystarczyło jednak, aby były to pliki z wyrazami grupowanymi po ich pierwszej literze. Trzeba było podzielić je wykorzystując dwie pierwsze litery, czego skutkiem jest prawie 1300 osobnych plików. Skrypt, który dokonuje takiego podziału to BigramsSplitter.py i ze względu na fakt, że utworzenie ponad tysiąca deskryptorów  plików równocześnie nie jest dobrym pomysłem, jest on nieco bardziej skomplikowany niż jego odpowiednik do transformacji unigramów.

Korektor funkcyjny

Zaimplementowanie korektora w OCamlu było jednym z pomysłów, które narodziły się w mojej głowie natychmiast po przeczytaniu artykułu Norviga. Zmierzenie się z próbą napisania takiego nietrywialnego programu to wszak jeden z lepszych sposobów nauki języka. Chociaż szybko zweryfikowałem, że wersje korektora w OCamlu już oczywiście powstały (np. autorstwa Stefano Pacifico oraz Alexandre Grisona), celowo nie czytałem ich, aby nie zasugerować się wykorzystanymi tam sposobami rozwiązania problemu.

Moja implementacja znajduje się w pliku corrector.ml i liczy sobie 189 linii. Jest to funkcyjna wersja zwykłego Norvigowego poprawiacza pisowni i nie jest w żaden specjalny sposób przystosowana do języka polskiego. Dodałem tam natomiast możliwość wyboru trybu interaktywnego oraz wsadowego. Tworzenie korektora w OCamlu dostarczyło mi chyba najwięcej zabawy, ponieważ wymagało całkiem innego sposobu myślenia niż ten, do którego jestem przyzwyczajony, pisząc na co dzień w językach imperatywnych. Przyznaję się wprawdzie, że w jednym miejscu nieco naruszyłem paradygmat funkcyjny, korzystając z mutowalnej tablicy haszującej w celu przechowywania par wyraz-liczba, ale zapewniam że we wszędzie indziej sumiennie starałem podążać się właściwą ścieżką, unikając pętli na korzyść rekurencji i stosując wielką trójcę map-filter-reduce.

Najciekawszym etapem było rzecz jasna zaimplementowanie funkcji odpowiadających za generowanie listy kandydatów. Dzielenie słowa, a później wykonywanie transpozycji, usunięć, zamian i wstawień. W trakcie pisania wpadały mi do głowy różne koncepcje jak zaprogramować poszczególne metody i wydaje mi się, że efekt końcowy jest całkiem zgrabny. Na przykład dzięki wydzieleniu części wspólnej operacji wstawiania liter oraz ich zamieniania wyglądają one tak:

Z kolei funkcja odpowiedzialna za usuwanie liter początkowo wyglądała jak poniżej:

, natomiast po paru eksperymentach przekształciła się w takiego oto pięknego jednolinijkowca:

Myślę, że jest to jeden z tych przykładów, które dobitnie dowodzą jak ciekawe i rozwijające jest zastosowanie podejścia funkcyjnego. Pokazuje to też, że moja znajomość OCamla nie jest jeszcze na poziomie, który pozwalałby napisać taką metodę ot tak – bez przesadnego zastanawiania się i od razu w eleganckiej formie, co raczej nie sprawiałoby większych trudności np. w Pythonie. Przyznaję, że tworzenie tych funkcji wiązało się ze sporą liczbą prób w środowisku interaktywnym i nierzadko dochodzeniem krok po kroku do właściwej formy, ale zdecydowanie było warto. To, ile rozrywki dostarczają próby przełożenia imperatywnych algorytmów na funkcyjne schematy OCamla sprawiło, że naprawdę pokochałem ten język.

Jak używać?

Programistów zachęcam do samodzielnego eksperymentowania z zaprezentowanym przez Norviga korektorem pisowni. Być może wartościowym doświadczeniem będzie dla niektórych zapoznanie się z moją implementacją, przetestowanie jej i pozmienianie tu i ówdzie. Aby ułatwić takim osobom początkowe kroki, przygotowałem krótką instrukcję użycia opisywanego w tym wpisie programu.

1. Pobierz repozytorium zawierające pliki korektora
2. Ze strony NKJP pobierz pliki z unigramami oraz bigramami
3. Pierwszy z nich popraw przy użyciu UnigramsFixera oraz podziel UnigramsSplitterem, natomiast plik zawierający bigramy podziel przy użyciu BigramsSplittera (skrypty te znajdują się w katalogu fixing-scripts).
4. Powkładaj pliki do wybranych przez siebie katalogów i w pliku python/InteractiveCorrector.py przypisz je do zmiennych, znajdujących się u samej góry
5. Jeśli chcesz korzystać również z wersji OCamlowej, to:
   1. Ścieżkę do pliku z unigramami podaj również w funkcji load_known_words w pliku ocaml/corrector.ml
   2. Skompiluj program poleceniem ocamlfind ocamlc str.cma -package core_extended -thread -linkpkg corrector.ml -o corrector (wymagane jest posiadanie zainstalowanego i skonfigurowanego środowiska OCamla)
6. Możesz już używać korektora!

Użycie: InteractiveCorrector.py [-h] [-b] [-w WORD] [-t TYPE]

Argumenty opcjonalne:

• -h, –help – wyświetla pomoc
• -b, –bigrams – włącza używanie bigramów do poprawy wyrazów
• -w SŁOWO, –word SŁOWO – tryb ‚wsadowy’, program tłumaczy podany tekst (jeśli zawiera kilka wyrazów, należy umieścić go w cudzysłowie) i kończy działanie
• -t TYP, –type TYP – używa wybranego „dostarczyciela słów”. Możliwe opcje: RAM (domyślnie), BigFile, MultipleFiles

Jeśli program startowany jest bez żadnych flag, zostaje uruchomiony w trybie interaktywnym, który umożliwia wielokrotne wprowadzanie tekstu przez użytkownika.

Użytkowanie OCamlowej wersji korektora jest jeszcze mniej skomplikowane, ponieważ ogranicza się do dwóch alternatywnych sposobów:

• ./corector -i – tryb interaktywny
• ./corrector "fraza do korekty" lub ./corrector słowo – tryb wsadowy

Grzebanie w kodzie radzę zaś rozpocząć od zerknięcia okiem na testy jednostkowe – myślę, że zawarte tam przykłady mogą co nieco rozjaśnić.

Linki

• How to Write a Spelling Corrector, P. Norvig.
• Natural Language Corpus Data: Beautiful Data, P. Norvig.
• How to Do Things with Word, P. Norvig.
• Spelling correction using N-grams, D. Sundby.
• What are N-Grams?
• Narodowy Korpus Języka Polskiego, PWN 2012.
• Implementacja korektora opisywana w tym wpisie – repozytorium na GitHub