欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2014101582620
申请人: 华为技术有限公司
专利类型:发明专利
专利状态:已下证
专利领域: 基本电子电路
更新日期:2024-07-02
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种DFA矩阵的压缩方法,其特征在于,包括:

获取确定的有限状态自动机DFA矩阵;

将DFA矩阵的行分为若干组;

从分在同一组的行中分别选出每一列上出现次数最多的元素值,获得所述组的核,所述核为将选出的元素值按所属列的顺序排成的行;以及获得所述分在同一组的行中的特别元素值,所述特别元素值为与所述核中对应的元素值不同的所述分在同一组的行中的元素值,所述特别元素值所在的列与所述核中对应的元素值所在的列相同;

建立第一对应关系和第二对应关系,所述第一对应关系为所述组与所述核的对应关系,所述第二对应关系为所述特别元素值与所述特别元素值所在组、所在行及所在列的对应关系;

保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系。

2.根据权利要求1所述的DFA矩阵的压缩方法,其特征在于,所述将DFA矩阵的行分为若干组,包括:基于聚类算法,将DFA矩阵的行分为若干组,使得在同一组中,每一列上的相同元素的数量大于或等于预设值。

3.根据权利要求2所述的DFA矩阵的压缩方法,其特征在于,所述基于聚类算法,将DFA矩阵的行分为若干组,包括:根据DFA矩阵,构造赋权无向完全图;

从所述赋权无向完全图的权值中选取一个权值作为阈值;

根据所述阈值,将所述赋权无向完全图划分为边权值大于所述阈值的连通子图;

将属于同一个连通子图的DFA矩阵的行分为一组。

4.根据权利要求3所述的DFA矩阵的压缩方法,其特征在于,在根据DFA矩阵,构造赋权无向完全图之后,所述方法还包括:将所述赋权无向完全图加入图集合;从所述图集合中选取未划分的赋权无向完全图进行划分;

所述从所述赋权无向完全图的权值中选取一个权值作为阈值,包括:从选取的赋权无向完全图的权值中选取一个权值作为阈值。

5.根据权利要求4所述的DFA矩阵的压缩方法,其特征在于,在将DFA矩阵的行分为若干组之后,所述方法还包括:计算第一存储空间和第二存储空间;所述第一存储空间为保存所述若干组所需的存储空间之和,其中每一组所需的存储空间包括每一组的核、特别元素值、第一对应关系以及第二对应关系所需的存储空间;所述第二存储空间为保存所述DFA矩阵所需的存储空间,其中保存所述DFA矩阵所需的存储空间包括由DFA矩阵的所有行组成的组的核、特别元素值、第一对应关系以及第二对应关系所需的存储空间;

当所述第一存储空间小于所述第二存储空间时,将所述连通子图标记为已划分的图,并加入所述图集合;

当所述第一存储空间大于所述第二存储空间时,将所述连通子图加入所述图集合;

所述保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系,包括:当所述第一存储空间小于所述第二存储空间时,保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系。

6.根据权利要求1至5任意一项所述的DFA矩阵的压缩方法,其特征在于,所述从所述赋权无向完全图的权值中选取一个权值作为阈值,包括:从所述赋权无向完全图的权值中选取最小权值作为阈值。

7.根据权利要求3至6任意一项所述的DFA矩阵的压缩方法,其特征在于,所述赋权无向完全图的权值满足如下公式:w(ri,rj)=C|hamdist(ri,rj)|

其中,w(ri,rj)表示赋权无向完全图的权值集合,ri表示DFA矩阵中第i行的元素,rj表示DFA矩阵中第j行的元素,i和j表示不同的行数,C表示DFA矩阵中行所包括的元素的个数,hamdist(ri,rj)表示海明距离函数。

8.根据权利要求1至7任意一项所述的DFA矩阵的压缩方法,其特征在于,所述保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系,包括:将每一组的核组成核矩阵,保存所述核矩阵;将每一组的特别元素值组成特殊跳转表,保存所述特殊跳转表;

