Fuzzy binary search problem: approach based on finite state machines

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

Authors

References