一种基于关键词字典树检索的中文AC自动机工作方法

摘要

本发明公开了一种基于关键词字典树检索的中文AC自动机工作方法，包括：获取所有关键词，并根据所有关键词建立关键词字典树；在关键词字典树中建立并初始化检索指针；获取待检测文章，将文章编码，建立并初始化文章指针；判断当前文章指针与当前检索指针的任一子节点是否匹配并由此移动文章指针与检索指针；判断当前检索指针的匹配子节点是否为终止节点并由此移动文章指针与检索指针；使文章指针扫过整篇文章，统计所有关键词的出现次数。本发明通过使用检索指针在字典树的节点之间移动来将关键词与文章进行比对的技术方案，有效地利用了字典树中具有相同前缀的关键词排布在相邻位置的特性，压缩了中文AC自动机的工作占用空间。

说明书

技术领域

本发明涉及信息技术领域，特别地，涉及一种基于关键词字典树检索的 中文AC自动机工作方法。

背景技术

AC自动机(Aho-Corasickautomaton)是一种著名的多模匹配方法，用于 在文章当中检索多个关键词出现的次数。传统的AC自动机只能识别26个英 文字母，现有技术则将传统的AC自动机工作原理套用到了中文文章中，但这 种方案下中文AC自动机工作的空间复杂度过高，缺乏实际应用价值。

针对现有技术中中文AC自动机工作的空间复杂度过高的问题，目前尚未 有有效的解决方案。

发明内容

针对现有技术中系统结构识别与优化方法抑或主观片面、计算能力差， 抑或耗时费力、仿真精度低的问题，本发明的目的在于提出一种基于关键词 字典树检索的中文AC自动机工作方法，能够用降低中文AC自动机工作时需 要的空间复杂度，压缩了中文AC自动机的工作占用空间。

基于上述目的，本发明提供的技术方案如下：

根据本发明的一个方面，提供了一种基于关键词字典树检索的中文AC自 动机工作方法，包括：

获取所有关键词，并根据所有关键词建立关键词字典树；

在关键词字典树中建立并初始化检索指针；

获取待检测文章，将文章编码，建立并初始化文章指针；

判断当前文章指针与当前检索指针的任一子节点是否匹配并由此移动文 章指针与检索指针；

判断当前检索指针的匹配子节点是否为终止节点并由此移动文章指针与 检索指针；

使文章指针扫过整篇文章，统计所有关键词的出现次数。

其中：

将文章编码，为将文章中的所有汉字按照指定的汉字编码方式以数字组 合的形式表示；

在关键词字典树中初始化检索指针，为在关键词字典树中将检索指针置 为指向虚根；

初始化文章指针，为将文章指针置为指向文件头第一字符编码。

并且，数字组合为十六进制数字的数字组合；指定的汉字编码方式为以 下之一：GB2312、GBK、BIG5、UTF-8。

同时，判断当前文章指针与当前检索指针的任一子节点是否匹配并由此 移动文章指针与检索指针包括：

获取当前文章指针指向的编码数字；

获取当前检索指针指向节点的所有子节点；

将当前文章指针指向的编码数字在当前检索指针指向节点的所有子节点 中进行比对，判断是否存在一个子节点上的数字与当前文章指针指向的编码 数字相匹配；若是，则继续判断当前检索指针的匹配子节点是否为终止节 点；若否，则将检索指针置为当前检索指针指向节点的失败指针指向的节 点。

并且，若不存在一个子节点上的数字与当前文章指针指向的编码数字相 匹配，且当前检索指针指向虚根或当前检索指针指向节点的失败指针指向虚 根，则将文章指针后移一位，并重新判断当前文章指针与当前检索指针的任 一子节点是否匹配。

并且，判断当前检索指针的匹配子节点是否为终止节点并由此移动文章 指针与检索指针包括：

在关键词字典树中获取匹配子节点的节点信息；

根据匹配子节点的节点信息判断匹配子节点是否为终止节点；若是，则 从关键词字典树中解码出该终止节点所代表的关键词，并将该关键词被检索 到的次数累加1，同时将检索指针重置为指向虚根、文章指针后移一位；若 否，则将检索指针置为指向匹配子节点、文章指针后移一位；

重新判断当前文章指针与当前检索指针的任一子节点是否匹配。

并且，使文章指针扫过整篇文章并统计所有关键词的出现次数，为将文 章指针在上述操作中移动到文章末尾，统计每个关键词被检索到的次数，并 将每个关键词与其在文章中被检索到的次数信息输出。

