LINUX.ORG.RU
решено Форум — Development  

Как вычислить расстояние между строками (степень схожести)

 , ,


1

3

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

Для «устаканивания» понятий: строка здесь — цепочка utf-8 символов конечной длинны. Массив известных строк — некая итерируемая коллекция (возможно неограниченного размера).

Возникают вопросы:

  • Какими критериями пользоваться для вычисления расстояния между искаемой и исходными строками?
  • Какую структуру данных для коллекции лучше всего выбрать?
  • Существуют ли готовые алгоритмы для этого?

Язык реализации — не существенен.

← Автодополнение в Bash как в Zsh
Как узнать pid родительского процесса по pid дочернего ? →

Примеры:

  • есть сайт с глобальным поиском. Поиск должен индексировать любые сущности сайта.
  • есть блокнот, в открытых файлах надо найти похожую последовательность символов.
KennyMinigun ★★★★★
() автор топика
Последнее исправление: KennyMinigun (всего исправлений: 1)
Ответ на: комментарий от KennyMinigun

Для английского языка есть еще такой забавный костыль как soundex

buddhist ★★★★★
()
Ответ на: комментарий от KennyMinigun

Тока, эта, работать с UTF-8 в этом контексте не очень здорово.

Вообще, недавно набрёл вот на какую штуку по этой теме: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

Однако, нужно помнить, что расстояние Левенштейна - это не совсем то, чего ждут от Вас Ваши пользователи. Тут ниже уже посоветовали soundex, а вообще для русскоязычных (иначе - зачем UTF-8? :) ) сайтов характерен другой набор пользовательских ошибок при наборе, чем тот, который описывается «классической» дистанцией Левенштейна. Например, набор фраз в неверной раскладке или ещё какая бНОПНЯ - ДЛ тут совсем не при делах :)

AlexM ★★★★★
()

Посмотри, как Xapian определяет слова с опечатками.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Автодополнение в Bash как в Zsh
Development
Как узнать pid родительского процесса по pid дочернего ? →