Вычисление расстояния Левенштейна быстро

24

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

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

Интересно, есть ли более эффективное решение этой проблемы? Может быть, какая-то эвристика, которая позволяет нам сократить количество слов для поиска или оптимизации алгоритма расстояния Левенштейна.

Ссылки на статьи по теме приветствуются.

Джошуа Герман
источник

Ответы:

16

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

Расстояние редактирования несколько неприятно для построения структур поиска ближнего. Основная проблема заключается в том , что в качестве метрики, она ведет себя ( своего рода) , как и другие хорошо известные плохие показатели , как с целью уменьшения размерности и приближения. По этой теме можно прочитать довольно обширную работу, и вашим лучшим источником является набор работ Алекса Андони : следуя указателям в обратном направлении (например, из его статьи FOCS 2010), вы получите хороший набор источников.1

Суреш Венкат
источник
1
Все, что я знаю о метрических пространствах, - это семантика, поэтому вопрос: существуют ли приличные (при любом значении приличных) вложения метрики Левенштейна в ультраметрию? Это может привести к появлению алгоритма двоичного дерева.
Нил Кришнасвами
Я не совсем уверен. Я подозреваю, что ответ "нет" в целом, но мне не на что указывать.
Суреш Венкат
Вторая статья на boytsov.info/pubs - это хороший обзор возможных решений для поиска соседей при расстоянии редактирования Левенштейна и Дамеро-Левенштейна.
a3nm
@NeelKrishnaswami Вложение в ультраметрическое будет иметь искажения по крайней мере где d - длина строки. Это следует из нижней границы искажения для встраивания в L 1 из-за Krauthgamer и Rabani , поскольку ультраметрики встраиваются изометрически в евклидово пространство, которое изометрически встраивается в L 1 . Ω(logd)dL1L1
Сашо Николов
5

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

В общем, лучше взглянуть на это с другой стороны: у вас есть индекс всех слов в словаре. Теперь для входного слова w, если оно есть в словаре, остановитесь. В противном случае создайте все варианты на расстоянии 1 и найдите их. Если их там нет, поищите варианты на расстоянии 2 и так далее ...

Есть несколько улучшений этой основной идеи.

luispedro
источник
1
Вы должны были включить ссылку на ваш воспроизводимый архив исследований для статьи .
Дэн Д.
4

Простое решение - хранить слова как три. Затем вы можете вычислить расстояние Левенштейна слова запроса по отношению к три с помощью стандартного алгоритма динамического программирования, вместо того, чтобы вычислять его по каждому слову в отдельности. В худшем случае временная сложность не улучшается асимптотически, но если сначала развернуть наиболее многообещающие ветви, вы получите что-то вроде времени для длины запроса m , размера алфавита σO(mk+1σk)mσk

Джуни Сирен
источник
4

Я написал ответ на очень похожий вопрос на cs.stackexchange.com ( /cs//a/2096/1490 ), а затем нашел этот вопрос. Ответ есть для приблизительного поиска ближайшего соседа на расстоянии редактирования (т. Е. Алгоритм выводит строку, которая примерно так же близка к строке запроса, как и ближайший сосед строки запроса). Я публикую здесь, так как я не нахожу никаких ссылок, которые я дал там в ответах, приведенных здесь.

Сашо Николов
источник
3

Я думаю, что вам нужен алгоритм Вагнера-Фишера: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm Основная идея заключается в том, что, поскольку словарь, через который вы проходите, отсортирован, два слова подряд очень вероятно, что у них будет длинный префикс, поэтому вам не нужно обновлять всю матрицу для каждого расчета расстояния.

Бьорн Линдквист
источник
2

Вы можете использовать Вы имели в виду?

А затем найдите расстояние Левенштейна между ответом, возвращаемым «Вы имели в виду» »и строкой ввода, используя динамическое программирование.

Пратик Деогхаре
источник
Я не понимаю этот ответ. Вопрос состоит в том, как эффективно найти слово в большом словаре с близким расстоянием Левенштейна к заданному входу, а не о том, как вычислить расстояние Левенштейна или о сравнении с результатами проверки правописания черного ящика ...
Гек Беннетт
@ Хак Беннетт: Я думал, что @ Григорий Джавадян строит Did you mean?особенность. Кроме того, Did you mean?возвращает слово, которое очень близко к заданному входу и делает это довольно эффективно. :)
Pratik Deoghare
Я думаю, что ваши идеи хороши, но кажется, что Григорий просит что-то более глубокое и конкретное.
Гек Беннетт
@Хак Беннетт: Да, вы правы! :)
Pratik Deoghare
-1

