Нахождение самой похожей строки среди множества миллионов строк

Question

Допустим, у меня есть словарь (список слов) из миллионов на миллионы слов.Учитывая слово запроса, я хочу найти слово из этого огромного списка, которое наиболее похоже.

Итак, допустим, мой запрос elepant, тогда результат, скорее всего, будет elephant.

Если мое слово fentist, результат, вероятно, будет dentist.

Конечно, при условии, что в моем исходном списке слов присутствуют elephant и dentist.

* 1014Какой тип индекса, структуры данных или алгоритма я могу использовать для быстрого выполнения запроса?Надеюсь, сложность O(log N).

Что у меня есть: Самое наивное, что нужно сделать, - это создать «функцию расстояния» (которая вычисляет «расстояние» между двумя словами в терминахнасколько они различны), а затем в O (n) сравните запрос с каждым словом в списке и верните слово с ближайшим расстоянием.Но я бы не стал этим пользоваться, потому что он медленный.

Answer 1

Вы описываете проблему Поиск ближайшего соседа (NNS) .Существует два основных метода решения задач NNS: точное и приблизительное .

Если вам нужно точное решение, я бы порекомендовал метрическое дерево , например, M-дерево , MVP-дерево и BK-дерево .Эти деревья используют неравенство треугольника для ускорения поиска.

Если вы готовы принять приблизительное решение, есть гораздо более быстрые алгоритмы.Современное состояние приближенных методов: Иерархический навигационный маленький мир (hnsw) . Nonmetric Space Library (nmslib) обеспечивает эффективную реализацию hnsw, а также несколько других приближенных методов NNS.

(Вы можете вычислить расстояние Левенштейна с помощью алгоритма Хиршберга )

Answer 2

Я сделал аналогичный алгоритм некоторое время назад

Идея состоит в том, чтобы иметь массив char [255] с символами и значениями - это список хэшей слов (идентификаторов слов), который содержит этот символ

При поиске «delete ....» search (d) выдаст пустой список search (e) найдет все с символом e, включая слона (два раза, поскольку у него два «e»), поиск (l) принесетВы новый список, и вам нужно объединить этот список с результатами предыдущего шага

... в конце ввода у вас будет список, затем вы можете попытаться сделать группу по wordHash и упорядочить по desc by count

Также интересная вещь: если в вашем вводе отсутствует один или несколько символов, вы просто получите пустой список в середине поиска, и это не повлияет на эту идею

Мой первоначальный алгоритм был безупорядочение, и я хранил для каждого символа wordId и lineNumber и char позицию.Моя главная проблема заключалась в том, что я хочу найти с помощью ee, чтобы найти 'elephant' с eleant, чтобы найти 'elephant' с antph, чтобы найти 'elephant'. Каждое слово на самом деле было строкой из файла, поэтому оно часто было очень длиннымСтроки были большими, я хотел быстрый поиск каталогов с текстовыми файлами размером более 1 ГБ. Поэтому было даже сложно сохранить их в памяти, для этой идеи вам нужна функция из 3 частей, чтобы заполнить вашу кеш-функцию для поиска по символу от функции ввода до фильтра и, возможно,результаты упорядочения (я не использовал упорядочение, поскольку пытался заполнить кэш в том же порядке, в котором я читал файл, и я хотел поместить строки, содержащие входные данные, в том же порядке сверху)

Я надеюсьэто имеет смысл