String сходство: как именно работает Bitap?

Question

Я пытаюсь обвести голову вокруг алгоритма Bitap, но у меня возникли проблемы с пониманием причин шагов алгоритма.

Я понимаю основную предпосылку алгоритма, который (поправьте меня, если я ошибаюсь):

Two strings:  PATTERN (the desired string) 
       TEXT (the String to be perused for the presence of PATTERN) 

Two indices:  i (currently processing index in PATTERN), 1 <= i < PATTERN.SIZE 
       j (arbitrary index in TEXT) 

Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j], S(0) = 1 

В английском выражении PATTERN.substring(0,i) соответствует подстроку TEXT, если предыдущий подстрока PATTERN.substring(0, i-1) был успешно сравнен и символ в PATTERN[i] совпадает с символом в TEXT[j].

То, что я не понимаю, является реализацией бит-сдвига. The official paper detailing this algorithm basically lays it out, но я не могу представить, что должно продолжаться. Спецификация алгоритма только первые 2 страницы бумаги, но я выделю важные части:

Вот бит смены версии концепции:

Вот T [текст] для поиска образца строки:

А вот след алгоритма.

В частности, я не понимаю, что табличные T, Значит и причина OR ИНГ запись в него с текущим состоянием.

Я был бы признателен, если кто-нибудь может помочь мне понять, что именно происходит

Answer 1

Извините за не позволяя кому-либо ответить, но я уверен, что я понял это сейчас.

Концепция, необходимая для обобщения алгоритма, представляет собой представление состояний соответствия (определенных в исходном столбце) в двоичном формате. Статья в оригинальной публикации объясняет это формально; Я попробую свои силы при таком разговоре:

Давайте будем иметь STR, который представляет собой строку, созданную с символами данного алфавита.

Представляем STR с набором двоичных цифр: STR_BINARY. Алгоритм требует, чтобы это представление было обратным (поэтому первая буква соответствует последней цифре, вторая буква со второй до последней цифрой и т. Д.).

Предположим, что RANDOM относится к строкам со случайными символами из того же алфавита STR создан.

В STR_BINARY, а 0 при заданном индексе указывает на то, что, RANDOM матчей STR от STR[0] к

STR[(index of letter in STR that the 0 in STR_BINARY corresponds to)]. Пустые пробелы считаются совпадениями. A 1 указывает, что RANDOM не соответствует STR внутри тех же границ.

Алгоритм упрощается, как только это будет понято.

Answer 2

T немного сбивает с толку, потому что вы, как правило, количество позиций в рисунка слева направо:

0 1 2 3 4 
a b a b c 

... в то время как биты обычно нумеруются справа налево.

Но писать образец назад над битами проясняет:

 
    bit: 4 3 2 1 0 

     c b a b a 
T[a] = 1 1 0 1 0 

     c b a b a 
T[b] = 1 0 1 0 1 

     c b a b a 
T[c] = 0 1 1 1 1 

     c b a b a 
T[d] = 1 1 1 1 1 

Бит п из T[x] является 0 если x появляется в положении п или 1, если он не делает.

Эквивалентно, вы можете думать об этом, как говорят, что если текущий символ во входной строке является x, и вы видите 0 в положении п из T[x], то вы только возможно, может быть соответствие шаблону, если начался матч n Персонажи ранее.

---

Теперь к процедуре сопоставления. A 0 в бит n состояния означает, что мы начали сопоставлять шаблон n символов назад (где 0 - текущий символ). Первоначально ничего не соответствует.

[start] 
1 1 1 1 1 

Как мы потребляем персонажи пытаются соответствовать, состояние сдвигается влево (который сдвигает ноль в на нижний бит, бит 0) и OR-е изд с записью в таблице для текущего символа. Первый символ: a; сворачивает налево и ИЛИ-в T[a] дает:

 a 
1 1 1 1 0 

0 бит, который был перемещен в сохраняется, так как текущий характер a может начать матч картины. Для любого другого символа бит был бы установлен на 1.

Тот факт, что бит 0 состояния находится сейчас 0, означает, что мы начали сопоставлять шаблон по с текущим символом; Продолжая, мы получим:

 a b 
1 1 1 0 1 

... потому что 0 немного сдвинута влево - думать о нем, как о том, что мы начали соответствие шаблону 1 символ назад - и T[b] имеет в том же положении, в 0, рассказывающий что мы видим b в текущей позиции хорошо, если мы начали сопоставлять 1 символ назад.

a b d 
1 1 1 1 1 

d не может сравниться нигде; все биты возвращаются к 1.

a b d a 
1 1 1 1 0 

Как и прежде.

a b d a b 
1 1 1 0 1 

Как и прежде.

b d a b a 
1 1 0 1 0 

a хорошо, если матч начался либо 2 символов назад или на текущий характер.

d a b a b 
1 0 1 0 1 

b хорошо, если матч начался 1 или 3-х символов назад. 0 в бите 3 означает , что мы почти соответствовали всему узору ...

a b a b a 
1 1 0 1 0 

... но следующий символ a, который не хорошо, если матч начался 4-х символов назад. Однако более короткие совпадения могут быть хорошими.

b a b a b 
1 0 1 0 1 

Все еще выглядит хорошо.

a b a b c 
0 1 1 1 1 

Наконец, cявляется хорошо, если матч начался 4-х символов раньше. Тот факт, что a 0 довел до конца, означает, что мы имеем совпадение.