Алгоритм bitap (также известный как shift-or , shift-and или алгоритм Баеза-Йетса-Гонне ) — это алгоритм приблизительного сопоставления строк . Алгоритм сообщает, содержит ли данный текст подстроку, которая «приблизительно равна» данному шаблону, где приблизительное равенство определяется в терминах расстояния Левенштейна — если подстрока и шаблон находятся в пределах заданного расстояния k друг от друга, то алгоритм считает их равными. Алгоритм начинается с предварительного вычисления набора битовых масок, содержащих по одному биту для каждого элемента шаблона. Затем он может выполнить большую часть работы с помощью побитовых операций , которые чрезвычайно быстры.
Алгоритм bitap, пожалуй, наиболее известен как один из базовых алгоритмов утилиты Unix agrep , написанной Уди Манбером , Саном Ву и Баррой Гопалом. Оригинальная статья Манбера и Ву дает расширения алгоритма для работы с нечетким соответствием общих регулярных выражений .
Из-за структур данных, требуемых алгоритмом, он лучше всего работает на шаблонах, длина которых меньше константы (обычно длина слова рассматриваемой машины), а также предпочитает входные данные, а не небольшой алфавит. Однако после того, как он был реализован для заданного алфавита и длины слова m , его время работы полностью предсказуемо — он работает за O ( mn ) операций, независимо от структуры текста или шаблона.
Алгоритм bitap для точного поиска строк был изобретен Балинтом Дёмёльки в 1964 году [1] [2] и расширен Р. К. Шьямасундаром в 1977 году [3] , прежде чем был переизобретен Рикардо Баэза-Йетсом и Гастоном Гонне [4] в 1989 году (одна глава докторской диссертации первого автора [5] ), которые также расширили его для обработки классов символов, подстановочных знаков и несовпадений. В 1991 году он был расширен Манбером и Ву [6] [7] для обработки также вставок и удалений (полный нечеткий поиск строк). Этот алгоритм был позже улучшен Баэза-Йетсом и Наварро в 1996 году. [8]
Алгоритм битап для точного поиска строк в общем виде выглядит на псевдокоде следующим образом:
алгоритм bitap_search имеет входные данные: текст как строка. шаблон как строка. выход: строка m := длина( шаблон ) если m = 0, то вернуть текст /* Инициализируем битовый массив R. */ R := новый массив [ m +1] бит , изначально все 0 R [0] := 1 для i := 0; i < длина( текст ); i += 1 сделать /* Обновить битовый массив. */ для k := m ; k ≥ 1; k -= 1 do R [k] := R [ k - 1] & ( текст [ i ] = шаблон [ k - 1]) если R [ m ] то вернуть ( текст + i - m ) + 1 вернуть ноль
Bitap отличается от других известных алгоритмов поиска строк своим естественным отображением на простые побитовые операции, как в следующей модификации вышеприведенной программы. Обратите внимание, что в этой реализации, вопреки интуиции, каждый бит со значением ноль указывает на совпадение, а каждый бит со значением 1 указывает на несовпадение. Тот же алгоритм можно записать с интуитивной семантикой для 0 и 1, но в этом случае мы должны ввести еще одну инструкцию во внутренний цикл для установки R |= 1. В этой реализации мы используем тот факт, что сдвиг влево значения сдвигает нули справа, что является именно тем поведением, которое нам нужно.
Обратите внимание, что нам требуются CHAR_MAXдополнительные битовые маски для преобразования (text[i] == pattern[k-1])условия в общей реализации в побитовые операции. Поэтому алгоритм bitap работает лучше, когда применяется к входам с меньшими алфавитами.
#include <string.h> #include <limits.h> const char * bitap_bitwise_search ( const char * text , const char * pattern ) { int m = strlen ( pattern ); unsigned long R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i ; if ( pattern [ 0 ] == '\0' ) return text ; if ( m > 31 ) return "The pattern is too long!" ; /* Инициализация битового массива R */ R = ~ 1 ; /* Инициализация битовых масок шаблона */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* Обновляем битовый массив */ R |= pattern_mask [ text [ i ]]; R <<= 1 ; if ( 0 == ( R & ( 1UL << m ))) return ( text + i - m ) + 1 ; } return NULL ; } Для выполнения нечеткого поиска строк с использованием алгоритма bitap необходимо расширить битовый массив R во второе измерение. Вместо одного массива R , который изменяется по длине текста, теперь у нас есть k различных массивов R 1.. k . Массив R i содержит представление префиксов шаблона , которые соответствуют любому суффиксу текущей строки с i или меньшим количеством ошибок. В этом контексте «ошибкой» может быть вставка, удаление или замена; см. расстояние Левенштейна для получения дополнительной информации об этих операциях.
Реализация ниже выполняет нечеткое сопоставление (возвращая первое совпадение с ошибками до k ) с использованием алгоритма нечеткого битапа. Однако он обращает внимание только на замены, а не на вставки или удаления – другими словами, на расстояние Хэмминга k . Как и прежде, семантика 0 и 1 перевернута с их обычных значений .
#include <stdlib.h> #include <string.h> #include <limits.h> const char * bitap_fuzzy_bitwise_search ( const char * text , const char * pattern , int k ) { const char * result = NULL ; int m = strlen ( pattern ); unsigned long * R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i , d ; if ( pattern [ 0 ] == '\0' ) return text ; if ( m > 31 ) return "The pattern is too long!" ; /* Инициализируем битовый массив R */ R = malloc ( ( k + 1 ) * sizeof * R ); for ( i = 0 ; i <= k ; ++ i ) R [ i ] = ~ 1 ; /* Инициализация битовых масок шаблона */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* Обновление битовых массивов */ unsigned long old_Rd1 = R [ 0 ]; R [ 0 ] |= pattern_mask [ text [ i ]]; R [ 0 ] <<= 1 ; for ( d = 1 ; d <= k ; ++ d ) { unsigned long tmp = R [ d ]; /* Все, что нас волнует — это подстановка */ R [ d ] = ( old_Rd1 & ( R [ d ] | pattern_mask [ text [ i ]])) << 1 ; old_Rd1 = tmp ; } if ( 0 == ( R [ k ] & ( 1UL << m ))) { result = ( text + i - m ) + 1 ; break ; } } free ( R ); return result ; }