专利详情

专利名称	确定自动机的空间压缩方法
申请号	CN200910090556.3	专利类型	发明专利
公开（公告）号	CN101630323	公开（授权）日	2010.01.20
申请（专利权）人	中国科学院计算技术研究所	发明（设计）人	杨毅夫;刘燕兵;刘萍;郭莉
主分类号	G06F17/30(2006.01)I	IPC主分类号	G06F17/30(2006.01)I
专利有效期	确定自动机的空间压缩方法至确定自动机的空间压缩方法	法律状态	实质审查的生效
说明书摘要	本发明提供一种确定自动机的空间压缩方法，包括：对确定自动机中的各个状态做分簇操作，得到多个用于表示状态集合的簇；将确定自动机中各个状态的转移边按簇分类，得到多个簇矩阵、与所述簇矩阵对应的位图以及一个剩余矩阵；其中，所述簇矩阵包括指向同一簇的转移边，所述位图用于描述所对应簇矩阵中相关元素的有效性；所述剩余矩阵包括确定自动机中未被包含到所述簇矩阵中的剩余转移边；为所述簇矩阵中的各行提取基值，然后将所述簇矩阵转换成一个偏移量矩阵，再将偏移量矩阵中的各行合并，增加用于标记可合并状态的索引数组，得到所述簇矩阵的压缩矩阵。本发明不仅在压缩效果上有所提高，而且在实现正则表达式匹配时在匹配速度上有很大的提高。