Geodesic
Fuzzy binary search problem: approach based on finite state machines
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 117-122.

Voir la notice de l'article provenant de la source Math-Net.Ru

This article deals with the fuzzy search of binary patterns in a binary data stream. Fuzzy entry of a pattern is the entry of a vector with short Hamming distance to the pattern. An approach based on finite state machines (FSM) is proposed along with the building algorithm. The FSM is further called SearchFSM. The building algorithm accepts a set of patterns as the input. For every pattern, the maximum Hamming distance is provided. The patterns may be partially defined. The SearchFSM accepting bits one-by-one is called bit-SearchFSM, but it is possible to build byte-SearchFSM accepting groups of bits at once. The octet-SearchFSM and nibble-SearchFSM are described and their performance is examined. The bit-SearchFSM is also examined along with the standard approach based on a shift register. There are estimates for the quantity of states and required memory in SearchFSM of some kinds.
Keywords: Search FSM, fuzzy search, binary search, sync search, string matching, KMP-algorithm, Aho–Corasick algorithm. 
@article{PDMA_2018_11_a36,
     author = {I. V. Pankratov},
     title = {Fuzzy binary search problem: approach based on finite state machines},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {117--122},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a36/}
}
TY  - JOUR
AU  - I. V. Pankratov
TI  - Fuzzy binary search problem: approach based on finite state machines
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 117
EP  - 122
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a36/
LA  - ru
ID  - PDMA_2018_11_a36
ER  - 
%0 Journal Article
%A I. V. Pankratov
%T Fuzzy binary search problem: approach based on finite state machines
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 117-122
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a36/
%G ru
%F PDMA_2018_11_a36
I. V. Pankratov. Fuzzy binary search problem: approach based on finite state machines. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 117-122. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a36/

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

[2] Pankratov I. V., “Odnovremennyi poisk neskolkikh dvoichnykh shablonov v potoke s pomoschyu konechnogo avtomata”, Prikladnaya diskretnaya matematika, 2014, no. 2(24), 119–125

[3] 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

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