公开(公告)号：CN110321463B

公开(公告)日：2022-01-21

申请号：CN201910466313.9

申请日：2019-05-31

Applicant: 中国科学院计算技术研究所

Inventor： 黄昆 ,  陈雪琳 ,  谢高岗

IPC: G06F16/903

Abstract: 本发明提出一种字符串匹配方法，包括：首先，构建一个全局迁移表，存储同一输入字符的相同目的状态的迁移边；其次，构建每个状态的本地迁移表，针对每个输入字符，存储与全局迁移表中不同目的状态的迁移边，并采用比特位图进一步压缩本地迁移边表。全局迁移表的构建时间复杂度为O(M×N)，M表示DFA状态总数，N表示字母表中唯一字符个数，因此RDFA比已有算法的构建时间少；同时，全局迁移表减少了大量冗余迁移边，RDFA显著压缩DFA存储空间；针对每个读入字符，RDFA仅需要查找当前状态的本地迁移表和全局迁移表，从而提高字符串匹配吞吐量。

公开(公告)号：CN110321463A

公开(公告)日：2019-10-11

申请号：CN201910466313.9

申请日：2019-05-31

Applicant: 中国科学院计算技术研究所

Inventor： 黄昆 ,  陈雪琳 ,  谢高岗

IPC: G06F16/903

Abstract: 本发明提出一种字符串匹配方法，包括：首先，构建一个全局迁移表，存储同一输入字符的相同目的状态的迁移边；其次，构建每个状态的本地迁移表，针对每个输入字符，存储与全局迁移表中不同目的状态的迁移边，并采用比特位图进一步压缩本地迁移边表。全局迁移表的构建时间复杂度为O(M×N)，M表示DFA状态总数，N表示字母表中唯一字符个数，因此RDFA比已有算法的构建时间少；同时，全局迁移表减少了大量冗余迁移边，RDFA显著压缩DFA存储空间；针对每个读入字符，RDFA仅需要查找当前状态的本地迁移表和全局迁移表，从而提高字符串匹配吞吐量。