Fast pattern matching method for a bitstream

Zavadskyi, I. O. (2020). Fast pattern matching method for a bitstream. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics(4), 36–39. https://doi.org/10.17721/1812-5409.2020/4.5

A family of algorithms for fast pattern matching in a bitstream is described. A bitstream is assumed to be stored in a memory and divided into bytes and machine words. The proposed algorithms are based on RZ-family of algorithms for fast pattern matching in a 256-ary text and inherit such their properties as ‘1.5-byte read’, double skip loop, right-to-left text processing as well as a special technique of multiple sliding windows. Beyond that, the new algorithms provide longer average shifts than the best known Binary Faro-Lecroq algorithm and more efficient technique of match checking. Applied to a text close to random, our algorithms outperform all known analogues for all pattern lengths from 20 up to 500.Key words: pattern matching, Faro-Lecroq, fast search, bitstream, search window.Pages of the article in the issue: 36 - 39Language of the article: Ukrainian