Нечёткий поиск

Материал из Кафедра АСОИУ
Перейти к: навигация, поиск

Нечёткий поиск

Нечеткий поиск является крайне полезной функцией любой поисковой системы.
Задачу нечеткого поиска можно сформулировать так: «По заданному слову найти в тексте или словаре размера n все слова, совпадающие с этим словом(или начинающиеся с этого слова) с учетом k возможных различий». Например, при запросе «Машина» с учетом двух возможных ошибок, найти слова «Машинка», «Махина», «Малина», «Калина» и так далее.

Алгоритмы нечеткого поиска характеризуются метрикой — функцией расстояния между двумя словами, позволяющей оценить степень их сходства в данном контексте. Строгое математическое определение метрики включает в себя необходимость соответствия условию неравенства треугольника (X — множество слов, p — метрика):

p(x,y)=<p(x,z)+p(z,y)

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

При реализации нечёткого поиска было использовано расстояние Хемминга.

Расстояние Хэмминга — число позиций, в которых соответствующие символы двух слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.

В приложении было реализовано простое последовательное применение заданной метрики к словам из входного текста. При использовании метрики с ограничением, этот метод позволяет добиться оптимальной скорости работы. Но, при этом, чем больше k, тем сильнее возрастает время работы. Асимптотическая оценка времени — O(kn).

Ссылки