Jaki algorytm jest zwykle używany podczas implementowania modułu sprawdzania pisowni, któremu towarzyszą sugestie słów?
Na początku pomyślałem, że sensowne może być sprawdzenie każdego nowego wpisanego słowa (jeśli nie ma go w słowniku) pod kątem jego odległości Levenshteina od każdego innego słowa w słowniku i zwrócenie pierwszych wyników. Wydaje się jednak, że byłoby to wysoce nieefektywne, wymagając wielokrotnej oceny całego słownika.
Jak to się zazwyczaj robi?
Jest dobry esej autorstwa Petera Norviga, jak wdrożyć korektor pisowni. Jest to w zasadzie metoda brutalnej siły, próbująca sprawdzać ciągi kandydatów z określoną odległością edycji. ( Oto kilka wskazówek, jak poprawić wydajność korektora pisowni za pomocą filtra Blooma i szybszego haszowania kandydatów ).
Wymagania dotyczące modułu sprawdzania pisowni są słabsze. Musisz tylko dowiedzieć się, że słowa nie ma w słowniku. Możesz użyć filtra wykwitów, aby zbudować moduł sprawdzania pisowni, który zużywa mniej pamięci. Starożytna wersja jest opisana w Perły programowania autorstwa Jona Bentleya przy użyciu 64kb dla angielskiego słownika.
BK-Tree jest alternatywne podejście. Ładny artykuł jest tutaj .
Odległość Levenshsteina nie jest dokładnie odpowiednią odległością edycji dla modułu sprawdzania pisowni. Zna tylko wstawianie, usuwanie i podstawianie. Brak transpozycji i daje 2 dla transpozycji 1 znaku (to jest 1 usunięcie i 1 wstawienie). Odległość Damerau – Levenshteina to właściwa odległość edycji.
Podejściem do generowania sugestii, które z powodzeniem stosowałem, ale nigdzie nie widziałem opisanego, polega na wstępnym obliczaniu sugestii (podczas budowania słownika) przy użyciu „złych” funkcji skrótu.
Chodzi o to, aby przyjrzeć się typom błędów pisowni, które ludzie popełniają, i zaprojektować funkcje skrótu, które przypisałyby niepoprawną pisownię do tego samego zasobnika, co poprawna pisownia.
Na przykład, częstym błędem jest użycie niewłaściwego samogłoskę, jak zdecydowanym zamiast definitywna . Więc projektujesz funkcję skrótu, która traktuje wszystkie samogłoski jako tę samą literę. Łatwym sposobem na to jest najpierw „znormalizowanie” słowa wejściowego, a następnie umieszczenie znormalizowanego wyniku za pomocą zwykłej funkcji skrótu. W tym przykładzie funkcja normalizująca może porzucić wszystkie samogłoski, więc stanie
definitesiędfnt. Słowo „znormalizowane” jest następnie hashowane za pomocą typowej funkcji skrótu.Wstaw wszystkie słowa ze słownika do pomocniczego indeksu (tablicy skrótów) za pomocą tej specjalnej funkcji skrótu. Zasobniki w tej tabeli będą miały długie listy kolizji, ponieważ funkcja skrótu jest „zła”, ale te listy kolizji są zasadniczo wstępnie obliczonymi sugestiami.
Teraz, gdy znajdziesz błędnie napisane słowo, przeszukujesz listy kolizji dla zasobnika, do którego odwzorowuje błąd pisowni w indeksach pomocniczych. Ta da: Masz listę sugestii! Wszystko, co musisz zrobić, to uszeregować zawarte w nim słowa.
W praktyce będziesz potrzebować kilku pomocniczych indeksów z innymi funkcjami skrótu do obsługi innych typów błędów, takich jak transponowane litery, pojedyncza / podwójna litera, a nawet uproszczony, podobny do Soundexa, aby wychwycić błędy ortograficzne. W praktyce znalazłem uproszczone wymowy, które przeszły długą drogę i zasadniczo przestarzały niektóre z tych, które miały na celu znalezienie trywialnych literówek.
Więc teraz wyszukujesz błędy ortograficzne w każdym z indeksów pomocniczych i łączysz listy kolizji przed rankingiem.
Pamiętaj, że listy kolizji zawierają tylko słowa, które są w słowniku. Dzięki podejściom, które próbują generować alternatywną pisownię (jak w artykule Petera Norviga), możesz uzyskać (dziesiątki) tysięcy kandydatów, których najpierw musisz przefiltrować w słowniku. Dzięki wstępnie obliczonemu podejściu otrzymujesz może kilkaset kandydatów i wiesz, że wszystkie są poprawnie napisane, więc możesz przejść od razu do rankingu.
Aktualizacja : Od tego czasu znalazłem jeden opis algorytmu, który jest podobny do tego, Wyszukiwanie rozproszone FAROO . Wciąż jest to wyszukiwanie ograniczone do edycji, ale jest bardzo szybkie, ponieważ etap obliczeń wstępnych działa jak mój pomysł na „złe funkcje skrótu”. FAROO używa tylko ograniczonej koncepcji złej funkcji skrótu.
źródło
Algorytm
Optymalizacja
Bardziej szczegółowe wyjaśnienia i kod źródłowy można znaleźć w projekcie github .
źródło
Nie musisz znać dokładnej odległości edycji dla każdego słowa w słowniku. Możesz zatrzymać algorytm po osiągnięciu wartości granicznej i wykluczyć słowo. Pozwoli to zaoszczędzić dużo czasu na obliczeniach.
źródło
Sprawdzanie pisowni jest bardzo łatwe do zaimplementowania, podobnie jak w programie do sprawdzania pisowni w systemie Unix. Kod źródłowy jest dostępny publicznie. Można wprowadzić korektę, jedną techniką jest dokonanie edycji i ponowne sprawdzenie, czy to nowe słowo jest w słowniku. Takie nowe zmiany można grupować i wyświetlać użytkownikowi.
System Unix wykorzystuje program napisany przez Mc IllRoy'a. Alternatywnym sposobem jest użycie Trie, co może być przydatne w przypadku dużych plików.
Podejście uniksowe wymaga bardzo mniej miejsca na ogromny słownik, ponieważ używa algorytmu mieszania rozproszonego.
źródło