Приближенное соответствие строк

В информатике, приближенное соответствие строк (также называемый нечетким поиском) — техника нахождения строк, которые приблизительно соответствуют шаблону (но не точно). Задача нахождения приближенного соответствия строк обычно делится на две подзадачи: нахождение приближенных совпадений подстрок внутри данной строки и нахождение словаря строк которые приблизительно соответствуют шаблону.

Нечеткий поиск в Википедии на запрос «ромио и джульетта», выдает результаты на запрос «ромео и джульетта»

ОбзорПравить

Схожесть строк измеряется количеством базовых операций, необходимых для преобразования входной строки E в выходную строку E'. Это значение называется редакционным расстоянием между строкой и шаблоном. Обычные базовые операции:

• вставка: кот → коты
• удаление: коты → кот
• замена: коты → кота

Эти три операции могут быть обобщены как формы замены путём добавления символа NULL (здесь обозначается *) везде где символ был удален или вставлен

• вставка: кот* → коты
• удаление: коты → кот*
• замена: коты → кота

Некоторые алгоритмы также обрабатывают транспозицию, в котором позиции двух букв в строке меняются местами, это ещё одна примитивная операция.

• транспозиция: кот → кто

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

• кота → коты отличается одной заменой,
• кота → котам — одной вставкой
• кота → кот — одним удалением
• кота → кофе — двумя заменами.

Если считать, что отдельная операция стоит единицу и применить алгоритм с максимальной стоимостью равной 1, то слова коты, коту и кот — совпадают, а кофе — нет.

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

Примеры алгоритмов:

• Расстояние Левенштейна
• Расстояние Дамерау — Левенштейна
• Алгоритм Bitap
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья
• Сходство Джаро — Винклера.

ПрименениеПравить

Обычно алгоритмы нечеткого соответствие используется в системах проверки правописания. Так, при наличию большого количество ДНК данных, сопоставление нуклеотидных последовательностей стало важным применением. Также нечетких поиск используется в фильтрации спама. Сопоставления данных обычно используемый в приложении где используются записи из нескольких баз данных.

Алгоритмы оценки соответствия строк не может быть использована для большинства видов двоичных данных, таких как изображения и звуки. Для них требуются различные алгоритмы, такие как звуковой отпечаток.