公开(公告)号：CN101630323A

公开(公告)日：2010-01-20

申请号：CN200910090556.3

申请日：2009-08-20

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

Inventor： 杨毅夫 ,  刘燕兵 ,  刘萍 ,  郭莉

IPC: G06F17/30

Abstract: 本发明提供一种确定自动机的空间压缩方法，包括：对确定自动机中的各个状态做分簇操作，得到多个用于表示状态集合的簇；将确定自动机中各个状态的转移边按簇分类，得到多个簇矩阵、与所述簇矩阵对应的位图以及一个剩余矩阵；其中，所述簇矩阵包括指向同一簇的转移边，所述位图用于描述所对应簇矩阵中相关元素的有效性；所述剩余矩阵包括确定自动机中未被包含到所述簇矩阵中的剩余转移边；为所述簇矩阵中的各行提取基值，然后将所述簇矩阵转换成一个偏移量矩阵，再将偏移量矩阵中的各行合并，增加用于标记可合并状态的索引数组，得到所述簇矩阵的压缩矩阵。本发明不仅在压缩效果上有所提高，而且在实现正则表达式匹配时在匹配速度上有很大的提高。

公开(公告)号：CN101630323B

公开(公告)日：2012-01-25

申请号：CN200910090556.3

申请日：2009-08-20

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

Inventor： 杨毅夫 ,  刘燕兵 ,  刘萍 ,  郭莉

IPC: G06F17/30

Abstract: 本发明提供一种确定自动机的空间压缩方法，包括：对确定自动机中的各个状态做分簇操作，得到多个用于表示状态集合的簇；将确定自动机中各个状态的转移边按簇分类，得到多个簇矩阵、与所述簇矩阵对应的位图以及一个剩余矩阵；其中，所述簇矩阵包括指向同一簇的转移边，所述位图用于描述所对应簇矩阵中相关元素的有效性；所述剩余矩阵包括确定自动机中未被包含到所述簇矩阵中的剩余转移边；为所述簇矩阵中的各行提取基值，然后将所述簇矩阵转换成一个偏移量矩阵，再将偏移量矩阵中的各行合并，增加用于标记可合并状态的索引数组，得到所述簇矩阵的压缩矩阵。本发明不仅在压缩效果上有所提高，而且在实现正则表达式匹配时在匹配速度上有很大的提高。