понедельник, июля 26, 2010

Расстояние Левенштейна

В институтах всех нас учат сравнивать две строки по принципу равны/не равны и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки?

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

Алгоритм подсчета расстояния Левенштейна описан в Википедии, с псевдокодом. Есть на русском.

Еще одно описание алгоритма, с ява-апплетом, который умеет считать расстояние Левенштейна.

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

(Пост опубликован в рамках недели борьбы с велосипедизмом)

17 коммент.:

Alex Ott комментирует...

при упоминании строковых алгоритмов, в первую очередь надо давать ссылку на <a href="http://www.ozon.ru/context/detail/id/1393109/>книгу Гасфилда</a> ;-)

hr0nix комментирует...

добавить/удалить/заменить

Alena комментирует...

hr0nix

добавить/удалить/заменить

угу...

_winnie комментирует...

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


import difflib
def ScoreMatch(a, b):
    diffs = [c[0] for c in difflib.ndiff(a, b)]
    return diffs.count('-') + diffs.count('+')


Или достать из спелл-чек словаря близкие слова как difflib.get_close_matches("appel", ["ape", "apple", "peach", "puppy"])

PS. А как в комментах форматироавать код? теги code, pre, font face="monospace" не проходят.

isagalaev комментирует...

_winnie, для Питона есть реализованный http://pypi.python.org/pypi/python-Levenshtein/ (он на Си, к слову)

Alena комментирует...

_winnie
PS. А как в комментах форматироавать код? теги code, pre, font face="monospace" не проходят.

никак :-(

Stas Fomin комментирует...

При всей банальности может кому-то и мои слайды пригодятся
(набросал быстро для разбора задачи студентам)

Mykolad комментирует...

Спасибо, Алена!

Вы очень правильно заметили, что "Но если не знаешь, что именно искать, то можно так никогда и не найти."

Я однажды видел реализацию Расстояния Левенштейна в одной из open-source программ для поиска похожих изображений. Работал он там, если честно, отвратительно :)

Лучшим вариантом было бы использование Color Coherence Vector (http://www.google.com.ua/search?q=color+coherence+vector) или чего подобного.

Если знаете что-то об алгоритмах сравнения изображений, напишите, пожалуйста.

jSunny комментирует...

Есть хороший обзор алгоритмов на строках, хоть и датирован 90-ми.
http://mklug.linux.kiev.ua/pub/docs/developer/algo/Stephen-92/index.html

Quick комментирует...

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

Мораль: занимайтесь спортивным программированием

muxx комментирует...

Я в свое время изучал этот вопрос в рамках задачи коррекции адреса при его ошибочном наборе. Алгоритм Левенштейна для этого хорошо подходит.

Кому интересно: http://blog.salikhovilyas.ru/2009/11/07/url-correction/.

Alena комментирует...

Quick
Правда я до сегодняшнего дня не знал что оно так называется, что не помешало мне тогда успешно сдать задачу :)

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

Quick комментирует...

Alena
Это далеко не развлечение. Опыт с олимпиад можно и нужно использовать в реальном программировании. Это хорошо, что такую простую динамическую задачу решили до вас и вы знаете где про это прочитать. А если условия немного изменятся? Важно иметь способность придумывать решения большого класса задач, как раз олимпиады развивают такой скилл.

Анонимный комментирует...

Вообще говоря, олимпиадники с первого года обычно уже знают, что это, и расстояние левенштейна (редакторское расстояние) является стандартным примером в большинстве лекций, да и просто материалов в дп. Что касается серьёзных проектов, людей, проявившихся в олимпиадах по программированию, за милую душу берут в Google/Yandex/ABBYY/… или может быть это несерьёзные проекты, или их олимпиадный опыт не имеет значения? Весь состав vkontakte — олимпиадники, надо заметить, что при критическом для абсолютного большинства крупных проектов кол-ве серверов, он работает невероятно быстро (в частности заслуга А.С.Лопатина, тренирующего олимпиадников в спб, и сам бывший олимпиадник), самое забавное, что как бы красиво и круто не писали в других проектах, их это не спасёт, потому что вся фишка того же ускорения запросов над сообщениями — структура данных, которую (о ужас!) не найдёшь ни в учебнике, ни в статейке или тем более форуме, потому что она попросту придумана командой вконтакте.
Каков вывод? Ботать спортивное программирование, теоркат (ВНЕЗАПНО) и С++ :)

Анонимный комментирует...

http://www.keldysh.ru/departments/dpt_10/lev.html

Вот он=)

Анонимный комментирует...

А вот и на всех языках - полезно.

http://ru.wikibooks.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.9B.D0.B5.D0.B2.D0.B5.D0.BD.D1.88.D1.82.D0.B5.D0.B9.D0.BD.D0.B0_.D0.BD.D0.B0_.D1.8F.D0.B7.D1.8B.D0.BA.D0.B5_Java

Ilya Zvyagin комментирует...

Самое плохое в расстоянии Левенштейна - медленно оно считается... Если большой текст, вообще становится узким местом.