Алгоритм битап
( Битовый алгоритм как также известный Баеза ) алгоритм -Йейтса-Гоннета представляет собой приблизительный алгоритм сопоставления строк . Алгоритм определяет, содержит ли данный текст подстроку, которая «приблизительно равна» данному шаблону, где приблизительное равенство определяется с точки зрения расстояния Левенштейна - если подстрока и шаблон находятся на заданном расстоянии k друг от друга, то алгоритм считает их равными. Алгоритм начинается с предварительного вычисления набора битовых масок, содержащих по одному биту для каждого элемента шаблона. Тогда он сможет выполнять большую часть работы с помощью побитовых операций , которые выполняются чрезвычайно быстро.
Алгоритм bitap, возможно, наиболее известен как один из основных алгоритмов Unix утилиты agrep , написанной Уди Манбером , Сунь Ву и Бурра Гопалом . В оригинальной статье Манбера и Ву алгоритм расширен для работы с нечетким сопоставлением общих регулярных выражений .
Из-за структур данных, требуемых алгоритмом, он лучше всего работает с шаблонами меньшей постоянной длины (обычно длиной слова рассматриваемой машины), а также предпочитает входные данные небольшому алфавиту. Однако , как только он был реализован для данного алфавита и длины слова m , время его работы полностью предсказуемо — оно выполняется за O ( mn ) операций, независимо от структуры текста или шаблона.
Битовый алгоритм для точного поиска строк был изобретен Балинтом Дёмёлки в 1964 году. [1] [2] и расширен Р.К. Шьямасундаром в 1977 г. [3] до того, как его заново изобрели Рикардо Баэса-Йейтс и Гастон Гонне. [4] в 1989 г. (одна глава первой авторской кандидатской диссертации [5] ), который также расширил его для обработки классов символов, подстановочных знаков и несоответствий. В 1991 году его расширили Манбер и Ву. [6] [7] для обработки также вставок и удалений (полный поиск нечеткой строки). Позже этот алгоритм был улучшен Баэза-Йейтсом и Наварро в 1996 году. [8]
Точный поиск
[ редактировать ]Побитовый алгоритм точного поиска строк в полной общности выглядит в псевдокоде так:
algorithm bitap_search is input: text as a string. pattern as a string. output: string m := length(pattern) if m = 0 then return text /* Initialize the bit array R. */ R := new array[m+1] of bit, initially all 0 R[0] := 1 for i := 0; i < length(text); i += 1 do /* Update the bit array. */ for k := m; k ≥ 1; k -= 1 do R[k] := R[k - 1] & (text[i] = pattern[k - 1]) if R[m] then return (text + i - m) + 1 return null
Bitap отличается от других известных алгоритмов поиска строк своим естественным отображением на простые побитовые операции, как в следующей модификации приведенной выше программы. Обратите внимание, что в этой реализации, как ни странно, каждый бит со значением 0 указывает на совпадение, а каждый бит со значением 1 указывает на несовпадение. Тот же алгоритм можно написать с интуитивной семантикой для 0 и 1, но в этом случае мы должны ввести во внутренний цикл еще одну инструкцию для установки R |= 1. В этой реализации мы воспользуемся тем фактом, что сдвиг значения влево смещается на нули справа, и это именно то поведение, которое нам нужно.
Обратите также внимание, что нам требуется CHAR_MAX дополнительные битовые маски для преобразования (text[i] == pattern[k-1]) условие в общей реализации на побитовые операции. Следовательно, алгоритм битового ввода работает лучше при применении к входным данным с меньшими алфавитами.
#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!"; /* Initialize the bit array R */ R = ~1; /* Initialize the pattern bitmasks */ 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) { /* Update the bit array */ R |= pattern_mask[text[i]]; R <<= 1; if (0 == (R & (1UL << m))) return (text + i - m) + 1; } return NULL; }Нечеткий поиск
[ редактировать ]Чтобы выполнить поиск нечеткой строки с использованием битового алгоритма, необходимо расширить битовый массив 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!"; /* Initialize the bit array R */ R = malloc((k+1) * sizeof *R); for (i=0; i <= k; ++i) R[i] = ~1; /* Initialize the pattern bitmasks */ 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) { /* Update the bit arrays */ 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]; /* Substitution is all we care about */ 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; }См. также
[ редактировать ]Внешние ссылки и ссылки
[ редактировать ]- ^ Балинт Дёмёлки, Алгоритм синтаксического анализа, Компьютерная лингвистика 3, Венгерская академия наук, стр. 29–46, 1964.
- ^ Балинт Дёмёлки, Универсальная система компилятора, основанная на правилах производства, BIT Numerical Mathematics , 8 (4), стр. 262–275, 1968. два : 10.1007/BF01933436
- ^ Р. К. Шьямасундар, Анализ приоритета с использованием алгоритма Дёмёлки, Международный журнал компьютерной математики , 6 (2), стр. 105–114, 1977.
- ^ Рикардо Баэса-Йейтс. «Эффективный поиск текста». Докторская диссертация, Университет Ватерлоо, Канада, май 1989 г.
- ^ Уди Манбер, Сунь Ву. «Быстрый поиск текста с ошибками». Технический отчет ТР-91-11. Факультет компьютерных наук, Университет Аризоны , Тусон, июнь 1991 г. ( gzip PostScript )
- ^ Рикардо Баэса-Йейтс, Гастон Х. Гонне. «Новый подход к поиску текста». Communications of ACM , 35(10): стр. 74–82, октябрь 1992 г.
- ^ Уди Манбер, Сунь Ву. «Быстрый текстовый поиск, допускающий ошибки». Сообщения ACM , 35(10): стр. 83–91, октябрь 1992 г., дои : 10.1145/135239.135244 .
- ^ Р. Баеза-Йейтс и Г. Наварро. Более быстрый алгоритм приблизительного сопоставления строк. В книге Дэна Хирчсберга и Джина Майерса, редакторов, Combinatorial Pattern Matching (CPM'96), LNCS 1075, страницы 1–23, Ирвин, Калифорния, июнь 1996 г.
- ^ Г. Майерс. «Быстрый бит-векторный алгоритм для приблизительного сопоставления строк, основанный на динамическом программировании». Журнал ACM 46 (3), май 1999 г., 395–415.
- libbitap — бесплатная реализация, показывающая, как можно легко расширить алгоритм для большинства регулярных выражений. В отличие от приведенного выше кода, он не накладывает ограничений на длину шаблона.
- Рикардо Баэса-Йейтс, Бертье Рибейро-Нето. Современный информационный поиск . 1999. ISBN 0-201-39829-X .
- bitap.py — реализация алгоритма Bitap на Python с модификациями Wu-Manber.