Алгоритм бітап (також відомий як shift-or, shift-and) - алгоритм приблизного пошуку рядків. Алгоритм визначає, чи містить заданий текст підрядок, «приблизно рівний» заданому зразку, де приблизна рівність визначається через відстань Левенштейна - якщо підрядок і зразок перебувають у межах заданої відстані k один від одного, алгоритм вважає їх рівними. Алгоритм починає з попереднього обчислення набору бітових масок, що містять по одному біту для кожного елемента зразка. Далі основну частину роботи він виконує за допомогою побітових операцій, які є надзвичайно швидкими.
Алгоритм бітап, мабуть, найбільш відомий як один з базових алгоритмів утиліти Unix agrep, написаної Уді Манбером, Сунь Ву та Буррою Гопалом. В оригінальній статті Манбера і Ву наведено розширення алгоритму для нечіткого пошуку за довільними регулярними виразами.
Через структури даних, яких потребує алгоритм, він працює найкраще на зразках, довжина яких не перевищує певної сталої (зазвичай - довжини машинного слова відповідної машини), а також віддає перевагу вхідним даним над невеликим алфавітом. Проте після того, як його реалізовано для заданого алфавіту та довжини слова m, його час роботи є повністю передбачуваним - алгоритм виконується за O(mn) операцій незалежно від структури тексту чи зразка.
Алгоритм бітап для точного пошуку рядків винайшов Балінт Демелкі 1964 року, а 1977 року його розширив Р. К. Ш'ямасундар. Пізніше, 1989 року, його заново винайшли Рікардо Баеса-Єйтс та Гастон Гонне (один з розділів докторської дисертації першого автора), розширивши його для підтримки класів символів, символів підстановки та невідповідностей. 1991 року Манбер і Ву розширили його для обробки також вставок і видалень (повноцінний нечіткий пошук рядків). Згодом, 1996 року, цей алгоритм удосконалили Баеса-Єйтс і Наварро.__TOC__
Точний пошук
Алгоритм бітап для точного пошуку рядка у загальному вигляді має такий псевдокод:
algorithm bitap_search is input: text — рядок (текст). pattern — рядок (зразок). output: рядок m := length(pattern)
if m = 0 then return text
/* Ініціалізуємо бітовий масив R. */ R := new array[m+1] of bit, спочатку всі 0 R := 1
for i := 0; i < length(text); i += 1 do /* Оновлюємо бітовий масив. */ 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
Бітап вирізняється серед інших відомих алгоритмів пошуку рядків тим, що природно відображається на прості побітові операції, як у наведеній нижче реалізації. Зверніть увагу, що в цій реалізації, всупереч інтуїції, кожен біт зі значенням нуль означає збіг, а кожен біт зі значенням 1 — незбіг. Той самий алгоритм можна записати з інтуїтивною семантикою для 0 та 1, але в такому разі у внутрішній цикл довелося б додати ще одну інструкцію, яка встановлює молодший біт в 1. У цій реалізації ми користуємося тим, що зсув значення вліво заповнює молодші біти нулями — а це саме та поведінка, яка нам потрібна.
У мовах на кшталт C для перетворення умови «поточний символ тексту дорівнює символу зразка» на побітові операції потрібно CHAR_MAX додаткових бітових масок — по одній на кожен можливий символ, тому класичні реалізації працюють краще на малих алфавітах. У наведеній нижче реалізації мовою Perl маски зберігаються в хеші, тож маски створюються лише для символів, які справді трапляються у зразку. Завдяки цьому обмеження на розмір алфавіту зникає, і алгоритм однаково працює з будь-яким Unicode-текстом, зокрема кирилицею. Обмеження на довжину зразка залишається: вона не може перевищувати розрядності цілого числа (63 біти для 64-бітного Perl).
use strict; use warnings; use utf8;
# Повертає позицію першого збігу (нумерація з нуля) або -1, якщо збігу немає. sub bitap_search { my ($text, $pattern) = @_;
my $m = length($pattern);
if ($m == 0) { return 0; # порожній зразок — збіг на початку тексту
if ($m > 63) { die "Зразок задовгий!\n";
# Ініціалізуємо бітові маски зразка. # Для символів, яких немає у зразку, маска дорівнює ~0 (всі одиниці). my %pattern_mask; my @pattern_chars = split //, $pattern;
for my $i (0 .. $m - 1) { my $char = $pattern_chars[$i]; $pattern_mask{$char} //= ~0; $pattern_mask{$char} &= ~(1 << $i);
# Ініціалізуємо бітовий масив R. my $R = ~1;
my @text_chars = split //, $text;
for my $i (0 .. $#text_chars) { my $mask = $pattern_mask{ $text_chars[$i] } // ~0;
# Оновлюємо бітовий масив. $R |= $mask; $R <<= 1;
if (($R & (1 << $m)) == 0) { return $i - $m + 1;
return -1; }
Приклад роботи
Розгляньмо пошук зразка «аба» (m = 3) у тексті «кабаба». Спершу обчислюються маски символів зразка (показано 4 молодші біти; біт i дорівнює нулю, якщо символ стоїть на позиції i зразка):
маска(«а») = 1010 — нулі в бітах 0 та 2, бо «а» стоїть на позиціях 0 та 2 зразка; маска(«б») = 1101 — нуль у біті 1; маска будь-якого іншого символу = 1111.
Далі текст читається символ за символом. На кожному кроці виконується R |= маска; R <<= 1. Збіг знайдено, коли біт 3 (біт з номером m) масиву R стає нулем:
+ Стан бітового масиву R під час пошуку «аба» в «кабаба» (0 — збіг) Крок Символ тексту Маска символу R після оновлення Біт 3 Результат 0 — — 1110 1 початковий стан 1 к 1111 1110 1 2 а 1010 1100 1 збігся префікс «а» 3 б 1101 1010 1 збігся префікс «аб» 4 а 1010 0100 0 збіг з позиції 1
На кроці 4 біт 3 дорівнює нулю, тому алгоритм повертає позицію 4 − 3 = 1: підрядок «аба» починається з другого символу тексту «кабаба» (нумерація з нуля).
Нечіткий пошук
Щоб виконувати нечіткий пошук рядків за допомогою алгоритму бітап, бітовий масив R необхідно розширити до другого виміру. Замість одного масиву R, що змінюється вздовж тексту, ми тепер маємо k окремих масивів R1..k. Масив Ri зберігає представлення префіксів зразка pattern, які збігаються з будь-яким суфіксом поточного рядка з i або меншою кількістю помилок. У цьому контексті «помилкою» може бути вставка, видалення або заміна; докладніше про ці операції див. відстань Левенштейна.
Наведена нижче реалізація виконує нечіткий пошук (повертає перший збіг із не більш ніж k помилками). Проте вона враховує лише заміни, а не вставки чи видалення — інакше кажучи, відстань Геммінга k. Як і раніше, семантика 0 та 1 обернена щодо їхніх звичних значень.
use strict; use warnings; use utf8;
# Повертає позицію першого збігу з не більш ніж $k помилками-замінами # (нумерація з нуля) або -1, якщо збігу немає. sub bitap_fuzzy_search { my ($text, $pattern, $k) = @_;
my $m = length($pattern);
if ($m == 0) { return 0;
if ($m > 63) { die "Зразок задовгий!\n";
# Ініціалізуємо бітові маски зразка. my %pattern_mask; my @pattern_chars = split //, $pattern;
for my $i (0 .. $m - 1) { my $char = $pattern_chars[$i]; $pattern_mask{$char} //= ~0; $pattern_mask{$char} &= ~(1 << $i);
# Ініціалізуємо масиви R: по одному на кожну кількість помилок 0..k. my @R; for my $d (0 .. $k) { $R[$d] = ~1;
my @text_chars = split //, $text;
for my $i (0 .. $#text_chars) { my $mask = $pattern_mask{ $text_chars[$i] } // ~0;
# Оновлюємо бітові масиви. my $old_R_prev = $R;
$R |= $mask; $R <<= 1;
for my $d (1 .. $k) { my $tmp = $R[$d]; # Враховуємо лише заміни. $R[$d] = ($old_R_prev & ($R[$d] | $mask)) << 1; $old_R_prev = $tmp;
if (($R[$k] & (1 << $m)) == 0) { return $i - $m + 1;
return -1; }
Наприклад, виклик bitap_fuzzy_search("собака", "сабака", 1) поверне 0: рядки відрізняються однією заміною, що вкладається в дозволену кількість помилок k = 1.
Посилання та джерела Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964. Bálint Dömölki, A universal compiler system based on production rules, BIT Numerical Mathematics, 8(4), pp 262–275, 1968. R. K. Shyamasundar, Precedence parsing using Dömölki's algorithm, International Journal of Computer Mathematics, 6(2) pp 105–114, 1977. Ricardo Baeza-Yates. «Efficient Text Searching.» PhD Thesis, University of Waterloo, Canada, May 1989. Udi Manber, Sun Wu. «Fast text searching with errors.» Technical Report TR-91-11. Department of Computer Science, University of Arizona, Tucson, June 1991. (gzipped PostScript) 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 — вільна реалізація, що показує, як алгоритм можна легко розширити для більшості регулярних виразів. На відміну від коду вище, вона не обмежує довжину зразка. Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern Information Retrieval. 1999. . bitap.py — реалізація алгоритму бітап мовою Python з модифікаціями Ву — Манбера.