陈 瑞 顾乃杰 叶 鸿

(中国科学技术大学计算机科学与技术学院 安徽 合肥 230027)(中国科学技术大学安徽省计算与通信软件重点实验室 安徽 合肥 230027)

0 引 言

串匹配是在已知字符序列(文本串)中按照一定的匹配条件搜索给定字符序列(模式串)集合中元素出现位置的搜索问题，是生物信息学、信号处理和信息检索等方向的核心问题，在涉及字符处理相关领域中具有广泛的应用[1]。随着信息时代数据的高速增长，如何快速高效地处理大规模数据的串匹配问题是当前研究的重点。串匹配问题包括多模式匹配和单模式匹配。其中，多模式匹配的研究大多根据自动机原理，其经典算法包括AM算法[2]、AC算法[3]、FS算法[4]等。单模式匹配是研究串匹配问题的基础，且其他模式匹配算法均由单模式匹配扩展而来，应用领域也最为广泛，已经成为涉及文本和符号处理领域应用的基本组件。因此，研究精确单模式串匹配问题有重要意义。

另一方面，随着多媒体技术的飞速发展，DSP处理器以其低功耗和高性能等特点在信号处理和图像检索等领域有着重要的应用。高性能DSP处理器不仅拥有强大的计算能力，还具有多种先进技术，单指令流多数据流(Single Instruction Multiple Data,SIMD)、超长指令字(Very Long Instruction Word,VLIW)等特殊的硬件结构使得字符串匹配算法在DSP上得以并行处理。本文提出一种基于魂芯DSP的精确单模式位并行串匹配算法，并在平台上进行仿真实验。

单模式串匹配算法众多，代表性的有按照前缀匹配规则的KMP算法[5]、Shift-Or/And(SO/SA)算法[6]和按照后缀匹配规则的Horspool算法[7]和SBNDM2算法[8]。……