В институтах всех нас учат сравнивать две строки по принципу равны/не равны и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки?
Расстояние Левенштейна определяет, сколько раз надо добавить/удалить/заменить символ, чтобы одну строку превратить в другую. Например, расстояние между словами kitten и sitting равно трем. Этот, и похожие алгоритмы используется в спеллчекерах, при распознавании текста, да и много еще где.
Алгоритм подсчета расстояния Левенштейна описан в Википедии, с псевдокодом. Есть на русском.
Еще одно описание алгоритма, с ява-апплетом, который умеет считать расстояние Левенштейна.
Вообще этих расстояний много разных, по вышеприведенным ссылкам найдете. Например есть расстояние Дамерау — Левенштейна, чуть посложнее, в него добавляется перестановка.
(Пост опубликован в рамках недели борьбы с велосипедизмом)
понедельник, июля 26, 2010
Расстояние Левенштейна
Подписаться на:
Комментарии к сообщению (Atom)
Atom feed
17 коммент.:
при упоминании строковых алгоритмов, в первую очередь надо давать ссылку на <a href="http://www.ozon.ru/context/detail/id/1393109/>книгу Гасфилда</a> ;-)
добавить/удалить/заменить
hr0nix
добавить/удалить/заменить
угу...
В питоне можно не шибко эффективно, но достаточно быстро для создания более удобного интерфейса считать похожее расстояние как
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" не проходят.
_winnie, для Питона есть реализованный http://pypi.python.org/pypi/python-Levenshtein/ (он на Си, к слову)
_winnie
PS. А как в комментах форматироавать код? теги code, pre, font face="monospace" не проходят.
никак :-(
При всей банальности может кому-то и мои слайды пригодятся
(набросал быстро для разбора задачи студентам)
Спасибо, Алена!
Вы очень правильно заметили, что "Но если не знаешь, что именно искать, то можно так никогда и не найти."
Я однажды видел реализацию Расстояния Левенштейна в одной из open-source программ для поиска похожих изображений. Работал он там, если честно, отвратительно :)
Лучшим вариантом было бы использование Color Coherence Vector (http://www.google.com.ua/search?q=color+coherence+vector) или чего подобного.
Если знаете что-то об алгоритмах сравнения изображений, напишите, пожалуйста.
Есть хороший обзор алгоритмов на строках, хоть и датирован 90-ми.
http://mklug.linux.kiev.ua/pub/docs/developer/algo/Stephen-92/index.html
На олимпиадах по программированию такие алгоритмы каждый средний кодер за 20 минут придумывает. По своему опыту говорю, буквально пару месяцев назад встретил задачу в точности по нахождению расстояния Левенштейна. Правда я до сегодняшнего дня не знал что оно так называется, что не помешало мне тогда успешно сдать задачу :)
Мораль: занимайтесь спортивным программированием
Я в свое время изучал этот вопрос в рамках задачи коррекции адреса при его ошибочном наборе. Алгоритм Левенштейна для этого хорошо подходит.
Кому интересно: http://blog.salikhovilyas.ru/2009/11/07/url-correction/.
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
Самое плохое в расстоянии Левенштейна - медленно оно считается... Если большой текст, вообще становится узким местом.
Отправить комментарий