公开(公告)号：CN101916259A

公开(公告)日：2010-12-15

申请号：CN201010226250.9

申请日：2010-07-06

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

Inventor： 刘燕兵 ,  何慧敏 ,  刘萍 ,  谭建龙 ,  郭莉

IPC: G06F17/30

Abstract: 本发明提供一种确定自动机状态转换表的空间压缩方法，包括：将确定自动机状态转换表表示为一个m×n的矩阵A，其中m代表确定自动机中的状态的个数，n代表字符集的大小；定义一个大小为m的列向量X和一个大小为n的行向量Y；对所述的列向量X和所述的列向量Y做迭代计算，直到对于任意的1≤i≤m，X[i]是多重集Di.中频率最高的元素，并且对于任意的1≤j≤n，Y[j]是多重集D.j中频率最高的元素；其中，所述的Di.＝{A[i，j]-Y[j]|1≤j≤n}，所述的D.j＝{A[i，j]-X[i]|1≤i≤m}；由所述的矩阵A、列向量X和行向量Y计算稀疏矩阵R，并压缩所得到的稀疏矩阵R；其中，R[i，j]＝A[i，j]-X[i]-Y[j]。本发明的确定自动机状态转换表的空间压缩方法在减少内存中所占用空间的同时，大大减少了空间开销。

公开(公告)号：CN101916259B

公开(公告)日：2012-07-11

申请号：CN201010226250.9

申请日：2010-07-06

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

Inventor： 刘燕兵 ,  何慧敏 ,  刘萍 ,  谭建龙 ,  郭莉

IPC: G06F17/30

Abstract: 本发明提供一种确定自动机状态转换表的空间压缩方法，包括：将确定自动机状态转换表表示为一个m×n的矩阵A，其中m代表确定自动机中的状态的个数，n代表字符集的大小；定义一个大小为m的列向量X和一个大小为n的行向量Y；对所述的列向量X和所述的列向量Y做迭代计算，直到对于任意的1≤i≤m，X[i]是多重集Di.中频率最高的元素，并且对于任意的1≤j≤n，Y[j]是多重集D.j中频率最高的元素；其中，所述的Di.＝{A[i，j]-Y[j]|1≤j≤n}，所述的D.j＝{A[i，j]-X[i]|1≤i≤m}；由所述的矩阵A、列向量X和行向量Y计算稀疏矩阵R，并压缩所得到的稀疏矩阵R；其中，R[i，j]＝A[i，j]-X[i]-Y[j]。本发明的确定自动机状态转换表的空间压缩方法在减少内存中所占用空间的同时，大大减少了空间开销。