公开(公告)号：CN1648901A

公开(公告)日：2005-08-03

申请号：CN200510007089.5

申请日：2005-02-03

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

Inventor： 刘萍 ,  谭建龙 ,  程学旗

IPC: G06F17/30

Abstract: 本发明提供针对大规模关键词匹配的方法和系统。按照所提供的方法和系统，首先将给定关键词集合进行规范化，在规范化的关键词集合(也可以直接在原始关键词集合上)上求解一个最优分组和组内最佳匹配方法，这个过程可以使用两种机制：一是使用动态规划的方法计算出一个最优分组，依照此结果将给定的关键词集合划分成若干个组；然后，针对每一个组，通过训练的方式得到一个最佳的匹配方法；一是通过训练建立一个边上带权重的有向图，求解此图的最短路径，得到最优分组和组内最佳匹配方法；然后对所有的组，使用训练的结果依次构造扫描自动机，形成一个扫描自动机序列，使输入的待扫描文本依次通过，得到最终的扫描结果。

公开(公告)号：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]。本发明的确定自动机状态转换表的空间压缩方法在减少内存中所占用空间的同时，大大减少了空间开销。

公开(公告)号：CN101140593A

公开(公告)日：2008-03-12

申请号：CN200710175751.7

申请日：2007-10-11

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

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

IPC: G06F17/30

Abstract: 本发明公开了一种关键词匹配方法和系统。首先读入关键词文件，统计关键词个数，设置多个过滤散列表和一个校验散列表的掩码或大小；根据关键词和上述散列表掩码或大小构造该过滤散列表和该校验散列表；根据过滤散列表和校验散列表对输入的文本进行扫描匹配，将匹配结果存储在指定的内存结构或者外部文件中。本发明的方法和系统不仅有效提高关键词匹配的速度，还非常节约内存，并可以实现大规模关键词匹配。