Битап алгоритм - Bitap algorithm

В битовый алгоритм (также известный как сдвиг-или, сдвиг и или же Баеза-Йетс – Гонне алгоритм) является приблизительное соответствие строк алгоритм. Алгоритм сообщает, содержит ли данный текст подстроку, которая «приблизительно равна» заданному шаблону, где примерное равенство определяется в терминах Расстояние Левенштейна - если подстрока и шаблон находятся на заданном расстоянии k друг друга, то алгоритм считает их равными. Алгоритм начинается с предварительного вычисления набора битовые маски содержащий по одному биту для каждого элемента шаблона. Тогда он сможет выполнять большую часть работы с побитовые операции, которые очень быстрые.

Битовый алгоритм, пожалуй, наиболее известен как один из основных алгоритмов Unix полезность соглашаться, написано Уди Манбер, Сунь У, и Бурра Гопал. В оригинальной статье Манбера и Ву даны расширения алгоритма для работы с нечетким сопоставлением общих обычные выражения.

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

Битовый алгоритм для точного поиска строки был изобретен Балинтом Дёмёльки в 1964 году.[1][2] и расширен Р. К. Шьямасундаром в 1977 г.[3], прежде чем быть изобретенным заново Рикардо Баеза-Йейтс и Гастон Гонне[4] в 1989 г. (одна глава первой авторской кандидатской диссертации[5]), который также расширил его для обработки классов символов, подстановочных знаков и несоответствий. В 1991 году он был расширен на Manber и Ву [6][7] также обрабатывать вставки и удаления (полный поиск по нечеткой строке). Позднее этот алгоритм был улучшен Баезой-Йейтсом и Наварро в 1996 г.[8] а позже Джин Майерс на длинные выкройки в 1998 году.[9]

Точный поиск

Битовый алгоритм для точного поиск строки, в общем, в псевдокоде выглядит так:

алгоритм bitap_search является    Вход: текст в виде строки. шаблон в виде строки. выход: нить м : = длина (шаблон)    если м = 0 тогда        возвращаться текст    / * Инициализируем битовый массив R. * / р := новый множество[м+1] из бит, изначально все 0 р[0] := 1    за я := 0; я <длина (текст); я += 1 делать        / * Обновляем битовый массив. * / за k := м; k ≥ 1; k -= 1 делать            р[k]: = р[k - 1] & (текст[я] = шаблон[k - 1])        если р[м] тогда            возвращаться (текст + я - м) + 1    возвращаться ноль

Bitap отличается от других хорошо известных алгоритмов поиска строк своим естественным отображением на простые побитовые операции, как в следующей модификации вышеупомянутой программы. Обратите внимание, что в этой реализации, как это ни парадоксально, каждый бит со значением 0 указывает совпадение, а каждый бит со значением 1 указывает на несовпадение. Тот же алгоритм можно написать с интуитивной семантикой для 0 и 1, но в этом случае мы должны ввести другую инструкцию в внутренний цикл устанавливать R | = 1. В этой реализации мы пользуемся преимуществом того факта, что при сдвиге влево значение сдвигается нулями вправо, что и является именно тем поведением, которое нам нужно.

Также обратите внимание, что мы требуем CHAR_MAX дополнительные битовые маски для преобразования (текст [i] == шаблон [k-1]) условие в общей реализации на побитовые операции. Следовательно, битовый алгоритм работает лучше при применении к входам с меньшими алфавитами.

 #включают <string.h> #включают <limits.h>  const char *bitap_bitwise_search(const char *текст, const char *шаблон) {     int м = Strlen(шаблон);     беззнаковый длинный р;     беззнаковый длинный pattern_mask[CHAR_MAX+1];     int я;      если (шаблон[0] == '\0') возвращаться текст;     если (м > 31) возвращаться "Шаблон слишком длинный!";       / * Инициализируем битовый массив R * /     р = ~1;      / * Инициализируем битовые маски шаблона * /     за (я=0; я <= CHAR_MAX; ++я)         pattern_mask[я] = ~0;     за (я=0; я < м; ++я)         pattern_mask[шаблон[я]] &= ~(1UL << я);      за (я=0; текст[я] != '\0'; ++я) {         / * Обновляем битовый массив * /         р |= pattern_mask[текст[я]];         р <<= 1;          если (0 == (р & (1UL << м)))             возвращаться (текст + я - м) + 1;     }      возвращаться НОЛЬ; }

Нечеткий поиск