所述方法还包括:记录每一组的核在核矩阵中的地址,以及记录每一组的特别元素值在所述特殊跳转表中的地址。

9.根据权利要求1至8任意一项所述的DFA矩阵的压缩方法,其特征在于,在获取DFA矩阵之后,所述方法还包括:将所述DFA矩阵的列进行编号,获得所述DFA矩阵的列编号;其中,所述DFA矩阵中相同的列对应同一列编号;

根据所述DFA矩阵的列对应的跳转字符和所述DFA矩阵的列对应的编号,建立所述DFA矩阵的字符映射表,所述字符映射表用于表示所述跳转字符与所述列编号的对应关系;

将所述DFA矩阵中相同的列进行合并,获得合并后的DFA矩阵;

所述将DFA矩阵的行分为若干组,包括:将合并后的DFA矩阵的行分为若干组。

10.根据权利要求9所述的DFA矩阵的压缩方法,其特征在于,所述获取DFA矩阵,包括:获取至少两个DFA矩阵;

所述将所述DFA矩阵的列进行编号,获得所述DFA矩阵的列编号;包括:将所述至少两个DFA矩阵的列进行编号,获得所述至少两个DFA矩阵的列编号;其中,所述至少两个DFA矩阵中所有相同的列对应同一列编号;

所述根据所述DFA矩阵的列对应的跳转字符和所述DFA矩阵的列对应的列编号,建立所述DFA矩阵的字符映射表,包括:根据所述至少两个DFA矩阵的列对应的跳转字符和所述至少两个DFA矩阵的列对应的列编号,建立所述至少两个DFA矩阵的字符映射表;

在建立所述至少两个DFA矩阵的字符映射表之后,所述方法还包括:

将所述至少两个DFA矩阵的字符映射表合并成所述至少两个DFA矩阵对应的共同的字符映射矩阵,其中,所述共同的字符映射矩阵的列对应的跳转字符用ASCII码表示,所述共同的字符映射矩阵的每一行对应所述至少两个DFA矩阵中的一个DFA矩阵;

将所述共同的字符映射矩阵中的列组成私有字符映射矩阵和公有字符映射矩阵,所述私有字符映射矩阵由所述共同的字符映射矩阵中的部分列组成,所述公有字符映射矩阵由所述共同的字符映射矩阵中的另一部分列组成;

将所述公有字符映射矩阵的行进行编号,获得所述公有字符映射矩阵的行对应的行编号;其中,所述公有字符映射矩阵中所有相同的行对应同一行编号;

记录所述公有字符映射矩阵的行与所述行编号的对应关系;

将所述公有字符映射矩阵中相同的行进行合并,获得压缩的DFA公有字符映射矩阵。

11.根据权利要求10所述的DFA矩阵的压缩方法,其特征在于,所述将所述共同的字符映射矩阵中的列组成私有字符映射矩阵和公有字符映射矩阵,包括:将所述共同的字符映射矩阵中的与表示自然语言符号的跳转字符对应的列作为所述私有字符映射矩阵的列;

将所述共同的字符映射矩阵中的与表示非自然语言符号的跳转字符对应的列作为所述公有字符映射矩阵的列。

12.根据权利要求10所述的DFA矩阵的压缩方法,其特征在于,所述将所述共同的字符映射矩阵中的列组成私有字符映射矩阵和公有字符映射矩阵,包括:将所述共同的字符映射矩阵中的第32至第127列组成私有字符映射矩阵;

将所述共同的字符映射矩阵中的第0至第31列以及第128至第255列组成公有字符映射矩阵。

13.一种压缩DFA矩阵的装置,其特征在于,包括:

获取单元,用于获取确定的有限状态自动机DFA矩阵;

分组单元,用于将所述获取单元获取到的所述DFA矩阵的行分为若干组;

