Наиболее часто применяемой метрикой является расстояние Левенштейна, или расстояние редактирования, алгоритмы вычисления которого можно найти на каждом шагу.
Расстояние Левенштейна
Впрочем, на практике расстояние Хемминга оказывается практически бесполезным, уступая более естественным с точки зрения человека метрикам, о которых и пойдет речь ниже.
В числе наиболее известных метрик расстояния Хемминга, Левенштейна и Дамерау-Левенштейна. При этом расстояние Хемминга является метрикой только на множестве слов одинаковой длины, что сильно ограничивает область его применения.
Между тем, в большинстве случаев под метрикой подразумевается более общее понятие, не требующее выполнения такого условия, это понятие можно также назвать расстоянием.
Алгоритмы нечеткого поиска характеризуются метрикой функцией расстояния между двумя словами, позволяющей оценить степень их сходства в данном контексте. Строгое математическое определение метрики включает в себя необходимость соответствия условию неравенства треугольника (X множество слов, p метрика):
Например, при запросе «Машина» с учетом двух возможных ошибок, найти слова «Машинка», «Махина», «Малина», «Калина» и так далее.
«По заданному слову найти в тексте или словаре размера n все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом k возможных различий».
Задачу нечеткого поиска можно сформулировать так:
Нечеткий поиск является крайне полезной функцией любой поисковой системы. Вместе с тем, его эффективная реализация намного сложнее, чем реализация простого поиска по точному совпадению.
А также проведу сравнительное тестирование качества и производительности алгоритмов.
Хеширование по сигнатуре
Алгоритм расширения выборки
Алгоритм Bitap с модификациями от Wu и Manber
Расстояние Дамерау-Левенштейна
Расстояние Левенштейна
В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:
Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду » в тех же поисковых системах.
Нечёткий поиск в тексте и словаре
Нечёткий поиск в тексте и словаре / Хабрахабр
Комментариев нет:
Отправить комментарий