Одна из мелочных идей, которые обычно лезут в голову в Макдональдсе за утренней чашкой кофе.
Алгоритм Демелки-Proteus
У нас есть образец p=aba и текст t=babbaabbababb - мы должны создать массив масок, размером с алфавит, где для каждой буквы нулевым битом обозначены присутвие буквы а конкретном месте образца: a={010}, b={101}. Далее мы обозначим начальное состояние s0=111 конечного автомата, где число едениц равно количеству букв в образце. Далее с каждым шагом алгоритма мы сдвигаем состояние вправо (замещая левую еденицу нулём), и накладываем по 'or' маску которая соотвествует очередной букве заданного текста. В данном примере состояния будут развиваться так:
| состояние | буква | маска буквы | новое состояние |
| 111 | b | 101 | 011|101=111 |
| 111 | a | 010 | 011|010=011 |
| 011 | b | 101 | 001|101=101 |
| 101 | b | 101 | 010|101=111 |
| 111 | a | 010 | 011|010=011 |
| 011 | a | 010 | 001|101=011 |
| 011 | b | 101 | 001|101=101 |
| 101 | b | 101 | 010|101=111 |
| 111 | a | 010 | 011|010=011 |
| 011 | b | 101 | 001|101=101 |
| 101 | a | 010 | 010|010=010 |
Крайний правый бит равный нулю - означает то что образец в данной позиции полностью совпал с текстом. Т.е. алгоритм работает очень просто мы свигаем состояние право добавляя нулевой бит слева, и по дороги включаем некоторые из битов. И нулевой бит доходит живым до крайней правой позиции, только если образец совпадал с текстом. Едиственный недостаток в том что количество битов в переменной ограничено и слишком большой образец туда не влезет. Для длинных образцов можно разместить состояние в нескольких переменных или искать только начало образца, а остаток сравнивать вручную (если правда некоторые мысли как решать эти проблемы, но они пока в зачатке).
Я просто решил сделать так, чтобы битовый массив отслеживал не отдельные буквы алфавита, а целые последовательности букв или отдельные части образца. Итак один из способов который мне приходит на ум, разбить образец на отрезки которые не повторяют друг друга. И представить что каждый отрезок это отдельная буква алфавита. Т.е. разделив образец на непересекающиеся отрезки можно построить дерево ключей, каждый лист которого кончается соотвествующей маской. Даном случае я разделяю образец по стыкам. Для образца P[1..n], стыком считается каждая позиция i удовлетворяющая условию P[i]=P[1] с условием что P[i-1]≠P[1]. Для примера образец abcabaaabab - таким образом распадётся на отрезки abc ab aaab ab. Для удобства и быстрой работы все найденые образцы хорошо пронумеровать и объеденить в дерево:
Корень всегда начинается с одной буквы, поэтому его можно просто отрезать. К тому же перед буквой P[1] образец обычно кончается, поэтому будет меньше хлопот. Таким образом, если я заменю все отрезки их номерами то abcabaaabab превратиться в 3212, а таблица масок будет выглядеть так:
| aaab | 1101 |
| ab | 1010 |
| abc | 0111 |
Любые незнакомые последовательности, должны сбрасывать состояние в еденицы. Для корректной работы системы необходимо так же отслеживать ситуацию, когда начальный отрезок образца является частью одного из других отрезков образца, так отдельного внимания требует конечный отрезок, это не особо сложно (пока не буду рассказывать о красоте сопуствующих технических приёмов). Для этого можно попросту пометить на дереве те листья которые кроме текущей позиции влияют и на первый или последний отрезок. Не трудно показать что оценка скорости поиска линейна, и данные для поиска можно так же подготовить за линейное время, даже если вы прибегаете к наивному способу построения дерева и применять любые процедуры к дереву, потому как сумарная длина путей дерева будет не больше чем длина образца. В моей реализации одинаковые начальные буквы отрезков не хранятся явно, а обозначены числом одинаковых букв. Т.е. в этоге дерево должно иметь следующий вид:
А сам алгоритм поиска можно приблизительно описать так (до начала допустим что дерево уже построено):
Кстати первые два пункта хороший повод для машинной оптимизации. Насчёт отрезков из которых состоит дерево, вы можете попробовать придумать другой способ разбиения на отрезки, может получится что-то интересное.
В таком случае вместо масок можно использовать номера битов. Или вообще выбрать способ кодирования: номера обозначаюшие интервалы битов; обрезки масок; коды хафмана. В целом вычисления значительно выростут, но если образец очень большой и повторяющихся отрезков в образце мало, то прирост скорости будет значительный.
p.s. думаю что я пока сделал не все что хотел, поэтому возможно будет продолжение.
Оригинальный битовый алгоритм Демелки
Тестовая версия Демелки-Proteus - без дерева и требует буфер для части текста.
(c) Proteus 2005 (icq:133575351)