从上面所述可以看出，本发明提供的技术方案通过使用检索指针在字典 树的节点之间移动来将关键词与文章进行比对的技术方案，有效地利用了字 典树中具有相同前缀的关键词排布在相邻位置的特性，使得节点对查询其子 节点所在位置的信息量被大幅度压缩，避免使用占用大量空间复杂度的哈希 表，因此降低了中文AC自动机工作时需要的空间复杂度，压缩了中文AC自 动机的工作占用空间。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实 施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅 仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性 劳动的前提下，还可以根据这些附图获得其他的附图。

图1为根据本发明实施例的一种基于关键词字典树检索的中文AC自动机 工作方法的流程图；

图2为根据本发明实施例的一种基于关键词字典树检索的中文AC自动机 工作方法中，字典树各节点生成过程示意图；

图3为根据本发明实施例的一种基于关键词字典树检索的中文AC自动机 工作方法中，字典树各节点的前缀指针生成过程示意图；

图4为根据本发明实施例的一种基于关键词字典树检索的中文AC自动机 工作方法中，字典树各节点的失败指针生成过程示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明 实施例中的附图，对本发明实施例中的技术方案进一步进行清楚、完整、详 细地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部 的实施例。基于本发明中的实施例，本领域普通技术人员所获得的所有其他 实施例，都属于本发明保护的范围。

根据本发明的实施例，提供了一种基于关键词字典树检索的中文AC自动 机工作方法。

如图1所示，根据本发明的实施例提供了一种基于关键词字典树检索的 中文AC自动机工作方法包括：

步骤S101，获取所有关键词，并根据所有关键词建立关键词字典树；

步骤S103，在关键词字典树中建立并初始化检索指针；

步骤S105，获取待检测文章，将文章编码，建立并初始化文章指针；

步骤S107，判断当前文章指针与当前检索指针的任一子节点是否匹配并 由此移动文章指针与检索指针；

步骤S109，判断当前检索指针的匹配子节点是否为终止节点并由此移动 文章指针与检索指针；

步骤S111，使文章指针扫过整篇文章，统计所有关键词的出现次数。

其中：

将文章编码，为将文章中的所有汉字按照指定的汉字编码方式以数字组 合的形式表示；

在关键词字典树中初始化检索指针，为在关键词字典树中将检索指针置 为指向虚根；

初始化文章指针，为将文章指针置为指向文件头第一字符编码。

并且，数字组合为十六进制数字的数字组合；指定的汉字编码方式为以 下之一：GB2312、GBK、BIG5、UTF-8。

同时，判断当前文章指针与当前检索指针的任一子节点是否匹配并由此 移动文章指针与检索指针包括：

获取当前文章指针指向的编码数字；

获取当前检索指针指向节点的所有子节点；

将当前文章指针指向的编码数字在当前检索指针指向节点的所有子节点 中进行比对，判断是否存在一个子节点上的数字与当前文章指针指向的编码 数字相匹配；若是，则继续判断当前检索指针的匹配子节点是否为终止节 点；若否，则将检索指针置为当前检索指针指向节点的失败指针指向的节 点。

并且，若不存在一个子节点上的数字与当前文章指针指向的编码数字相 匹配，且当前检索指针指向虚根或当前检索指针指向节点的失败指针指向虚 根，则将文章指针后移一位，并重新判断当前文章指针与当前检索指针的任 一子节点是否匹配。

并且，判断当前检索指针的匹配子节点是否为终止节点并由此移动文章 指针与检索指针包括：

在关键词字典树中获取匹配子节点的节点信息；

根据匹配子节点的节点信息判断匹配子节点是否为终止节点；若是，则 从关键词字典树中解码出该终止节点所代表的关键词，并将该关键词被检索 到的次数累加1，同时将检索指针重置为指向虚根、文章指针后移一位；若 否，则将检索指针置为指向匹配子节点、文章指针后移一位；

重新判断当前文章指针与当前检索指针的任一子节点是否匹配。

并且，使文章指针扫过整篇文章并统计所有关键词的出现次数，为将文 章指针在上述操作中移动到文章末尾，统计每个关键词被检索到的次数，并 将每个关键词与其在文章中被检索到的次数信息输出。