核单元,用于在所述分组单元将所述DFA矩阵的行分为若干组之后,从分在同一组的行中分别选出每一列上出现次数最多的元素值,获得所述组的核,所述核为将选出的元素值按所属列的顺序排成的行;以及获得所述分在同一组的行中的特别元素值,所述特别元素值为与所述核中对应的元素值不同的所述分在同一组的行中的元素值,所述特别元素值所在的列与所述核中对应的元素值所在的列相同;

记录单元,用于在所述核单元获取所述组的核及所述特别元素值之后,建立第一对应关系和第二对应关系,所述第一对应关系为所述组与所述核的对应关系,所述第二对应关系为所述特别元素值与所述特别元素值所在组、所在行及所在列的对应关系;

存储单元,用于保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系。

14.根据权利要求13所述的压缩DFA矩阵的装置,其特征在于,分组单元,用于将所述获取单元获取到的所述DFA矩阵的行分为若干组,包括:用于基于聚类算法,将所述DFA矩阵的行分为若干组,使得在同一组中,每一列上的相同元素的数量大于或等于预设值。

15.根据权利要求14所述的压缩DFA矩阵的装置,其特征在于,所述分组单元用于基于聚类算法,将DFA矩阵的行分为若干组,包括:用于:根据DFA矩阵,构造赋权无向完全图;从所述赋权无向完全图的权值中选取一个权值作为阈值;根据所述阈值,将所述赋权无向完全图划分为边权值大于所述阈值的连通子图;将属于同一个连通子图的DFA矩阵的行分为一组。

16.根据权利要求15所述的压缩DFA矩阵的装置,其特征在于,所述分组单元还用于:在根据DFA矩阵,构造赋权无向完全图之后,将所述赋权无向完全图加入图集合;从所述图集合中选取未划分的赋权无向完全图进行划分;

所述分组单元用于从所述赋权无向完全图的权值中选取一个权值作为阈值,包括:用于从选取的赋权无向完全图的权值中选取一个权值作为阈值。

17.根据权利要求16所述的压缩DFA矩阵的装置,其特征在于,所述分组单元还用于:在将DFA矩阵的行分为若干组之后,计算第一存储空间和第二存储空间;所述第一存储空间为保存所述若干组所需的存储空间之和,其中每一组所需的存储空间包括每一组的核、特别元素值、第一对应关系以及第二对应关系所需的存储空间;所述第二存储空间为保存所述DFA矩阵所需的存储空间,其中保存所述DFA矩阵所需的存储空间包括由DFA矩阵的所有行组成的组的核、特别元素值、第一对应关系以及第二对应关系所需的存储空间;当所述第一存储空间小于所述第二存储空间时,将所述连通子图标记为已划分的图,并加入所述图集合;当所述第一存储空间大于所述第二存储空间时,将所述连通子图加入所述图集合;

所述存储单元用于保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系,包括:用于当所述第一存储空间小于所述第二存储空间时,保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系。

18.根据权利要求13至17任意一项所述的压缩DFA矩阵的装置,其特征在于,所述分组单元用于从所述赋权无向完全图的权值中选取一个权值作为阈值,包括:用于从所述赋权无向完全图的权值中选取最小权值作为阈值。

19.根据权利要求15至18任意一项所述的压缩DFA矩阵的装置,其特征在于,所述赋权无向完全图的权值满足如下公式:w(ri,rj)=C|hamdist(ri,rj)|

其中,w(ri,rj)表示赋权无向完全图的权值集合,ri表示DFA矩阵中第i行的元素,rj表示DFA矩阵中第j行的元素,i和j表示不同的行数,C表示DFA矩阵中行所包括的元素的个数,hamdist(ri,rj)表示海明距离函数。

20.根据权利要求13至19任意一项所述的压缩DFA矩阵的装置,其特征在于,所述存储单元用于保存所述核、所述特别元素值、所述第一对应关系以及所述第二对应关系,包括:用于将每一组的核组成核矩阵,保存所述核矩阵;将每一组的特别元素值组成特殊跳转表,保存所述特殊跳转表;

