Рассматривается задача поиска булевых векторов в потоке данных. Предлагается метод построения конечного автомата, который ищет одновременно несколько векторов, совершая только две простые операции на каждый бит или группу битов, например байт данных. При этом с увеличением количества искомых шаблонов объём требуемой памяти растёт медленнее, чем суммарная длина шаблонов, а трудоёмкость не изменяется совсем. Приводятся оценки размеров таблиц переходов и выходов автомата. Рассматриваются известные подходы к решению этой задачи. Есть возможность обобщить алгоритм построения поискового автомата на поиск не полностью определённых булевых векторов, однако в этом случае объём требуемой памяти может превышать найденную в данной работе оценку.
Скачать электронную версию публикации
Загружен, раз: 64
- Title Одновременный поиск нескольких двоичных шаблонов в потоке с помощью конечного автомата
- Headline Одновременный поиск нескольких двоичных шаблонов в потоке с помощью конечного автомата
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(24)
- Date:
- DOI
Ключевые слова
поиск битовых последовательностей, синхропосылка, поиск подстроки, КМП-поиск, алгоритм Ахо - КорасикАвторы
Ссылки
Агибалов Г. П., Оранов А. М. Лекции по теории конечных автоматов. Томск: Изд-во Том. ун-та, 1984. 185 с.
Knuth D. E., Morris J.H.Jr., and Pratt V.R. Fast pattern matching in strings // SIAM J. Comput. 1977. No. 6(2). P. 323-350.
AhoA.V. and CorasickM.J. Efficient string matching: An aid to bibliographic search // Commun. ACM. 1975. No. 18(6). P. 333-340.
Одновременный поиск нескольких двоичных шаблонов в потоке с помощью конечного автомата | Прикладная дискретная математика. 2014. № 2(24).
Скачать полнотекстовую версию
Загружен, раз: 202