Создание «проверки орфографии», которая проверяет базу данных с разумным временем выполнения

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

К сожалению, вычисление расстояния Левенштейна довольно дорого, и вы будете делать это много, если будете использовать BK-дерево с большим словарем. Для лучшей производительности, вы можете рассмотреть 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.

Answer 3

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

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

• 1 вставка (208)
  • пример
  • пример
  • cexample
  • ...
  • examplex
  • exampley
  • examplez
• 1 удаление (7)
  • xample
  • пример
  • пример
  • ...
  • пример
• 1 замена(182)
  • axample
  • bxample
  • cxample
  • ...
  • examplz

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

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

• 1 вставка (8)
  • ? Пример
  • e? Xample
  • например? Достаточно
  • например
  • экзамен?
  • экзамен? le
  • пример? e
  • пример?
• 1 делеция (7)
  • xample
  • пример
  • пример
  • пример
  • пример
  • экзамен
  • пример
• 1 замена (7)
  • ? Xample
  • e? Достаточно
  • ex? Mple
  • например
  • экзамен? Le
  • examp? E
  • 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 заменой

См. Также: Как работает алгоритм Google «Вы имели в виду?»?

Answer 4

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

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

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

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

Итак, предположим, что в вашей базе данных есть слово "яблоко"

Итак, в словаре «а» вы добавляете слово «яблоко»

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

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

в словаре «е»: вы добавляете слово «яблоко»

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

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

скажем, aplse

вы начинаете с "а" и получаете все слова в "а"

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

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

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

в итоге у вас будет просто набор слов, состоящих из алфавитов "a", "p", "l", "s", "e"

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

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

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

Итак, что-то вроде начала с * klse (пересечение слов k, l, s, e) num (слова возвращены) = k1

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

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

Есть много сложных алгоритмов, построенных поверх этого ..

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

Answer 5

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

Взгляните на BK-Trees

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

Answer 6

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

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

Либо

• Есть ли совпадение на заднем конце и возвращайте только те результаты, которые вам нужны.

или

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