Введение
Алгоритм битапа (также известный как алгоритм Shift Or, Shift И или алгоритм Бэеса-Ятеса-Гоннета) — это алгоритм приблизительного сопоставления строк. Алгоритм определяет, содержит ли данный текст подстроку, которая "приблизительно равна" заданному шаблону, где приблизительное равенство определяется с точки зрения расстояния Левенштейна. Если подстрока и шаблон находятся на расстоянии не более заданного значения k друг от друга, алгоритм считает их равными. Алгоритм начинается с предварительного вычисления набора битовых масок, содержащих один бит для каждого элемента шаблона. Затем он может выполнять большую часть работы с помощью битовых операций, которые чрезвычайно быстры. Алгоритм битапа, пожалуй, наиболее известен как один из базовых алгоритмов утилиты Unix agrep, разработанной Уди Манбером, Сун Ву и Буррой Гопалом. Оригинальная работа Манбера и Ву содержит расширения алгоритма для решения задач нечёткого сопоставления общих регулярных выражений. В силу структуры данных, необходимой алгоритму, он наиболее эффективен для шаблонов небольшой фиксированной длины (обычно равной длине машинного слова) и для входных данных, использующих небольшой алфавит. Однако, после реализации для заданного алфавита и длины слова m, время его работы полностью предсказуемо — он выполняется за O(mn) операций, независимо от структуры текста или шаблона. Алгоритм битапа для точного поиска строк был изобретён Балинтом Дёмелки в 1964 году и расширен Р. К. Шьямасундаром в 1977 году, а затем повторно изобретён Рикардо Бэесой-Ятесом и Гастоном Гоннетом в 1989 году (в одной из глав докторской диссертации первого автора), который также расширил его для обработки классов символов, подстановочных знаков и несовпадений. В 1991 году Манбер и Ву расширили его для обработки вставок и удалений (полноценный нечёткий поиск строк). Этот алгоритм был впоследствии улучшен Бэесой-Ятесом и Наварро в 1996 году. TOC
The bitap algorithm (also known as the shift or, shift and or Baeza Yates Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast. The bitap algorithm is perhaps best known as one of the underlying algorithms of the Unix utility agrep, written by Udi Manber, Sun Wu, and Burra Gopal. Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general regular expressions. Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the word length of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length m, however, its running time is completely predictableit runs in O(mn) operations, no matter the structure of the text or the pattern. The bitap algorithm for exact string searching was invented by Bálint Dömölki in 1964 and extended by R. K. Shyamasundar in 1977, before being reinvented by Ricardo Baeza Yates and Gaston Gonnet in 1989 (one chapter of first author's PhD thesis) which also extended it to handle classes of characters, wildcards, and mismatches. In 1991, it was extended by Manber and Wu to handle also insertions and deletions (full fuzzy string searching). This algorithm was later improved by Baeza Yates and Navarro in 1996. TOC
Внешние ссылки и ссылки
Балинт Дёмёлки, Алгоритм синтаксического анализа, Вычислительная лингвистика, 3, Венгерская академия наук, стр. 29–46, 1964. Балинт Дёмёлки, Универсальная компиляторная система на основе правил вывода, BIT Numerical Mathematics, 8(4), стр. 262–275, 1968. Р. К. Шьямасундар, Синтаксический анализ с приоритетами с использованием алгоритма Дёмёлки, Международный журнал компьютерной математики, 6(2), стр. 105–114, 1977. Рикардо Баэса Йейтс, "Эффективный поиск текста". Докторская диссертация, Университет Ватерлоо, Канада, май 1989. Уди Манбер, Сун Ву, "Быстрый поиск текста с ошибками". Технический отчет TR 91 11. Департамент компьютерных наук, Университет Аризоны, Тусон, июнь 1991. (сжатый PostScript). Рикардо Баэса Йейтс, Гастон Гоннет, "Новый подход к поиску текста". Communications of the ACM, 35(10), стр. 74–82, октябрь 1992. Уди Манбер, Сун Ву, "Быстрый поиск текста с допускаемыми ошибками". Communications of the ACM, 35(10), стр. 83–91, октябрь 1992. Р. Баэса Йейтс и Г. Наварро, Более быстрый алгоритм для приближенного сопоставления строк. В Дэн Хиршберге и Джин Майерс (ред.), Комбинаторное сопоставление образцов (CPM'96), LNCS 1075, стр. 1–23, Ирвин, Калифорния, июнь 1996. Г. Майерс, "Быстрый алгоритм с битовыми векторами для приближенного сопоставления строк на основе динамического программирования". Journal of the ACM, 46(3), май 1999, 395–415. libbitap – бесплатная реализация, демонстрирующая, как алгоритм можно легко расширить для большинства регулярных выражений. В отличие от приведенного выше кода, она не ограничивает длину шаблона. Рикардо Баэса Йейтс, Бертье Рибейро Нето, Современный информационный поиск, 1999. bitap.py – Python-реализация алгоритма Bitap с модификациями Wu Manber.
Ricardo Baeza Yates, Gastón H. Gonnet. "A New Approach to Text Searching." Communications of the ACM, 35(10): pp. 74–82, October 1992. Udi Manber, Sun Wu. "Fast text search allowing errors." Communications of the ACM, 35(10): pp. 83–91, October 1992, R. Baeza Yates and G. Navarro. A faster algorithm for approximate string matching. In Dan Hirchsberg and Gene Myers, editors, Combinatorial Pattern Matching (CPM'96), LNCS 1075, pages 1–23, Irvine, CA, June 1996. G. Myers. "A fast bit vector algorithm for approximate string matching based on dynamic programming." Journal of the ACM 46 (3), May 1999, 395–415. libbitap, a free implementation that shows how the algorithm can easily be extended for most regular expressions. Unlike the code above, it places no limit on the pattern length. Ricardo Baeza Yates, Berthier Ribeiro Neto. Modern Information Retrieval. 1999. bitap. py Python implementation of Bitap algorithm with Wu Manber modifications.