Pattern matching by the terms of cache memory limitations

Zavadskyi, I. O. (2019). Pattern matching by the terms of cache memory limitations. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics(3), 56–59. https://doi.org/10.17721/1812-5409.2019/3.8

A few known techniques of exact pattern matching, such as 2-byte read, skip loop, and sliding search windows, are improved and applied to pattern matching algorithms, performing over 256-ary alphabets. Instead of 2-byte read, we offer “1.5-byte read”, i.e. reading more than 8 but less than 16 bits of two sequential bytes of a text at each iteration of a search loop. This allows us to fit the search table into L1 cache memory, which significantly improves the algorithm performance. Also, we introduce the so-called double skip loop instead of single one, resolve problems caused by endianness of a machine, and adopt the sliding windows technique to our algorithms. The experimental results averaged over 500 runs of algorithms on 40 different computers show that our algorithms outperform all other tested methods for all tested pattern lengths.Key words: pattern matching, Boyer-Moore-Horspool, fast search, text search, sliding windows.Pages of the article in the issue: 56 - 59Language of the article: Ukrainian