Создание "проверки орфографии", которая проверяет базу данных с разумной продолжительностью выполнения

Я не прошу о внедрении самого алгоритма проверки орфографии. У меня есть база данных, содержащая сотни тысяч записей. То, что я хочу сделать, это проверить ввод пользователя в определенный столбец в таблице для всех этих записей и вернуть любые совпадения с определенным расстоянием для хамминга (опять же, этот вопрос не касается определения расстояния для хамминга и т.д.). Целью, конечно же, является создание функции "вы имели в виду", когда пользователь ищет имя, и если в базе данных нет прямых совпадений, возвращается список возможных совпадений.

Я пытаюсь придумать способ выполнить все эти проверки в наиболее разумной версии. Как я могу проверить вход пользователя во все эти записи наиболее эффективным способом?

Функция в настоящее время реализована, но время выполнения чрезвычайно медленное. Теперь он теперь загружает все записи из таблицы (или таблиц), указанной пользователем, в память, а затем выполняет проверку.

Для чего это стоит, я использую NHibernate для доступа к данным.

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

Ответ 1

Расчет расстояния Левенштейна не должен быть таким дорогостоящим, как вы думаете. Код в статье Norvig можно рассматривать как psuedocode, чтобы помочь читателю понять алгоритм. Гораздо более эффективная реализация (в моем случае примерно в 300 раз быстрее при наборе данных в 20 000 семплов) - это trie. Разница в производительности в основном объясняется устранением необходимости выделять миллионы строк для того, чтобы выполнять поиск в словарях, тратить гораздо меньше времени на GC, а также улучшать локальность ссылок, чтобы иметь меньше промахов в кэше процессора. При таком подходе я могу выполнять поиск примерно на 2 мс на моем веб-сервере. Дополнительный бонус - это возможность легко вернуть все результаты, начинающиеся с предоставленной строки.

Недостатком является то, что создание trie происходит медленно (может занимать секунду или около того), поэтому, если исходные данные изменяются регулярно, вам нужно решить, нужно ли перестраивать все это или применять дельта. Во всяком случае, вы захотите повторно использовать структуру как можно больше после ее создания.

Ответ 2

Как сказала Даркара, BK-Tree - хороший первый прием. Их очень легко реализовать. Существует несколько бесплатных реализаций, которые легко найти через Google, но лучшее введение в алгоритм можно найти здесь: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees.

К сожалению, вычисление расстояния Левенштейна довольно дорого, и вы будете делать это много, если используете BK-Tree с большим словарем. Для лучшей производительности вы можете рассмотреть Levenshtein Automata. Немного сложнее реализовать, но и более эффективно, и они могут быть использованы для решения вашей проблемы. Тот же самый потрясающий блоггер имеет подробности: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata. Эта статья также может быть интересной: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652.

Ответ 3

Я думаю, что расстояние Левенштейна более полезно здесь, чем Расстояние Хэмминга.

Возьмем пример: возьмем слово example и ограничимся расстоянием Левенштейна от 1. Затем мы можем перечислить все возможные орфографические ошибки:

1 вставка (208)
- aexample
- bexample
- CExample
- ...
- examplex
- exampley
- examplez
1 удаление (7)
- Xample
- eample
- exmple
- ...
- exampl
1 замена (182)
- axample
- bxample
- cxample
- ...
- examplz

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

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

1 вставка (8)
- ? Пример
- е? Xample
- ех? Обилен
- экса? Mple
- экзамен? PLE
- examp? Ль
- exampl? Е
- Пример?
1 удаление (7)
- Xample
- eample
- exmple
- exaple
- нелогич-
- exampe
- exampl
1 подстановка (7)
- ? Xample
- е? Обилен
- ех? Mple
- экса? PLE
- экзамен? Ль
- examp? Е
- exampl?

Это выглядит вполне управляемым. Вы можете создать все эти "подсказки" для каждого слова и сохранить их в базе данных. Когда пользователь вводит слово, генерируйте из него все "подсказки" и запросите базу данных.

