Блог

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

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

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

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

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

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

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

Самое простое, что я бы попробовал, это начать с вашего слова и выполнить поиск по всем возможным наборам модификаций, пока вы не найдете ближайшее слово в вашем словаре. Требуется модифицированный поиск по ширине. Сохранить (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
  

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

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