基于SSE指令集的串匹配算法优化

摘要

串匹配是计算机研究领域的经典问题之一,在网络安全、计算生物学、信息检索等领域发挥着关键的作用。其中,基于位并行的串匹配算法所需存储空间小、匹配速度快,但由于受到机器字的限制,只适合小规模的串匹配。基于SSE系列指令集对经典的位并行算法Shift-And、BNDM进行了优化,优化算法利用SSE指令集提供的128住大位宽寄存器,将多个状态向量打包到SSE寄存器上,并通过SSE的位操作指令状态向量进行更新。在随机数据和真实数据上的测试结果显示,优化算法的匹配速度达到原算法的2倍以上。