专利详情

专利名称	确定自动机状态转换表的空间压缩方法
申请号	CN201010226250.9	专利类型	发明专利
公开（公告）号	CN101916259A	公开（授权）日	2010.12.15
申请（专利权）人	中国科学院计算技术研究所	发明（设计）人	刘燕兵;何慧敏;刘萍;谭建龙;郭莉
主分类号	G06F17/30(2006.01)I	IPC主分类号	G06F17/30(2006.01)I
专利有效期	确定自动机状态转换表的空间压缩方法至确定自动机状态转换表的空间压缩方法	法律状态	实质审查的生效
说明书摘要	本发明提供一种确定自动机状态转换表的空间压缩方法，包括：将确定自动机状态转换表表示为一个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]。本发明的确定自动机状态转换表的空间压缩方法在减少内存中所占用空间的同时，大大减少了空间开销。