Поиск ближайшего соседа в метрике Левенштейна - PullRequest
Новая
       6

Поиск ближайшего соседа в метрике Левенштейна

2 голосов
/ 26 апреля 2011

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

Я использую обобщение расстояния Левенштейна в качестве метрики - причина, по которой мне нужно было обобщить, заключается в том, что мне нужны конкретные «затраты» на обмен двух данных букв - например, мне нужен обмен «а»с 'b', чтобы стоить меньше от обмена 'a' с 'c'.Я думаю, мне все еще нужно убедить себя, что мое обобщение все еще является метрикой.

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

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

Имея это в виду, я хотел бы услышать несколько советов относительно того, какие алгоритмы искать.

1 Ответ

1 голос
/ 26 апреля 2011

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

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

Самое простое, что я бы попробовал, - это начать с вашего слова и искать во всех возможных наборах модификаций, пока не найдете наиболее близкое слово в вашем словаре. Вы хотите изменить поиск в ширину. Сохраните (0, your_word) как единственную запись в некотором виде http://en.wikipedia.org/wiki/Priority_queue (куча проста в реализации), выберите расстояние до случайного словарного слова в качестве вашего текущего лучшего решения и затем до тех пор, пока приоритетная очередь не будет пусто: 

Take the lowest cost element out.
If it is more expensive than your best solution:
    stop, return your best.
For each possible one step modification of that word:
    if the new word is in the dictionary and is lower cost than your best:
        improve best estimate
    else:
        store (new_cost, new_word) in the priority queue

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

Это может быть далеко не оптимальное решение, но его не должно быть слишком сложно программировать и пробовать.

...