Simultaneous search for several binary patterns in a stream with finite-state automaton.pdf Рассматриваемую задачу можно сформулировать так. Имеем двоичную последовательность (поток данных) и набор булевых векторов (далее называемых шаблонами) V1, V2, ... , длин k1, k2, ... , kn соответственно. Необходимо найти вхождения всех шаблонов в последовательность. В работе предлагается строить конечный автомат, на вход которого подаются биты или байты потока, а на выходе получается информация о найденных в потоке шаблонах. На каждый бит или байт потока автомат совершает две простейших операции: изменение состояния по таблице переходов и определение выхода по таблице выходов. При этом автомат осуществляет одновременный поиск произвольного количества шаблонов любых длин. Опишем алгоритм построения битового автомата. Входной алфавит автомата - {0,1}. Выходной алфавит - множество булевых векторов {0,1}n, где каждому биту сопоставлен шаблон из набора, и этот бит принимает значение 1, если шаблон закончился в текущей позиции. Строится автомат по индукции. Сначала вводится нулевое состояние, соответствующее ситуации, когда не найден ни один префикс ни одного шаблона. Затем алгоритм поочерёдно обрабатывает все состояния условной подачей на вход автомата 0 и 1, попутно сохраняя новые полученные состояния и строя таблицы переходов и выходов автомата. Обработав таким образом все состояния автомата, получаем таблицы переходов и выходов, а также таблицу соответствия номеров состояний их описаниям: состоянию s сопоставляется набор Ts = (Ts1, Ts 2,... , Ts,n), где Ts,j содержит множество длин найденных префиксов шаблона номер j. Обозначим 1-й бит вектора V через V[1], биты нумеруем с нуля. В выходном векторе F бит F [j - 1] соответствует j-му шаблону. Алгоритм построения битового поискового автомата Вход: набор булевых векторов (шаблонов) V1, V2, ... , Vn, их длины ki, k2, ..., kn Выход: функции переходов - и выходов ^ поискового автомата 1. Запоминаем начальное состояние T0 := (0, 0,... 0), s := 0. 2. Обрабатываем состояние s условной подачей нуля и единицы. Подаваемый бит обозначим b. Сначала зададим b := 0. 3. Строим новое состояние T, в которое автомат должен перейти после подачи бита b в состоянии Ts, и соответствующий выходной символ - вектор F; сначала полагаем F := 00 ... 0 = 0n. Для каждого j от 1 до n: 3.1. Зададим A := Ts,j U {0}, Bj := 0. 3.2. Для всех I е A если b = Vj[1], то B, := B, U { + 1}. Теперь множество Bj содержит длины всех найденных префиксов вектора Vj после подачи бита b в состоянии Ts. 3.3. Если kj е Bj, то вектор Vj найден; полагаем Bj := Bj \ {/ + 1}, F[j - 1] := 1. 4. Получили набор T := (B*, B2,... , Bn), описывающий следующее состояние, и выходной символ автомата - вектор F. Ищем набор T среди имеющихся наборов T0,... ,TS. Если нашли, что T = Th, то присваиваем s' := h; если такого состояния ещё нет, то добавляем его в таблицу в новую ячейку. Пусть номер этой ячейки s'. Тогда состояние Ts = T. 5. Запоминаем - (s,b) := s',

Скачать электронную версию публикации