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

Я пытаюсь обвести голову вокруг алгоритма 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].

То, что я не понимаю, - это битовая реализация этого. Официальная статья, подробно описывающая этот алгоритм, в основном излагает это, но я не могу представить, что должно продолжаться. Спецификация алгоритма - это только первые 2 страницы бумаги, но я выделим важные части:

Вот версия с битрейтом:

enter image description here

Здесь T [текст] для строки поиска:

enter image description here

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

enter image description here

В частности, я не понимаю, что означает таблица T, и причина OR записи в нее с текущим состоянием.

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

Ответы

Ответ 1

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

Бит n из T[x] равен 0, если x появляется в позиции n или 1, если это не так.

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

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

  [start]
1 1 1 1 1

По мере того, как мы потребляем символы, пытающиеся соответствовать, состояние сдвигается влево (которое сдвигает ноль в до нижнего бита, бит 0) и OR-ed с записью таблицы для текущего символа. Первый символ - a; сдвиг влево и OR-ing в 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 в той же позиции, сообщая нам, что видение a 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 хорош, если в начале матча было четыре символа. Дело в том, что a 0 сделал все возможное, чтобы верхний бит означал, что у нас есть соответствие.

Ответ 2

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

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

Пусть имеет 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 внутри тех же границ.

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