В информатике приблизительное сопоставление строк (часто в разговорной речи называемое нечетким поиском строк ) — это метод поиска строк , которые приблизительно соответствуют шаблону (а не точно). Проблема приблизительного сопоставления строк обычно делится на две подзадачи: поиск приблизительных совпадений подстрок внутри заданной строки и поиск строк словаря, которые приблизительно соответствуют шаблону.
Близость соответствия измеряется в терминах количества примитивных операций, необходимых для преобразования строки в точное соответствие. Это число называется расстоянием редактирования между строкой и шаблоном. Обычные примитивные операции: [1]
Эти три операции можно обобщить как формы замены путем добавления символа NULL (здесь обозначенного *) везде, где символ был удален или вставлен:
Некоторые приближенные сопоставители также рассматривают транспозицию , при которой позиции двух букв в строке меняются местами, как примитивную операцию. [1]
Различные приблизительные сопоставители накладывают различные ограничения. Некоторые сопоставители используют единую глобальную невзвешенную стоимость, то есть общее количество примитивных операций, необходимых для преобразования соответствия в шаблон. Например, если шаблон — coil , то foil отличается одной заменой, coils — одной вставкой, oil — одним удалением, а foal — двумя заменами. Если все операции считаются одной единицей стоимости и предел установлен на единицу, то foil , coils и oil будут считаться соответствиями, а foal — нет.
Другие сопоставители указывают количество операций каждого типа отдельно, а третьи устанавливают общую стоимость, но позволяют назначать разные веса разным операциям. Некоторые сопоставители допускают отдельные назначения лимитов и весов для отдельных групп в шаблоне.
Одно из возможных определений задачи приблизительного сопоставления строк выглядит следующим образом: для заданной строки-шаблона и текстовой строки найти подстроку в T , которая из всех подстрок T имеет наименьшее расстояние редактирования до шаблона P.
Подход грубой силы будет заключаться в вычислении расстояния редактирования до P для всех подстрок T, а затем выборе подстроки с минимальным расстоянием. Однако этот алгоритм будет иметь время выполнения O ( n 3 m ).
Лучшее решение, предложенное Селлерсом [2] , основано на динамическом программировании . Оно использует альтернативную формулировку задачи: для каждой позиции j в тексте T и каждой позиции i в шаблоне P вычислить минимальное расстояние редактирования между i первыми символами шаблона , и любой подстрокой T , которая заканчивается в позиции j .
Для каждой позиции j в тексте T и каждой позиции i в шаблоне P пройдитесь по всем подстрокам T, заканчивающимся на позиции j , и определите, какая из них имеет минимальное расстояние редактирования до i первых символов шаблона P. Запишите это минимальное расстояние как E ( i , j ). После вычисления E ( i , j ) для всех i и j мы можем легко найти решение исходной задачи: это подстрока, для которой E ( m , j ) минимально ( m — длина шаблона P ).
Вычисление E ( m , j ) очень похоже на вычисление расстояния редактирования между двумя строками. Фактически, мы можем использовать алгоритм вычисления расстояния Левенштейна для E ( m , j ), с той лишь разницей, что мы должны инициализировать первую строку нулями и сохранить путь вычисления, то есть, использовали ли мы E ( i − 1, j ), E( i , j − 1) или E ( i − 1, j − 1) при вычислении E ( i , j ).
В массиве, содержащем значения E ( x , y ), мы затем выбираем минимальное значение в последней строке, пусть это будет E ( x 2 , y 2 ), и следуем по пути вычисления в обратном направлении, обратно к строке с номером 0. Если поле, к которому мы пришли, было E (0, y 1 ), то T [ y 1 + 1] ... T [ y 2 ] является подстрокой T с минимальным расстоянием редактирования до шаблона P .
Вычисление массива E ( x , y ) занимает O ( mn ) времени с помощью алгоритма динамического программирования, тогда как фаза обратной работы занимает O ( n + m ) времени.
Другая недавняя идея — это соединение по сходству. Когда сопоставление базы данных относится к большому масштабу данных, время O ( mn ) с алгоритмом динамического программирования не может работать в течение ограниченного времени. Поэтому идея состоит в том, чтобы уменьшить количество пар кандидатов, вместо того, чтобы вычислять сходство всех пар строк. Широко используемые алгоритмы основаны на проверке фильтров, хешировании, локально-чувствительном хешировании (LSH), Tries и других жадных и приближенных алгоритмах. Большинство из них разработаны для соответствия некоторой структуре (например, Map-Reduce) для параллельных вычислений.
Традиционно алгоритмы приблизительного сопоставления строк делятся на две категории: онлайн и офлайн. С помощью онлайн-алгоритмов шаблон может быть обработан до поиска, но текст не может. Другими словами, онлайн-методы выполняют поиск без индекса. Ранние алгоритмы для онлайн-приблизительного сопоставления были предложены Вагнером и Фишером [3] и Селлерсом. [2] Оба алгоритма основаны на динамическом программировании, но решают разные задачи. Алгоритм Селлерса ищет приблизительно подстроку в тексте, в то время как алгоритм Вагнера и Фишера вычисляет расстояние Левенштейна , будучи подходящим только для нечеткого поиска по словарю.
Методы поиска в сети неоднократно совершенствовались. Возможно, самым известным усовершенствованием является алгоритм bitap (также известный как алгоритм shift-or и shift-and), который очень эффективен для относительно коротких строк шаблонов. Алгоритм Bitap является сердцем поисковой утилиты Unix agrep . Обзор алгоритмов поиска в сети был сделан G. Navarro. [4]
Хотя существуют очень быстрые онлайн-методы, их производительность на больших данных неприемлема. Предварительная обработка текста или индексация значительно ускоряют поиск. Сегодня представлено множество алгоритмов индексации. Среди них деревья суффиксов [5] , метрические деревья [6] и методы n-грамм . [7] [8] Подробный обзор методов индексации, позволяющий находить произвольную подстроку в тексте, дан Наварро и др. [7] Вычислительный обзор методов словаря (т. е. методов, которые позволяют находить все слова словаря, которые приблизительно соответствуют шаблону поиска) дан Бойцовым. [9]
Распространенные приложения приблизительного соответствия включают проверку орфографии . [5] С появлением больших объемов данных ДНК сопоставление нуклеотидных последовательностей стало важным приложением. [1] Приблизительное сопоставление также используется в фильтрации спама . [5] Связывание записей — распространенное приложение, в котором сопоставляются записи из двух разнородных баз данных.
Сопоставление строк не может использоваться для большинства двоичных данных, таких как изображения и музыка. Они требуют других алгоритмов, таких как акустическое отпечатки пальцев .
Обычный инструмент командной строки fzf часто используется для интеграции приблизительного поиска строк в различные приложения командной строки. [10]
