Jaki jest dobry algorytm, aby przejść Trie, aby sprawdzić sugestie ortograficzne?
Zakładając, że zbudowany jest ogólny Trie słów słownikowych, jaka byłaby najlepsza metoda sprawdzania 4 przypadków błędów ortograficznych - zastępowania, usuwania, transpozycji i wstawiania podczas przechodzenia?
Jedną z metod jest określenie wszystkich słów w n odległości edycji danego słowa, a następnie sprawdzenie ich w Trie. Nie jest to zła opcja, ale lepszą intuicją tutaj wydaje się być użycie dynamicznej metody programowania (lub rekurencyjnego odpowiednika) w celu określenia najlepszego sub-próbuje po zmodyfikowaniu słów podczas trawersu.
Wszelkie pomysły będą mile widziane!
PS, doceniłbym rzeczywiste wejścia, a nie tylko linki w odpowiedziach.
4 answers
Napisałem kiedyś jakiś kod, żeby to zrobić:
Https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py
Jest oparty na kodzie Petera Norviga ( http://norvig.com/spell-correct.html ), ale przechowuje słownik w trie, aby szybciej znaleźć słowa w danej odległości edycji.
Algorytm wykonuje Trie rekurencyjnie stosując możliwe edycje (lub nie) na każdym kroku po drodze, pochłaniając litery ze słowa wejściowego. A parametr do wywołania rekurencyjnego określa, ile można jeszcze dokonać edycji. Trie pomaga zawęzić przestrzeń wyszukiwania, sprawdzając, które litery można rzeczywiście dotrzeć z naszego podanego prefiksu. Na przykład, gdy wstawiamy znak, zamiast dodawać każdą literę w alfabecie, dodajemy tylko litery, które są osiągalne z bieżącego węzła. Brak edycji jest równoznaczny z pobraniem gałęzi z bieżącego węzła w trie wzdłuż bieżącej litery ze słowa wejściowego. Jeśli tej gałęzi nie ma następnie możemy cofnąć się i uniknąć przeszukiwania potencjalnie dużej przestrzeni, w której nie można znaleźć prawdziwych słów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-09 18:05:06
Myślę, że możesz to zrobić za pomocą prostego wyszukiwania w drzewie: wybierz próg liczby błędów, których szukasz, po prostu przeprowadź litery słowa, które mają być dopasowane pojedynczo, generując zestaw par (prefix, subtrie) osiągniętych do tej pory pasujących do prefiksu, a gdy jesteś poniżej progu błędu, Dodaj do swojego zestawu kolejnych podstron:
- No error at this character place: add the subgoal of the trie at the next character in the word
- wstawiony, usunięty lub podstawiony znak w tym miejscu: znajdź tam odpowiedni trie i zwiększ liczbę błędów;
- nie jest to dodatkowy cel, ale zauważ, że transpozycje są albo wstawianiem, albo usuwaniem, które pasuje do wcześniejszego usunięcia lub wstawiania: jeśli ten test wstrzymuje się, to nie zwiększaj liczby błędów.
To wydaje się dość naiwne: czy jest z tym jakiś problem, który skłonił Cię do myślenia o programowaniu dynamicznym?
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-15 09:07:54
Zakładając, że każdy kolejny znak w Twoim słowie reprezentuje jeden poziom w twoim drzewie, masz pięć przypadków do sprawdzenia przy każdym znaku (dopasowanie, usunięcie, wstawienie, podstawienie i transpozycja). Zakładam, że transpozycje są dwoma sąsiadującymi ze sobą znakami.
Będziesz potrzebował funkcji (CheckNode), która akceptuje węzeł drzewa i znak do sprawdzenia. Będzie musiał zwrócić zestaw węzłów (child/grand-child) reprezentujących dopasowania.
Będziesz potrzebował funkcji (CheckWord), która / align = "left" / Sprawdza każdy znak po kolei względem zestawu węzłów. Zwróci zestaw węzłów (leaf) reprezentujących dopasowane słowa.
Chodzi o to, że każdy poziom w drzewie (dziecko, dziadek itp.), odpowiada pozycji znaku w słowie. Jeśli wywołasz węzeł drzewa najwyższego poziomu, poziom 0, wtedy będziesz miał Poziom 1, Poziom 2 itp.
Oczywiście dla słowa bez błędów, istnieje dopasowanie Jeden do jednego między pozycją znaku a poziomem w drzewo.
Aby usunąć, musisz pominąć poziom w drzewie.
Aby wstawić, musisz pominąć znak w słowie.
W przypadku zastępstw, musisz pominąć zarówno poziom, jak i postać.
W przypadku transpozycji należy (tymczasowo) zamienić znaki w słowie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-15 12:00:09
Przyjrzyj się obliczeniu odległości Levenshteina , która zapewnia dynamiczne rozwiązanie programistyczne do znajdowania odległości między dwoma sekwencjami.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-14 23:14:30