Sugestia pisowni

Sugerowanie pisowni to funkcja wielu aplikacji komputerowych używana do sugerowania wiarygodnych zamienników słów, które prawdopodobnie zostały błędnie napisane.

sugestii pisowni są powszechnie dostępne w wyszukiwarkach internetowych , edytorach tekstu , modułach sprawdzania pisowni , transkrypcjach medycznych , automatycznym przeformułowaniu zapytań i raportach statystycznych dotyczących częstotliwości.

Algorytmy

Każdy moduł sprawdzania pisowni musi mieć pewne dane o słowach w języku docelowym, zarówno w użyciu ogólnym, jak i ze specjalistyczną wiedzą (np. Słownictwo medyczne). Może to pochodzić z:

• Słownik wszystkich znanych słów .
• Korpus tekstowy zawierający typowy tekst, o znanej poprawnej pisowni.
• Lista często błędnie zapisywanych słów, mapowanie błędów na poprawki.
• Dzienniki wprowadzania tekstu przez ludzi, na przykład z popularnej wyszukiwarki . Zasadniczo jest to pozyskiwany w ramach crowdsourcingu , ale zakłada się, że wystąpią pewne błędy ortograficzne. Dane mogą być uwzględniane o tym, kiedy ludzie klikają sugestię dotyczącą pisowni lub zadają drugie, bardzo podobne zapytanie; tworzy to crowdsourcingowe mapowanie błędnie napisanych słów na wiarygodne poprawki.

Listę często błędnie zapisywanych słów, być może zawierającą wielowyrazowe frazy, można po prostu przejrzeć, aby zobaczyć, czy któreś z wprowadzonych słów lub fraz są na liście.

Aby skorzystać ze słownika bez wcześniejszego mapowania błędów ortograficznych na poprawki, typową techniką jest obliczenie odległości edycji między słowem wejściowym a dowolnym słowem w słowniku. Metryka odległości Levenshteina traktuje „edycję” jako wstawienie, usunięcie lub zastąpienie (inną literą) jednej litery. Odległość Damerau -Levenshteina dodaje transpozycje (zamiana sąsiednich liter). Słowa ze słownika, które znajdują się w odległości edycji 1 od słowa wejściowego, są uważane za wysoce prawdopodobne jako poprawki, odległość edycji 2 jest mniej prawdopodobna, a odległość edycji 3 jest czasami uwzględniana w sugestiach, a czasami ignorowana.

Korpus tekstowy można podsumować jako słownik znanych słów, z częstotliwością występowania każdego słowa. Można tego użyć do sortowania sugestii dotyczących pisowni. Na przykład, jeśli istnieje wiele sugestii dotyczących odległości edycji 1, słowa, które pojawiają się najczęściej w korpusie, najprawdopodobniej będą żądaną poprawką.

Ponieważ słownik znanych słów jest bardzo duży, obliczanie odległości edycji między słowem wejściowym a każdym słowem w słowniku jest intensywne obliczeniowo, a zatem stosunkowo powolne. Do przyspieszenia wyszukiwania w pamięci można wykorzystać różne struktury danych , takie jak drzewa BK . Szybsze podejście przyjęte przez Petera Norviga generuje wszystkie permutacje ze słowa wejściowego wszystkich możliwych edycji. Dla słowa o długości n i alfabetu o rozmiarze a , dla odległości edycji 1 jest co najwyżej n usunięć, n-1 transpozycji, a*n i insercje a*(n+1) . Używając tylko 26 liter alfabetu angielskiego , dałoby to tylko 54*n+25 wyszukiwania w słowniku, pomniejszone o wszelkie duplikaty (co zależy od konkretnych liter w słowie). To stosunkowo niewiele w porównaniu ze słownikiem zawierającym setki tysięcy słów. Jednak dla odległości edycji 2 i większej mogą być wymagane dziesiątki lub setki tysięcy wyszukiwań. Kolejna innowacja przyjęta przez Wolfa Garbe, znana jako SymSpell („sym” jak w „symetrii”) przyspiesza obliczanie czasu wprowadzania, wykorzystując fakt, że dla słów wejściowych muszą być generowane tylko permutacje obejmujące usunięcia, jeśli te same permutacje usunięcia są na -obliczone na słownik.

Opisane do tej pory algorytmy nie radzą sobie dobrze z poprawnymi słowami, których nie ma w słowniku. Częstym źródłem nieznanych słów w języku angielskim są wyrazy złożone i odmiany , takie jak -s i -ing . Można je dostosować algorytmicznie, zwłaszcza jeśli słownik zawiera część mowy .

Algorytmy te zakładały również, że wszystkie błędy danej odległości są jednakowo prawdopodobne, co nie jest prawdą. Błędy polegające na pisowni fonetycznej tam, gdzie angielska ortografia nie jest fonetyczna, są powszechne, podobnie jak błędy polegające na powtarzaniu tej samej litery lub myleniu sąsiednich liter na klawiaturze QWERTY . Jeśli dostępny jest duży zestaw znanych błędów ortograficznych i poprawek, dane te można wykorzystać do wygenerowania tabel częstotliwości dla par liter i typów edycji; można ich użyć do dokładniejszego uszeregowania sugestii. Jest to również bardziej powszechne niż szansa, że ​​słowo zostanie zapisane w niewłaściwym dialekcie w porównaniu z resztą tekstu, na przykład z powodu różnic w pisowni amerykańskiej i brytyjskiej .

Sugestie dotyczące pisowni mogą być również dokładniejsze, biorąc pod uwagę więcej niż jedno słowo na raz. Sekwencje wielowyrazowe są znane jako n-gramy (gdzie n to liczba słów w sekwencji). Bardzo duża baza danych n-gramów o długości do 5 słów jest dostępna w Google do tego i innych celów.

Inni eksperymentowali z wykorzystaniem dużych ilości danych i technik głębokiego uczenia się (forma uczenia maszynowego do trenowania sieci neuronowych w celu poprawiania pisowni.