Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Нечеткий поисковый запрос «сердитый смайлик» в Mediawiki предлагает результат «андре эмоции».

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

Обзор [ править ]

Близость совпадения измеряется количеством примитивных операций, необходимых для преобразования строки в точное совпадение. Это число называется расстоянием редактирования между струной и шаблоном. Обычные примитивные операции: [1]

  • вставка: детская кроватка → co a t
  • удаление: co a t → cot
  • замена: co a t → co s t

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

  • вставка: co * t → co a t
  • удаление: co a t → co * t
  • замена: co a t → co s t

Некоторые средства приблизительного сопоставления также рассматривают транспонирование , при котором позиции двух букв в строке меняются местами, как примитивную операцию. [2]

  • транспонирование: co st → co ts

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

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

Постановка проблемы и алгоритмы [ править ]

Одно из возможных определений приближенной задачи Строка согласования состоит в следующем: Учитывая шаблон строки и текстовая строка , найти подстроку в T , который, из всех подстрок Т , имеет наименьшее расстояние редактирования для шаблона P .

Подход грубой силы заключался бы в вычислении расстояния редактирования до P для всех подстрок T, а затем в выборе подстроки с минимальным расстоянием. Однако этот алгоритм будет иметь время работы O ( n 3  м ).

Лучшее решение, предложенное Селлерсом [3] , основано на динамическом программировании . Он использует альтернативную формулировку задачи: для каждой позиции J в тексте Т и каждую позицию я в шаблоне P , вычислить расстояние минимального редактирования между я первыми символами шаблона, и любая подстрокой из Т , который заканчивается в положении j .

Для каждой позиции J в текст T , и каждой позиции I в шаблон P , пройти через все подстроки T заканчиваясь в положении J , и определить , какой из них имеет минимальное редактировать расстояние до я первых символов шаблона 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. . Если поле мы достигли было Е (0,  у 1 ), то Т [ у 1  + 1] , ...  T [ у 2 ] является подстрокой T с минимальным расстоянием до редактирования шаблона P .

Вычисление массива E ( x ,  y ) занимает O ( mn ) времени с помощью алгоритма динамического программирования, в то время как фаза обратной работы занимает O ( n  +  m ) времени.

Еще одна недавняя идея - соединение подобия. Когда сопоставление базы данных относится к большому объему данных, время O ( mn ) с алгоритмом динамического программирования не может работать в течение ограниченного времени. Итак, идея состоит в том, чтобы вместо вычисления сходства всех пар строк уменьшить количество пар-кандидатов. Широко используемые алгоритмы основаны на проверке фильтров, хешировании, хешировании с учетом местоположения (LSH), попытках и других жадных и аппроксимационных алгоритмах. Большинство из них спроектировано так, чтобы соответствовать какой-либо структуре (например, Map-Reduce) для одновременных вычислений.

Он-лайн или оф-лайн [ править ]

Традиционно алгоритмы приблизительного сопоставления строк подразделяются на две категории: оперативные и автономные. С помощью онлайн-алгоритмов шаблон может быть обработан перед поиском, а текст - нет. Другими словами, онлайн-методы выполняют поиск без индекса. Ранние алгоритмы для приближенного согласования в режиме онлайн были предложены Вагнером и Фишером [4] и Селлерсом [5] . Оба алгоритма основаны на динамическом программировании, но решают разные задачи. Алгоритм Продавца приблизительно ищет подстроку в тексте, в то время как алгоритм Вагнера и Фишера вычисляет расстояние Левенштейна , что подходит только для нечеткого поиска по словарю.

Методики онлайн-поиска неоднократно совершенствовались. Возможно, наиболее известным улучшением является алгоритм побитового отображения (также известный как алгоритм shift-or и shift-and), который очень эффективен для относительно коротких строк шаблона. Алгоритм Bitap является сердцем поисковой утилиты согласования Unix . Обзор алгоритмов онлайн-поиска был сделан Дж. Наварро. [6]

Хотя существуют очень быстрые интерактивные методы, их производительность на больших объемах данных неприемлема. Предварительная обработка текста или индексация значительно ускоряют поиск. Сегодня были представлены самые разные алгоритмы индексации. Среди них суффиксные деревья [7] , метрические деревья [8] и методы n-грамм . [9] [10] Подробный обзор методов индексации, позволяющих найти произвольную подстроку в тексте, дан Navarro et al. [11] Вычислительный обзор словарных методов (т. Е. Методов, которые позволяют находить все словарные слова, которые приблизительно соответствуют поисковому шаблону) дан Бойцовым [12] .

