Приближенное соответствие строк
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/23/%D0%9D%D0%B5%D1%87%D0%B5%D1%82%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%80%D1%83%D1%81%D1%81%D0%BA%D0%BE%D0%BC_%D1%80%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D0%B5_%D0%B2%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D0%B8..png/300px-%D0%9D%D0%B5%D1%87%D0%B5%D1%82%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%80%D1%83%D1%81%D1%81%D0%BA%D0%BE%D0%BC_%D1%80%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D0%B5_%D0%B2%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D0%B8..png)
В информатике, приближённое соответствие строк (также называемый нечётким поиском) — техника нахождения строк, которые приблизительно соответствуют шаблону (но не точно). Задача нахождения приближённого соответствия строк обычно делится на две подзадачи: нахождение приближённых совпадений подстрок внутри данной строки и нахождение словаря строк, которые приблизительно соответствуют шаблону.
Обзор
[править | править код]Схожесть строк измеряется количеством базовых операций, необходимых для преобразования входной строки E в выходную строку E'. Это значение называется редакционным расстоянием между строкой и шаблоном. Обычные базовые операции:
- вставка: кот → коты
- удаление: коты → кот
- замена: коты → кота
Эти три операции могут быть обобщены как формы замены путём добавления символа NULL (здесь обозначается *) везде, где символ был удален или вставлен
- вставка: кот* → коты
- удаление: коты → кот*
- замена: коты → кота
Некоторые алгоритмы также обрабатывают транспозицию, в котором позиции двух букв в строке меняются местами, это ещё одна примитивная операция.
- транспозиция: кот → кто
Разные алгоритмы позволяют накладывать разные типы ограничения. Некоторые алгоритмы поддерживают одиночную глобальную невзвешенную стоимость, то есть общее число базовых операций, необходимых для превращения совпадения в паттерн. Например, если шаблон — кота то:
- кота → коты отличается одной заменой,
- кота → котам — одной вставкой
- кота → кот — одним удалением
- кота → кофе — двумя заменами.
Если считать, что отдельная операция стоит единицу и применить алгоритм с максимальной стоимостью равной 1, то слова коты, коту и кот — совпадают, а кофе — нет.
Другие алгоритмы назначают количество разных операций отдельно, в то время как остальные считают общую стоимость, но разрешают устанавливают разную стоимость для разных операций. Некоторые алгоритмы позволяют отдельно назначать пределы и веса для отдельных групп в шаблоне.
Примеры алгоритмов[1]:
- Расстояние Левенштейна
- Расстояние Дамерау — Левенштейна
- Алгоритм Bitap
- Алгоритм расширения выборки
- Метод N-грамм
- Хеширование по сигнатуре
- BK-деревья
- Сходство Джаро — Винклера.
Применение
[править | править код]Обычно алгоритмы нечёткого соответствия используется в системах проверки правописания. Так, при наличии большого количество ДНК-данных, сопоставление нуклеотидных последовательностей стало важным применением. Также нечёткий поиск используется в фильтрации спама. Сопоставления данных обычно используемый в приложении где используются записи из нескольких баз данных.
Алгоритмы оценки соответствия строк не могут быть использованы для большинства видов двоичных данных, таких как изображения и звуки. Для них требуются другие алгоритмы, такие как звуковой отпечаток.
Примечания
[править | править код]- ↑ Нечёткий поиск в тексте и словаре . Хабр. Дата обращения: 5 сентября 2022. Архивировано 5 сентября 2022 года.
![]() | В статье не хватает ссылок на источники (см. рекомендации по поиску). |