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