Accelerating Knuth-Morris-Pratt String Matching over LZ77 Compressed Text
Accelerating Knuth-Morris-Pratt String Matching over LZ77 Compressed Text
复制标题
DOI：
10.1109/dcc50243.2021.00070
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Xiuwen Sun;Di Wu;Da Mo;Jie Cui;Hong Zhong
中科院分区：
文献类型：
--
作者：
Xiuwen Sun;Di Wu;Da Mo;Jie Cui;Hong Zhong
为了对海量数据进行全面分析或高效检索，字符串匹配作为网络流量检测应用和文本编辑器的核心技术被广泛应用。然而，越来越多的压缩文本挑战字符串匹配，以实现高速处理。在本文中，我们提出了KCM，一个快速的Knuth-Morris-Pratt为基础的字符串匹配方法在LZ 77压缩文本。它利用扫描过程中收集的启发式信息来跳过应该扫描的字符。在我们的评估与真实的流量，KCM跳过90%以上的压缩文本，这几乎接近理论上限。它可以实现1.61 Gbps的吞吐量，比经典的字符串匹配提高1.87倍。
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.