Приложения [ править ]

Общие применения приблизительного соответствия включают проверку орфографии . [13] При наличии большого количества данных ДНК, сопоставление нуклеотидных последовательностей стало важным приложением. [14] Приблизительное соответствие также используется при фильтрации спама . [15] Связывание записей - это обычное приложение, в котором сопоставляются записи из двух разных баз данных.

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

См. Также [ править ]

  • Поиск концепции
  • Расстояние Яро – Винклера
  • Расстояние Левенштейна
  • Хеширование с учетом местоположения
  • Метафон
  • Алгоритм Нидлмана – Вунша
  • Обнаружение плагиата
  • Регулярные выражения для нечеткого и нечеткого сопоставления
  • Алгоритм Смита – Уотермана
  • Soundex
  • Строковая метрика

Ссылки [ править ]

  • ^ Baeza-Yates, R .; Наварро, Г. (июнь 1996 г.). «Более быстрый алгоритм приблизительного сопоставления строк». В Дэне Хирксберге; Джин Майерс (ред.). Комбинаторное сопоставление с образцом (CPM'96), LNCS 1075 . Ирвин, Калифорния. С. 1–23. CiteSeerX  10.1.1.42.1593 .
  • ^ Baeza-Yates, R .; Наварро, Г. «Быстрое приближенное сопоставление строк в словаре» (PDF) . Proc. SPIRE'98 . IEEE CS Press. С. 14–22.
  • ↑ Бойцов, Леонид (2011). «Методы индексирования для приблизительного словарного поиска: Сравнительный анализ». Журнал экспериментальной алгоритмики . 16 (1): 1–91. DOI : 10.1145 / 1963190.1963191 .
  • ^ Кормен, Томас ; Лейзерсон, Ривест (2001). Введение в алгоритмы (2-е изд.). MIT Press. С. 364–7. ISBN 978-0-262-03293-3.
  • ^ Галил, Цви; Апостолико, Альберто (1997). Алгоритмы сопоставления с образцом . Оксфорд [Оксфордшир]: Издательство Оксфордского университета. ISBN 978-0-19-511367-9.
  • ^ Gusfield, Дан (1997). Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 978-0-521-58519-4.
  • ^ Майерс, Г. (май 1999 г.). «Быстрый алгоритм бит-вектор для приблизительного сопоставления строк на основе динамического программирования» (PDF) . Журнал ACM . 46 (3): 395–415. DOI : 10.1145 / 316542.316550 .
  • Перейти ↑ Navarro, Gonzalo (2001). «Экскурсия по приблизительному сопоставлению строк». ACM Computing Surveys . 33 (1): 31–88. CiteSeerX 10.1.1.96.7225 . DOI : 10.1145 / 375360.375365 . 
  • ^ Наварро, Гонсало; Баеза-Йейтс, Рикардо; Сутинен, Эркки; Тархио, Йорма (2001). «Методы индексирования для приблизительного сопоставления строк» (PDF) . Бюллетень IEEE Data Engineering . 24 (4): 19–27.
  • ^ Продавцы, Питер Х. (1980). «Теория и вычисление эволюционных расстояний: распознавание образов». Журнал алгоритмов . 1 (4): 359–73. DOI : 10.1016 / 0196-6774 (80) 90016-4 .
  • ^ Skiena, Steve (1998). Руководство по разработке алгоритмов (1-е изд.). Springer. ISBN 978-0-387-94860-7.
  • ^ Ukkonen, E. (1985). «Алгоритмы приблизительного сопоставления строк» . Информация и контроль . 64 (1–3): 100–18. DOI : 10.1016 / S0019-9958 (85) 80046-2 .
  • ^ Вагнер, Р .; Фишер, М. (1974). «Проблема исправления строки в строку». Журнал ACM . 21 : 168–73. DOI : 10.1145 / 321796.321811 .
  • ^ Зобель, Джастин; Дарт, Филипп (1995). «Нахождение примерных совпадений в больших лексиконах». Программное обеспечение - практика и опыт . 25 (3): 331–345. CiteSeerX 10.1.1.14.3856 . DOI : 10.1002 / spe.4380250307 . 

Внешние ссылки [ править ]

  • Фламинго Проект
  • Проект эффективной обработки запросов на подобие с последними достижениями в приблизительном сопоставлении строк на основе порогового значения расстояния редактирования.
  • StringMetric проекта в Scala библиотеку строковых метрик и фонетических алгоритмов
  • Natural project - библиотека обработки естественного языка JavaScript, которая включает в себя реализации популярных строковых показателей.