一种串匹配算法的加速方法及装置

摘要

本发明提出一种串匹配算法的加速方法及装置，该方法包括构造基本转换规则与交叉转换规则，根据缓存策略函数确定状态缓存寄存器中的状态S_c1与S_c2，判断当前状态S_i在基本转换规则和n步交叉转换规则中是否存在接收当前字符c的转换规则，根据相应转换规则，将字符c进行转换。本发明通过增加状态缓存组件和选通电路，如寄存器组和多路选通器，在串匹配过程中动态生成转换规则，实现了串匹配算法的加速，同时能够消除传统串匹配算法中需存储的大量转换规则，降低生成状态机的规模，提高串匹配算法的执行速度。

主权项

一种串匹配算法的加速方法，其特征在于，包括构造基本转换规则与交叉转换规则，根据缓存策略函数确定状态缓存寄存器中的状态S_c1与S_c2，判断当前状态S_i在基本转换规则和n步交叉转换规则中是否存在接收当前字符c的转换规则，如果存在对应的转换规则，则应用对应的转换规则，并跳到下一个状态S_k，应用基本转换规则或n步交叉转换规则，同时按缓存策略函数更新缓存寄存器中的状态S_c1与S_c2；否则，将被缓存的状态S_c2取出，并以状态S_c2为当前状态，在基本转换规则与n步交叉转换规则中寻找接收当前字符c的转换规则；如果寻找到对应的转换规则,则跳转到对应的下一个状态S_j,并应用2步交叉转换规则；否则，将被缓存的状态S_c1取出，并以状态S_c1为当前状态在基本转换规则与n步交叉转换规则中寻找接收当前字符c的转换规则；如果寻找到对应的转换规则，则跳转到对应的下一个状态S_j,并应用1步交叉转换规则；否则，判断初始状态S₀是否接收字符c；如果接收字符c，则跳到相应状态，应用重启转换规则；否则，跳转到初始状态S₀，用于失败转换规则。