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

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

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

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

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

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.

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.

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.