Accelerating Knuth-Morris-Pratt String Matching over LZ77 Compressed Text
Xiuwen Sun, Di Wu, Da Mo, Jie Cui, Hong Zhong · 2021
For comprehensive analyzing or efficient searching from massive data, string matching is widely used as a core technique of the network traffic detection applications and text editors. However, the increasing compressed text challenges string matching to achieve high-speed processing. In this paper, we propose KCM, a fast Knuth-Morris-Pratt based string matching method over LZ77 compressed text. It leverages the gathered heuristic information during scanning to skip the characters that should have been scanned. In our evaluation with real traffic, KCM skips more than 90% compression text, which nearly approaches the theoretical upper bound. It can achieve 1.61 Gbps throughput and boost 1.87 times than the classic string matching.