Loading AI tools
алгоритм для нахождение строк которые приблизительно соответствуют паттерну Из Википедии, свободной энциклопедии
В информатике, приближённое соответствие строк (также называемый нечётким поиском) — техника нахождения строк, которые приблизительно соответствуют шаблону (но не точно). Задача нахождения приближённого соответствия строк обычно делится на две подзадачи: нахождение приближённых совпадений подстрок внутри данной строки и нахождение словаря строк, которые приблизительно соответствуют шаблону.
Схожесть строк измеряется количеством базовых операций, необходимых для преобразования входной строки E в выходную строку E'. Это значение называется редакционным расстоянием между строкой и шаблоном. Обычные базовые операции:
Эти три операции могут быть обобщены как формы замены путём добавления символа NULL (здесь обозначается *) везде, где символ был удален или вставлен
Некоторые алгоритмы также обрабатывают транспозицию, в котором позиции двух букв в строке меняются местами, это ещё одна примитивная операция.
Разные алгоритмы позволяют накладывать разные типы ограничения. Некоторые алгоритмы поддерживают одиночную глобальную невзвешенную стоимость, то есть общее число базовых операций, необходимых для превращения совпадения в паттерн. Например, если шаблон — кота то:
Если считать, что отдельная операция стоит единицу и применить алгоритм с максимальной стоимостью равной 1, то слова коты, коту и кот — совпадают, а кофе — нет.
Другие алгоритмы назначают количество разных операций отдельно, в то время как остальные считают общую стоимость, но разрешают устанавливать разную стоимость для разных операций. Некоторые алгоритмы позволяют отдельно назначать пределы и веса для отдельных групп в шаблоне.
Примеры алгоритмов[1]:
Обычно алгоритмы нечёткого соответствия используется в системах проверки правописания. Так, при наличии большого количество ДНК-данных, сопоставление нуклеотидных последовательностей стало важным применением. Также нечёткий поиск используется в фильтрации спама. Сопоставления данных обычно используемый в приложении где используются записи из нескольких баз данных.
Алгоритмы оценки соответствия строк не могут быть использованы для большинства видов двоичных данных, таких как изображения и звуки. Для них требуются другие алгоритмы, такие как звуковой отпечаток.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.