下面根据具体实施例进一步阐述本发明的技术方案。

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变 种，它将所有的模式串组织在一棵树的树边上，根节点是一个虚根，每条树 边代表一个字母，从虚根到任意一个节点的路径上的边的有序集合代表某个 模式串的某个前缀。典型应用是用于统计，排序和保存大量的字符串(但不 仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。字典树利用字 符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询 效率比哈希树高。

如图2、3、4所示，在本实施例中，白色点表示虚根，灰色点表示内部 节点，黑色点表示终止节点，即从虚根到终止节点的每条路径代表了一个模 式串，由于"11"是"110"的前缀，所以在图中"11"这两条边是这两个字符串路 径的共用部分，这样就节省了存储空间，由于trie树的虚根到每个节点的路 径(边权)都代表了一个模式串的前缀，所以它又叫前缀树。

构造字典树的前提一般是给定一系列的关键词，然后对每个关键词进行 插入字典树的操作。图2示出的是字典树各节点的生成过程，如图2所示， 初始情况下字典树只有一个虚根，进行四个关键词的插入后就完成了字典树 的节点生成，每次插入在末尾节点设置终止节点印记，可以注意到，第四次 操作实际上没有生成新的节点，只是设置了一个新的终止节点印记，由于它 的这个性质，使得字典树的节点数目不会很多，大大压缩了存储结构。

对于一篇给定的文章，要求在由关键词构建的字典树中查找这个文章中 有多少个关键词，我们可以设定一个检索指针p，初始状态下它指向虚根， 然后从前往后枚举文章，对每一个文章中的字符c，如果在检索指针p指向 节点的出边集合中能够找到字符c对应的边，那么将检索指针p指向c对应 边的子节点，循环往复，直到匹配失败，那么退回到检索指针p节点的前缀 指针指向的节点继续同样的匹配，当遇到一个终止节点时，计数器+1。

每个非虚根节点都有一个前缀指针。图3示出的是字典树各节点的前缀 指针生成过程，如图3所示，虚根子节点的前缀指针指向虚根，因为当一个 字符都不能匹配时要跳到字符串首重新匹配；每个节点的前缀指针都是由它 父节点的前缀指针决定的，所以一次宽度优先搜索(BreadthFirst Search，下文中简称为BFS)就可以把所有节点的前缀指针逐层求解出来。

为了方便描述，我们先把所有字典树上的节点进行编号，编号顺序为节 点的插入顺序，虚根编号为0。图4示出的是字典树各节点的失败指针生成 过程，如图4所示，我们发现如果现在是1号节点，当接收一个'1'这个字 符，则进入2号节点，因为沿着字符'1'的出边到达的状态正好是2号节点； 但是如果接受的是'0'字符，我们发现1号节点没有'0'字符代表的出边，所 以我们需要补上这条'0'边，这条1号节点的“0”边指向1号节点的前缀指 针指向的状态的'0'边对应的节点，而这个状态正好是它自己，所以向自己补 一条边权为'0'的边，在图4中以灰色箭头表示，这就是条1号节点的“0” 边的失败指针。同样地，利用BFS可逐层求解所有节点的后继状态。我们发 现所有节点遍历完后，每个节点都有且仅有两条出边，即完成了关键词字典 树的建立。

现有的中文AC自动机中，汉字被转化为UTF8编码。设文章共N篇，每 篇长度为L，关键词共M个，每个长度为K，则有算法本身时间复杂度为 O(N*L+K)、空间复杂度为O(M*K*26)，26是子节点hash表的大小。汉字 转化成字符在linux下为3个字符，字符的取值范围为0～255，则时间复杂 度为(N*3L+3K),空间复杂度为(M*3K*255)。

而在本发明的技术方案中，对于任一节点I，必然存在一个区间[P,Q]， 使得除了这个区间外没有它的子节点，并且区间内全是它的子节点，即区间 [P,Q]与节点I的子节点集合完全相等。因此，我们可以在判断上舍弃了哈希 表，把空间复杂度降到O(2*M*3K)，每次判断子节点是需要判断256次，此 时时间复杂度为O(256*3*(N*L+K))。本发明相对于现有技术的空间复杂度 降低了O(M*K*759)，即压缩了99.22％的工作占用空间。

在另一个实施例中，可以将中文的汉字转化为拼音，汉字转化成拼音一 般为2～6个字母，这里取4。此时，时间复杂度为O(N*4L+4K)，空间复杂度 为O(M*4K*26)，同样起到了降低空间复杂度的效果。但是一样的字母组成 的话多种多样，此算法需要匹配后再实际比对文字是否相同，所以时间复杂 度为O(K*(N*4L+4K))。

综上所述，借助于本发明的上述技术方案，通过使用检索指针在字典树 的节点之间移动来将关键词与文章进行比对的技术方案，有效地利用了字典 树中具有相同前缀的关键词排布在相邻位置的特性，使得节点对查询其子节 点所在位置的信息量被大幅度压缩，避免使用占用大量空间复杂度的哈希 表，因此降低了中文AC自动机工作时需要的空间复杂度，压缩了中文AC自 动机的工作占用空间

所属领域的普通技术人员应当理解：以上所述仅为本发明的具体实施例 而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修 改、等同替换、改进等，均应包含在本发明的保护范围之内。