Одним из способов является обучение модели машинного обучения для сопоставления слов с векторами и сопоставления расстояния Левенштейна с евклидовым расстоянием. Затем вы можете построить KDTree из векторов для словаря, который вы хотите использовать. Я создал блокнот Jupyter, который делает это здесь: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

Согласно комментариям DW:

  1. процедура обучения = стохастический градиентный спуск с адаптивными градиентами
  2. функция потерь = средняя квадратическая ошибка между истинным редактируемым расстоянием и евклидовым расстоянием
  3. обучающие данные = случайные строки длиной от 1 до 32 символов (могут быть улучшены с данными, которые соответствуют фактическому распределению общих опечаток)
  4. количественные результаты: после обучения примерно 150 эпох с размером партии 2048 (время стены = приблизительно одна минута) с использованием вложения слов 512 измерений с одним скрытым слоем средняя абсолютная ошибка между истинным расстоянием редактирования и прогнозируемым расстоянием редактирования находится на отметке 0,75, что означает, что прогнозируемое расстояние редактирования составляет примерно один символ

Краткое описание структуры модели:

  1. Создайте заученное вложение для каждого символа, включая нулевой символ (используется позже для правого отступа текста под лимитом символов)
  2. Заполните правую часть текста нулевым символом, пока он не достигнет предела (32)
  3. Объединить эти вложения
  4. Выполните вложения через нейронную сеть с прямой связью, чтобы получить вложение слова меньшего размера (512-мерное)
  5. Сделайте это для обоих слов
  6. Найти евклидово расстояние между векторами
  7. Установите потерю равной среднеквадратической ошибке между истинным расстоянием Левенштейна и евклидовым расстоянием.

Мои тренировочные данные - это просто случайные строки, но я думаю, что результаты могли бы действительно улучшиться, если бы тренировочные данные были (опечатка / правильное слово) парами. Я просто использовал, /usr/share/dict/wordsпотому что он общедоступен.

michaelsnowden
источник
2
Как вы тренируете модель ML, чтобы слова, находящиеся рядом в Левенштейне, отображали одинаковые векторы? Какую процедуру тренировки и функцию потери вы используете для этого? Можете ли вы обобщить метод в своем ответе, чтобы ответ по-прежнему был полезен, даже если ссылка перестала работать, и чтобы нам не приходилось копаться в вашей записной книжке, чтобы понять метод, который вы используете? Кроме того, вы можете оценить, насколько хорошо это работает в количественном отношении? Это лучше, чем альтернативы?
DW
В нынешнем виде это (я думаю) плохо подходит для CSTheory. То есть, нет представления о том, что конкретно предлагается, и нет теоретического обоснования для этого.
Клемент С.
@DW К сожалению об этом - я сделал довольно существенное редактирование, которое должно быть исчерпывающим, если ссылка не работает (или если вы не хотите перелистывать блокнот). Хотя на самом деле это не теория КС, потому что это не исследование, я думаю, что это практический подход, потому что он быстрый и легкий как для обучения, так и для вывода.
michaelsnowden
1
Вы тренируетесь на случайных строках. Ожидаемое расстояние Левенштейна между двумя такими струнами будет приблизительно равным длине более длинной струны. Таким образом, очень легко оценить это расстояние на случайных строках, но это бесполезно для работы с реальными данными. Я подозреваю, что ваши вложения могут просто кодировать длину строки, и, таким образом, вы, возможно, создали причудливый способ сделать что-то тривиальное и бесполезное. Это проблема с использованием ML; он очень чувствителен к используемой вами функции потери.
DW
@DW Если вы посмотрите на результаты в записной книжке, то поиск закончился тем, что выдает приличные результаты, а не только строки одинаковой длины. Я бы очень посоветовал вам снять это. Я бы не назвал это тривиальным и бесполезным.
michaelsnowden