Меню Главная Случайная статья Настройки Алгоритмы нечеткого поиска Материал из https://ru.wikipedia.org В информатике, приближённое соответствие строк (также называемый нечётким поиском) — техника нахождения строк, которые приблизительно соответствуют шаблону (но не точно). Задача нахождения приближённого соответствия строк обычно делится на две подзадачи: нахождение приближённых совпадений подстрок внутри данной строки и нахождение словаря строк, которые приблизительно соответствуют шаблону. Обзор Схожесть строк измеряется количеством базовых операций, необходимых для преобразования входной строки E в выходную строку E'. Это значение называется редакционным расстоянием между строкой и шаблоном. Обычные базовые операции: вставка: кот коты удаление: коты кот замена: коты кота Эти три операции могут быть обобщены как формы замены путём добавления символа NULL (здесь обозначается *) везде, где символ был удален или вставлен вставка: кот* коты удаление: коты кот* замена: коты кота Некоторые алгоритмы также обрабатывают транспозицию, в котором позиции двух букв в строке меняются местами, это ещё одна примитивная операция. транспозиция: кот кто Разные алгоритмы позволяют накладывать разные типы ограничения. Некоторые алгоритмы поддерживают одиночную глобальную невзвешенную стоимость, то есть общее число базовых операций, необходимых для превращения совпадения в паттерн. Например, если шаблон — кота то: кота коты отличается одной заменой, кота котам — одной вставкой кота кот — одним удалением кота кофе — двумя заменами. Если считать, что отдельная операция стоит единицу и применить алгоритм с максимальной стоимостью равной 1, то слова коты, коту и кот — совпадают, а кофе — нет. Другие алгоритмы назначают количество разных операций отдельно, в то время как остальные считают общую стоимость, но разрешают устанавливать разную стоимость для разных операций. Некоторые алгоритмы позволяют отдельно назначать пределы и веса для отдельных групп в шаблоне. Примеры алгоритмов[1]: Расстояние Левенштейна Расстояние Дамерау — Левенштейна Алгоритм Bitap Алгоритм расширения выборки Метод N-грамм Хеширование по сигнатуре BK-деревья Сходство Джаро — Винклера. Применение Обычно алгоритмы нечёткого соответствия используется в системах проверки правописания. Так, при наличии большого количество ДНК-данных, сопоставление нуклеотидных последовательностей стало важным применением. Также нечёткий поиск используется в фильтрации спама. Сопоставления данных обычно используемый в приложении где используются записи из нескольких баз данных. Алгоритмы оценки соответствия строк не могут быть использованы для большинства видов двоичных данных, таких как изображения и звуки. Для них требуются другие алгоритмы, такие как звуковой отпечаток. Примечания Нечёткий поиск в тексте и словаре  (рус.). Хабр. Дата обращения: 5 сентября 2022. Архивировано 5 сентября 2022 года.