所述记录单元还用于:记录每一组的核在核矩阵中的地址,以及记录每一组的特别元素值在所述特殊跳转表中的地址。

21.根据权利要求13至20任意一项所述的压缩DFA矩阵的装置,其特征在于,所述装置还包括:编号单元,用于将所述获取单元获取到的DFA矩阵的列进行编号,获得所述DFA矩阵的列编号;其中,所述DFA矩阵中相同的列对应同一列编号;

映射单元,用于根据所述DFA矩阵的列对应的跳转字符和所述DFA矩阵的列对应的编号,建立所述DFA矩阵的字符映射表,所述字符映射表用于表示所述跳转字符与所述列编号的对应关系;

合并单元,用于将所述DFA矩阵中相同的列进行合并,获得合并后的DFA矩阵;

所述分组单元用于将DFA矩阵的行分为若干组,包括:用于将合并后的DFA矩阵的行分为若干组。

22.根据权利要求21所述的压缩DFA矩阵的装置,其特征在于,所述获取单元用于获取DFA矩阵,包括:用于获取至少两个DFA矩阵;

所述编号单元用于将所述DFA矩阵的列进行编号,获得所述DFA矩阵的列编号;包括:用于将所述至少两个DFA矩阵的列进行编号,获得所述至少两个DFA矩阵的列编号;其中,所述至少两个DFA矩阵中所有相同的列对应同一列编号;

所述映射单元用于根据所述DFA矩阵的列对应的跳转字符和所述DFA矩阵的列对应的列编号,建立所述DFA矩阵的字符映射表,包括:用于根据所述至少两个DFA矩阵的列对应的跳转字符和所述至少两个DFA矩阵的列对应的列编号,建立所述至少两个DFA矩阵的字符映射表;

所述映射单元还用于在建立所述至少两个DFA矩阵的字符映射表之后,将所述至少两个DFA矩阵的字符映射表合并成所述至少两个DFA矩阵对应的共同的字符映射矩阵,其中,所述共同的字符映射矩阵的列对应的跳转字符用ASCII码表示,所述共同的字符映射矩阵的每一行对应所述至少两个DFA矩阵中的一个DFA矩阵;

所述映射单元还用于将所述共同的字符映射矩阵中的列组成私有字符映射矩阵和公有字符映射矩阵,所述私有字符映射矩阵由所述共同的字符映射矩阵中的部分列组成,所述公有字符映射矩阵由所述共同的字符映射矩阵中的另一部分列组成;

所述编号单元还用于将所述公有字符映射矩阵的行进行编号,获得所述公有字符映射矩阵的行对应的行编号;其中,所述公有字符映射矩阵中所有相同的行对应同一行编号;

所述记录单元还用于记录所述公有字符映射矩阵的行与所述行编号的对应关系;

合并单元还用于将所述公有字符映射矩阵中相同的行进行合并,获得压缩的DFA公有字符映射矩阵。

23.根据权利要求22所述的压缩DFA矩阵的装置,其特征在于,所述映射单元用于将所述共同的字符映射矩阵中的列组成私有字符映射矩阵和公有字符映射矩阵,包括:用于:将所述共同的字符映射矩阵中的与表示自然语言符号的跳转字符对应的列作为所述私有字符映射矩阵的列;将所述共同的字符映射矩阵中的与表示非自然语言符号的跳转字符对应的列作为所述公有字符映射矩阵的列。

24.根据权利要求22所述的压缩DFA矩阵的装置,其特征在于,所述映射单元用于将所述共同的字符映射矩阵中的列组成私有字符映射矩阵和公有字符映射矩阵,包括:用于:将所述共同的字符映射矩阵中的第32至第127列组成私有字符映射矩阵;将所述共同的字符映射矩阵中的第0至第31列以及第128至第255列组成公有字符映射矩阵。