Geodesic
Simultaneous search for several binary patterns in a stream with finite-state automaton
Prikladnaâ diskretnaâ matematika, no. 2 (2014), pp. 119-125
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The task under consideration in this paper is to search for binary subsequencies in a data stream. The article offers the finite automaton able to search for a set of binary vectors simultaneously performing only two operations per every bit or even byte of the data stream. Increasing the number of searched vectors causes a slower increase in memory usage compared to overall vector's length growth, and computational complexity does not increase at all. The automaton is described by the transition and output tables. Estimates of the size of the automaton's tables are given. Known approaches to the problem are discussed. There is a possibility to generalize the automaton building algorithm to search for partially defined Boolean patterns, but the amount of required memory may be greater than the estimate found in the paper.
Keywords: bit subsequences search, synchronization, string matching, Knuth–Morris–Pratt algorithm, Aho–Corasick string matching. 
@article{PDM_2014_2_a10,
     author = {I. V. Pankratov},
     title = {Simultaneous search for several binary patterns in a~stream with finite-state automaton},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {119--125},
     year = {2014},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_2_a10/}
}
TY  - JOUR
AU  - I. V. Pankratov
TI  - Simultaneous search for several binary patterns in a stream with finite-state automaton
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 119
EP  - 125
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_2_a10/
LA  - ru
ID  - PDM_2014_2_a10
ER  - 
%0 Journal Article
%A I. V. Pankratov
%T Simultaneous search for several binary patterns in a stream with finite-state automaton
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 119-125
%N 2
%U http://geodesic.mathdoc.fr/item/PDM_2014_2_a10/
%G ru
%F PDM_2014_2_a10
I. V. Pankratov. Simultaneous search for several binary patterns in a stream with finite-state automaton. Prikladnaâ diskretnaâ matematika, no. 2 (2014), pp. 119-125. http://geodesic.mathdoc.fr/item/PDM_2014_2_a10/

[1] Agibalov G. P., Oranov A. M., Lektsii po teorii konechnykh avtomatov, Izd-vo Tom. un-ta, Tomsk, 1984, 185 pp. | MR

[2] Knuth D. E., Morris J. H. Jr., Pratt V. R., “Fast pattern matching in strings”, SIAM J. Comput., 6:2 (1977), 323–350 | DOI | MR | Zbl

[3] Aho A. V., Corasick M. J., “Efficient string matching: An aid to bibliographic search”, Commun. ACM, 18:6 (1975), 333–340 | DOI | MR | Zbl