确定自动机的空间压缩方法

摘要

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

主权项

一种确定自动机的空间压缩方法，包括：步骤1)、对确定自动机中的各个状态做分簇操作，得到多个用于表示状态集合的簇；步骤2)、将所述确定自动机中各个状态的转移边按步骤1)所得到的簇分类，得到多个簇矩阵、与所述簇矩阵对应的位图以及一个剩余矩阵；其中，所述簇矩阵包括指向同一簇的转移边，所述位图用于描述簇矩阵中相关元素的有效性；所述剩余矩阵包括确定自动机中未被包含到所述簇矩阵中的剩余转移边；步骤3)、为所述簇矩阵中的各行提取基值，然后将所述簇矩阵转换成一个偏移量矩阵，再将偏移量矩阵中的各行合并，增加用于标记可合并状态的索引数组，得到所述簇矩阵的压缩矩阵；其中，所述的基值为基值所在行所对应簇中的最小值，所述的偏移量矩阵中的偏移量为所述簇矩阵中的转移边的值与所述基值间的差；所述的将偏移量矩阵中的各行合并时，满足以下规则：在矩阵T中，当且仅当对任意字符c满足T[r][c]＝‑1或者T[s][c]＝‑1或者T[s][c]＝T[r][c]时，行r和行s是可合并的，其中，“‑1”代表对应位置的值为无效值。