Чтобы выполнить поиск по нечеткой строке с использованием битового алгоритма, необходимо расширить битовый массив р во второе измерение. Вместо одного массива р который изменяется по длине текста, теперь у нас есть k отдельные массивы р1..k. Множество ря содержит представление префиксов шаблон которые соответствуют любому суффиксу текущей строки с я или меньше ошибок. В этом контексте «ошибка» может быть вставкой, удалением или заменой; видеть Расстояние Левенштейна для получения дополнительной информации об этих операциях.

Реализация ниже выполняет нечеткое соответствие (возвращение первого совпадения до k ошибок) с использованием алгоритма нечеткого битового массива. Однако он обращает внимание только на замены, а не на вставки или удаления - другими словами, Расстояние Хэмминга из k. Как и раньше, семантика 0 и 1 отличается от их обычных значений.

 #включают <stdlib.h> #включают <string.h> #включают <limits.h>  const char *bitap_fuzzy_bitwise_search(const char *текст, const char *шаблон, int k) {     const char *результат = НОЛЬ;     int м = Strlen(шаблон);     беззнаковый длинный *р;     беззнаковый длинный pattern_mask[CHAR_MAX+1];     int я, d;      если (шаблон[0] == '\0') возвращаться текст;     если (м > 31) возвращаться "Шаблон слишком длинный!";      / * Инициализируем битовый массив R * /     р = маллок((k+1) * размер *р);     за (я=0; я <= k; ++я)         р[я] = ~1;      / * Инициализируем битовые маски шаблона * /     за (я=0; я <= CHAR_MAX; ++я)         pattern_mask[я] = ~0;     за (я=0; я < м; ++я)         pattern_mask[шаблон[я]] &= ~(1UL << я);      за (я=0; текст[я] != '\0'; ++я) {         / * Обновляем битовые массивы * /         беззнаковый длинный old_Rd1 = р[0];          р[0] |= pattern_mask[текст[я]];         р[0] <<= 1;          за (d=1; d <= k; ++d) {             беззнаковый длинный tmp = р[d];             / * Замена - это все, что нас волнует * /             р[d] = (old_Rd1 & (р[d] | pattern_mask[текст[я]])) << 1;             old_Rd1 = tmp;         }          если (0 == (р[k] & (1UL << м))) {             результат = (текст+я - м) + 1;             перемена;         }     }      свободный(р);     возвращаться результат; }

Смотрите также

Внешние ссылки и ссылки

  1. ^ Балинт Дёмёльки, Алгоритм синтаксического анализа, Компьютерная лингвистика 3, Венгерская академия наук, стр. 29–46, 1964.
  2. ^ Балинт Дёмёлки, Универсальная система компиляции, основанная на производственных правилах, BIT вычислительная математика, 8 (4), стр. 262–275, 1968. Дои:10.1007 / BF01933436
  3. ^ Р. К. Шьямасундар, Анализ приоритета с использованием алгоритма Демёльки, Международный журнал компьютерной математики, 6 (2) pp 105–114, 1977.
  4. ^ Рикардо Баеза-Йейтс. «Эффективный поиск текста». Докторская диссертация, Университет Ватерлоо, Канада, май 1989 г.
  5. ^ Уди Манбер, Сунь Ву. «Быстрый поиск текста с ошибками». Технический отчет TR-91-11. Департамент компьютерных наук, Университет Аризоны, Тусон, июнь 1991 г. (сжатый PostScript )
  6. ^ Рикардо Баеза-Йейтс, Гастон Х. Гонне. «Новый подход к поиску текста». Коммуникации ACM, 35 (10): pp. 74–82, October 1992.
  7. ^ Уди Манбер, Сунь Ву. «Быстрый текстовый поиск, допускающий ошибки». Коммуникации ACM, 35 (10): pp. 83–91, октябрь 1992 г., стр. Дои:10.1145/135239.135244.
  8. ^ Р. Баеза-Йейтс и Г. Наварро. Более быстрый алгоритм приблизительного сопоставления строк. Дэн Хирксберг и Джин Майерс, редакторы, Комбинаторное сопоставление с образцом (CPM'96), LNCS 1075, страницы 1-23, Ирвин, Калифорния, июнь 1996 г.
  9. ^ Г. Майерс. «Быстрый алгоритм битового вектора для приблизительного сопоставления строк на основе динамического программирования». Журнал ACM 46 (3), май 1999 г., стр. 395–415.
  10. libbitap, бесплатная реализация, показывающая, как алгоритм может быть легко расширен для большинства регулярных выражений. В отличие от приведенного выше кода, он не накладывает ограничений на длину шаблона.
  11. Рикардо Баеза-Йейтс, Бертье Рибейро-Нето. Современный информационный поиск. 1999. ISBN  0-201-39829-X.
  12. bitap.py - Реализация алгоритма Bitap на Python с модификациями Wu-Manber.