Wydajne struktury danych do budowy szybkiego sprawdzania pisowni

Próbuję napisać moduł sprawdzania pisowni, który powinien działać z dość dużym słownikiem. Naprawdę chcę efektywnego sposobu indeksowania danych słownikowych za pomocą odległości Damerau-Levenshteina w celu ustalenia, które słowa są najbliższe błędnie napisanemu słowu.

Szukam struktury danych, która dałaby mi najlepszy kompromis między złożonością przestrzeni a złożonością środowiska wykonawczego.

Na podstawie tego, co znalazłem w Internecie, mam kilka wskazówek dotyczących tego, jakiej struktury danych użyć:

Trie

trie-500px

To jest moja pierwsza myśl i wygląda na dość łatwą do wdrożenia i powinna zapewnić szybkie wyszukiwanie / wstawianie. Przybliżone wyszukiwanie za pomocą Damerau-Levenshtein powinno być również łatwe do wdrożenia tutaj. Ale nie wygląda to zbyt wydajnie pod względem złożoności przestrzeni, ponieważ najprawdopodobniej masz dużo narzutu dzięki przechowywaniu wskaźników.

Patricia Trie

trie-500px

Wydaje się, że zajmuje to mniej miejsca niż zwykła Trie, ponieważ zasadniczo unikasz kosztów przechowywania wskaźników, ale trochę martwię się fragmentacją danych w przypadku bardzo dużych słowników, takich jak to, co mam.

Drzewo sufiksów

przyrostek-500px

Nie jestem pewien co do tego, wygląda na to, że niektórzy uważają, że jest on użyteczny w eksploracji tekstu, ale nie jestem pewien, co dałoby to pod względem wydajności sprawdzania pisowni.

Drzewo wyszukiwania trójskładnikowego

tst

Wyglądają całkiem ładnie i pod względem złożoności powinny być zbliżone (lepiej?) Do Patricii Tries, ale nie jestem pewien, czy fragmentacja byłaby lepsza niż Patricia Tries.

Burst Tree

rozerwanie

To wydaje się hybrydowe i nie jestem pewien, jaką miałoby przewagę nad Tries i tym podobnymi, ale kilkakrotnie czytałem, że jest to bardzo wydajne w przypadku eksploracji tekstu.

Chciałbym uzyskać informacje zwrotne na temat tego, która struktura danych byłaby najlepsza w tym kontekście i co czyni ją lepszą niż inne. Jeśli brakuje mi niektórych struktur danych, które byłyby jeszcze bardziej odpowiednie dla sprawdzania pisowni, jestem również bardzo zainteresowany.

data-structures strings string-metrics

— Charles Menguy
źródło

W jaki sposób patricia trie unika kosztów przechowywania wskaźników? Czy to tylko en.wikipedia.org/wiki/Radix_tree ? Jeśli tak jest, to myślę, że nadal przechowuje wiele wskaźników, ale będziesz mieć ogromne oszczędności miejsca, ponieważ wspólne prefiksy są przechowywane tylko raz

— Joe

Bez szczegółów porównanie, o które prosisz, może być niemożliwe. W szczególności, jaką gęstość ma twój słownik? Do jakiej odległości chcesz wykryć błędy ortograficzne (wydaje się, że mówisz bez ograniczeń)? Jaka jest gęstość słownika + wariantów? (Gęstość tutaj oznacza ułamek wszystkich słów o długości który jest zawarty w przechowywanym zestawie.)

\geq n

$\geq n$

— Raphael

@linker: Czy wypróbowałeś już wszystkie warianty swojego słownika? Biorąc pod uwagę ustalony przypadek użycia, jest to prawdopodobnie najszybszy sposób na sprawdzenie, która struktura danych zajmuje tyle miejsca.

— Raphael

To tylko podstawowy słownik, po prostu znana lista poprawnie napisanych słów.

— Charles Menguy,

Zobacz także to najbardziej powiązane pytanie .

— Raphael

Napotkałem ten sam problem, ale podjąłem inne podejście. Możesz zbudować jakąś funkcję „mieszającą”, która dla podobnego słowa da taką samą lub zbliżoną liczbę.

Problem polega na tym, że funkcja, która da „dobry” wynik dla słów z wstawianiem / usuwaniem, da „zły” dla przejścia i odwrotnie. Przykład: zamapuj litery na cyfry, literę podobną do sąsiednich liczb i po prostu zsumuj je dla każdej litery w słowie. Następnie utwórz tabele skrótów z zestawami dla każdego klawisza i znajdź przecięcie dla słowa.

Być może niektóre wyniki zostaną osiągnięte, jeśli spojrzymy na „przestrzeń” słów. X do zmiany litery, Y do dodawania / usuwania, Z do przejścia lub coś w tym rodzaju.

Są to jednak tylko abstrakcyjne pomysły, nie mam czasu na ich wdrożenie.

— MadRunner
źródło

To właśnie robi Soundex en.wikipedia.org/wiki/Soundex

— rgrig

Możesz użyć drzewa metrycznego do szybkiego badania, jeśli brutalna siła nie jest możliwa (zawsze próbuj brutalnej siły). Znalezienie sąsiadów będzie możliwe w , ale stała w może być duża. Wydaje się, że masz miliony ciągów, więc może to być dobry kompromis. $\mathcal O(\log (n))$ $\mathcal O$

Nie przechowuj ciągów w drzewie metryk. Po prostu zapisz indeks i zapisz ciągi w drzewie Patricia.

Nie jestem pewien, którego drzewa powinieneś użyć. Będzie to zależeć od twoich danych i twoich wymagań (czy potrzebujesz szybkiego wstawiania?). Zaktualizuj swoje pytanie, jeśli okaże się, że jedno drzewo jest bardziej wydajne niż inne.

Możesz także spojrzeć na specjalistyczne narzędzia, takie jak Lucen.

— oao
źródło