Пример: пользователь вводит exaple (уведомление отсутствует m).

SELECT DISTINCT word
           FROM dictionary
          WHERE hint = '?exaple'
             OR hint = 'e?xaple'
             OR hint = 'ex?aple'
             OR hint = 'exa?ple'
             OR hint = 'exap?le'
             OR hint = 'exapl?e'
             OR hint = 'exaple?'
             OR hint = 'xaple'
             OR hint = 'eaple'
             OR hint = 'exple'
             OR hint = 'exale'
             OR hint = 'exape'
             OR hint = 'exapl'
             OR hint = '?xaple'
             OR hint = 'e?aple'
             OR hint = 'ex?ple'
             OR hint = 'exa?le'
             OR hint = 'exap?e'
             OR hint = 'exapl?'

exaple с 1 вставкой == exa?ple == example с 1 заменой

Ответ 4

он загружает все записи из пользовательской таблицы (или таблиц) в память и затем выполняет проверку

не делайте этого

Либо

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

или

Сбросить записи в память раньше на захват рабочего удара и сделать проверьте, когда вам это нужно.

Ответ 5

Вам нужно будет структурировать свои данные по-другому, чем база данных. Создайте собственное дерево поиска со всеми необходимыми данными словаря на клиенте. Хотя память может стать проблемой, если словарь чрезвычайно велик, поиск будет очень быстрым. O (nlogn), если я правильно помню.

Посмотрите BK-Trees

Кроме того, вместо использования расстояния Хэмминга рассмотрим расстояние Левенштейна

Ответ 6

Ответ, который вы отметили как правильно.

Note: when i say dictionary.. in this post, i mean hash map .. map.. 
 basically i mean a python dictionary

Еще один способ повысить свою производительность, создав инвертированный индекс слов.

Вместо того, чтобы вычислять расстояние редактирования против целого db, вы создаете 26 словарей. У каждого есть ключ алфавита. поэтому английский язык имеет 26 алфавитов.. поэтому клавиши "a" , "b".. "z"

Итак, предположим, что у вас есть слово в вашем db "apple"

Итак, в словаре "a" : вы добавляете слово "яблоко"

в словаре "p" : вы добавляете слово "яблоко"

в словаре "l": вы добавляете слово "яблоко"

в словаре "e": вы добавляете слово "яблоко"

Итак, сделайте это для всех слов в словаре.

Теперь, когда вводится слово с ошибкой.

позволяет сказать aplse

вы начинаете с "a" и возвращаете все слова в "a"

тогда вы начинаете с "p" и находите пересечение слов между "a" и "p"

тогда вы начинаете с "l" и находите пересечение слов между "a" , "p" и "l"

и вы делаете это для всех алфавитов.

в конце концов у вас будет только куча слов, которые сделаны из алфавитов "a" , "p" , "l", "s", "e"

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

теперь может быть случай, когда ничего не может быть возвращено.

так что-то вроде "aklse".. есть хороший шанс, что нет слова, которое сделано из этих алфавитов. В этом случае вам нужно будет начать отмену вышеуказанного шага до стадии, когда у вас осталось конечное число слов.

Так что, например, начинайте с * klse (пересечение между словами k, l, s, e) num (слова вернулись) = k1

то a * lse (пересечение слов a, l, s, e)... numwords = k2

и т.д.. выберите тот, у которого есть более высокое количество слов, возвращенных.. в этом случае на самом деле нет ни одного ответа.. поскольку многие слова могут иметь такое же расстояние редактирования. Вы можете просто сказать, что если значение editdistance больше, чем "k", тогда нет хорошего совпадения...

Существует множество сложных алгоритмов, построенных поверх этого.

как и после этих многих шагов, используйте статистические выводы (вероятность слова "яблоко" , когда ввод "aplse".. и т.д.). Затем вы начинаете путь машинного обучения:)