Comments 17
Мне приходилось решать задачи с вычислением расстояний Левенштейна. Только модифицированными. Значения весов перестановки, вставки, замены и удаления были различными в зависимости от задач.
В чем рисовали таблицы, в Экселе?
Если у нас в тексте есть слово с ошибкой и словарь на 10 тыс слов. Как найти, какое слово из словаря ближе всего к слову с ошибкой? Вычислять расстояние Левенштейна 10 тыс раз? Или есть способы оптимизации?
Могут подойти n-граммные индексы.
Если словарь упорядочен, то в первую очередь искать по нужной букве, а это значительно меньше 10 тыс. вычислений. Ну и всё зависит от того, какая ошибка. Если предполагаем, что ошибка одна или две, то можно предварительно отсеивать слова из словаря по длине.
Можно например для словаря (фиксированного) построить префиксное и суффиксное деревья, и для конкретного слова находить пересечение множеств слов из словаря с совпадающими суффиксами и префиксами наибольшей длины. После чего найти в этом множестве ближайшее слово перебором, а затем проверить нет ли в оставшихся словах вариантов с меньшим расстоянием (отсекая вычисление расстояния, если оно заведомо больше уже текущего оптимального). Будет в разы быстрее (особенно на словах с ошибкой в середине). Но такой подход все еще линейно зависит от размера словаря и сильно подтармаживает, если в слове есть 2 ошибки: в начале и конце (что впрочем нечасто встречается).
Можно еще попробовать нечеткий вариант: сделать отображение из слова в вектор такое, что расстояние между векторами сильно коррелирует с растоянием Левенштейна (например сетку обучить предсказывать эти расстояния как скалярное произведение эмбеддингов слов). Затем использовать классические методы поиска ближайшего соседа — flann trees или faiss. Такой метод будет очень быстр (порядка O(log N) времени где N — число слов в словаре). Но с какой-то вероятностью будет возвращать не самое близкое слово.
Используйте бинарный поиск. Пока что это наилучший способ для решения подобных задач
Я бы попробовал поменять все буквы слова на все возможные символы и сделать для каждого варианта запрос в словарь на полное совпадение.
Если работаем с кириллицей, то это 32 * L запросов в словарь на полное совпадение, где L - длина слова (почти всегда будет не более 15). Интуитивно кажется, что даже однократное вычисление расстояния Левенштейна для двух слов будет в среднем несколько дольше, чем такой перебор.
P.s. Это работает только для 1 ошибки, для исправления двух ошибок лучше использовать какой-нибудь более сложный способ
По сути, это минимальное число односимвольных преобразований (удаления, вставки или замены), необходимых, чтобы превратить одну последовательность в другую.
Вообще-то не совсем так. Расстояние Левенштейна не обязательно должно быть целым числом количества преобразований, потому что расстояние Левенштейна считает не количество преобразований, а их суммарную сложность.
Например, нам надо найти в словаре слово, наиболее похожее на заданное. На входе слово "трапа", в словаре есть "трава" и "тропа". Если считать просто по символам, то оба слова отличаются на один символ, то есть одинаково похожи. Но замена "а" на "о" - частая ошибка, поэтому её стоит считать с меньшим весом, чем нетипичная ошибка замены "п" на "в", тогда от "трапа" до "тропа" получится меньше расстояние Левенштейна, чем до "трава". То есть "тропа" - более похожее слово.
Аналогично можно учитывать ошибки при вводе, когда нажимаются соседние буквы на клавиатуре или на разной раскладке. То есть между заменой "d" на "в" куда меньше расстояние, чем между заменой "d" на "i".
Дополняйте словарь, может это трап или рапа.
По-моему, это уже не к Расстоянию Левенштейна вопросы. Это просто алгоритм поиска различия в строках. Для него "трава" с "тропа" всё равно, что "cei8h0" c "9uvq2h".
Это уже задача конкретной реализации под свой контекст добавить дополнительные плюшки. И заранее нужно понимать, что все их невозможно и даже вредно добавлять. Если я пишу росчерком на телефоне - для меня не работают правила клавиатуры (точнее, работают не все), и наоборот. Если я пишу на английском, замена "а" на "о" тоже не про меня. А уж если я ещё и какую-то другую раскладку использую, а не стандартную ЙЦУК...
Посмотрите раздел "Разные цены операций" в статье "Расстояние Левенштейна".
То есть да, я ошибся в том, что именно расстояние Левенштейна считает все замены символов одинаковыми. Тем не менее в практическом применении желательно учитывать различную цену между парами символов.
Огромное спасибо за статью!
Возник вопрос. В статье описывается обработка слов, где заведомо изменены буквы на одинаковых позициях. Но как это работает на том же КОТИК и СКОТИНА? Ведь если их просто поставить рядом, то там расстояние не 3, а все 7 будет, потому что на одних и тех же позициях стоят разные буквы, а секрет схожести заключается в смещении на одну позицию. Как расчёт работает в этом случае? Вначале ищет схожие области?
А если усложнить задачу? Взять, например, АБВгдеЖЗИК и ъАБВъЖЗИК. Тут есть и смещения, и несколько одинаковых областей, причём, более похожая область находится в конце, т.е. если просто механически найти первую похожую область, то вычисленное расстояние с таким одиночным смещением будет меньше, чем если взять вторую область или, тем более, учесть обе области.
Расстояние Левенштейна для чайников