Эффективные структуры данных для построения быстрой проверки орфографии

41

Я пытаюсь написать проверку орфографии, которая должна работать с довольно большим словарем. Я действительно хочу, чтобы эффективный способ индексирования данных моего словаря использовался с использованием расстояния Дамерау-Левенштейна, чтобы определить, какие слова наиболее близки к слову с ошибкой.

Я ищу структуру данных, которая дала бы мне лучший компромисс между сложностью пространства и сложностью во время выполнения.

Основываясь на том, что я нашел в Интернете, у меня есть несколько рекомендаций относительно того, какой тип структуры данных использовать:

Trie

Trie-500px

Это моя первая мысль, и она выглядит довольно простой в реализации и должна обеспечивать быстрый поиск / вставку. Приблизительный поиск с использованием Дамерау-Левенштейна также должен быть прост в реализации. Но это не выглядит очень эффективным с точки зрения сложности пространства, так как у вас, скорее всего, много накладных расходов при хранении указателей.

Патриция Три

Trie-500px

Кажется, это занимает меньше места, чем обычный Trie, поскольку вы в основном избегаете затрат на хранение указателей, но меня немного беспокоит фрагментация данных в случае очень больших словарей, таких как у меня.

Суффикс Дерево

Суффикс-500px

Я не уверен в этом, кажется, что некоторые люди находят его полезным для анализа текста, но я не совсем уверен, что он даст с точки зрения производительности для проверки орфографии.

Троичное дерево поиска

TST

Они выглядят довольно красиво и по сложности должны быть близки (лучше?) К Патрисии Трис, но я не уверен насчет фрагментации, если это будет лучше, чем Патрисия Трис.

Взрыв дерево

взрыв

Это кажется своего рода гибридом, и я не уверен, какое преимущество оно даст по сравнению с Tries и тому подобным, но я несколько раз читал, что это очень эффективно для интеллектуального анализа текста.


Я хотел бы получить некоторую обратную связь относительно того, какую структуру данных лучше всего использовать в этом контексте и что делает ее лучше, чем другие. Если мне не хватает некоторых структур данных, которые были бы еще более подходящими для проверки орфографии, я тоже очень заинтересовался бы.

Чарльз Менгу
источник
Как Patricia Trie избегает затрат на хранение указателей? Это просто en.wikipedia.org/wiki/Radix_tree ? Если это так, то я думаю, что он по-прежнему хранит много указателей, но у вас будет огромная экономия места, потому что общие префиксы сохраняются только один раз
Joe
n
1
@linker: Вы перепробовали все варианты для своего словаря? Учитывая фиксированный вариант использования, это, вероятно, самый быстрый способ выяснить, какая структура данных занимает сколько места.
Рафаэль
1
Это просто основной словарь, просто известный список правильно написанных слов.
Чарльз Менгуй
1
Смотрите также этот наиболее тесно связанный вопрос .
Рафаэль

Ответы:

4

Я столкнулся с той же проблемой, но использовал другой подход. Вы можете создать какую-то функцию «хэш», которая для аналогичного слова будет давать одинаковое или близкое число.

Проблема в том, что та функция, которая даст «хороший» результат для слов со вставкой / удалением, даст «плохой» для перехода, и наоборот. Пример: сопоставить буквы цифрам, аналогичные буквы соседним цифрам и просто сложить их для каждой буквы в слове. Затем создайте хеш-таблицы с наборами для каждого ключа и найдите пересечение для слова.

Может быть, некоторые результаты могут быть достигнуты, если мы посмотрим на «пространство» слов. X для изменения буквы, Y для добавления / удаления, Z для перехода или что-то в этом роде.

Однако это только абстрактные идеи, у меня недостаточно времени для их реализации.

MadRunner
источник
Это то, что делает Soundex en.wikipedia.org/wiki/Soundex
rgrig
4

O(log(n))O

Не храните строки в метрическом дереве. Просто сохраните индекс и сохраните строки в дереве Патриции.

Я не уверен, какое дерево вы должны использовать. Это будет зависеть от ваших данных и ваших требований (вам нужна быстрая вставка?). Обновите свой вопрос, если вы обнаружите, что одно дерево более эффективно, чем другие.

Вы также можете посмотреть на специализированные инструменты, такие как люцен.

оао
источник