Введение
Найти строки, которые приблизительно соответствуют шаблону
В информатике, приблизительное сопоставление строк (часто неформально называемое нечетким поиском строк) — это техника поиска строк, которые соответствуют шаблону приблизительно, а не точно. Задача приблизительного сопоставления строк обычно разделяется на две подзадачи: поиск приблизительных совпадений подстрок внутри заданной строки и поиск строк из словаря, которые приблизительно соответствуют шаблону.
Онлайн против офлайн
Традиционно алгоритмы приблизительного сопоставления строк классифицируются на две категории: онлайн и офлайн. В онлайн-алгоритмах образец может быть обработан перед поиском, но текст – нет. Иными словами, онлайн-методы выполняют поиск без индекса. Ранние алгоритмы для приблизительного сопоставления в режиме онлайн были предложены Вагнером и Фишером и Селлерсом. Оба алгоритма основаны на динамическом программировании, но решают разные задачи. Алгоритм Селлерса приблизительно ищет подстроку в тексте, в то время как алгоритм Вагнера и Фишера вычисляет расстояние Левенштейна, которое подходит только для нечёткого поиска в словаре. Онлайн-методы поиска неоднократно улучшались. Пожалуй, самым известным улучшением является алгоритм битапа (также известный как алгоритм сдвига И или сдвига и сдвига), который очень эффективен для относительно коротких строк-шаблонов. Алгоритм Bitap лежит в основе поисковой утилиты agrep в Unix. Обзор алгоритмов онлайн-поиска был выполнен Г. Наварро. Хотя существуют очень быстрые онлайн-методы, их производительность при работе с большими данными неприемлема. Предварительная обработка текста или индексация значительно ускоряют поиск. Сегодня представлено множество алгоритмов индексации, включая деревья суффиксов, метрические деревья и методы n-грамм. Подробный обзор методов индексации, позволяющих найти произвольную подстроку в тексте, представлен Наварро и др. Бойцов дал вычислительный обзор словарных методов (то есть методов, позволяющих найти все слова из словаря, приблизительно соответствующие поисковому шаблону).
famous improvement is the bitap algorithm (also known as the shift or and shift and algorithm), which is very efficient for relatively short pattern strings. The Bitap algorithm is the heart of the Unix searching utility agrep. A review of on line searching algorithms was done by G. Navarro. Although very fast on line techniques exist, their performance on large data is unacceptable. Text preprocessing or indexing makes searching dramatically faster. Today, a variety of indexing algorithms have been presented. Among them are suffix trees, metric trees and n gram methods. A detailed survey of indexing techniques that allows one to find an arbitrary substring in a text is given by Navarro et al. A computational survey of dictionary methods (i. e., methods that permit finding all dictionary words that approximately match a search pattern) is given by Boytsov.
Приложения
Общие применения приблизительного сопоставления включают проверку орфографии. С появлением больших объемов данных ДНК, сопоставление нуклеотидных последовательностей стало важным направлением применения. Приблизительное сопоставление также используется в фильтрации спама. Связывание записей – распространенная задача, при которой сопоставляются записи из двух различных баз данных. Для большинства бинарных данных, таких как изображения и музыка, сопоставление строк неприменимо. Для них требуются другие алгоритмы, например, акустическое распознавание. Популярный инструмент командной строки fzf часто используется для интеграции приблизительного поиска строк в различные приложения командной строки.