通过预计算优化搜索引擎分词的方法及搜索引擎分词装置

摘要

本发明提出一种通过预计算优化搜索引擎分词的方法，包括以下步骤：按照Trie树子节点的数目对分词词典中字符进行编码以生成序列码，其中，对所述Trie树子节点的数目多的字符优先进行编码；根据所述序列码进行预计算以生成双数组Trie树的第一数组和第二数组；根据所述序列码、所述第一数组和所述第二数组在所述分词词典中进行分词查询。本发明提高了搜索引擎分词的空间利用率，加快了分词模块的载入速度，增强了线上服务的稳定性。本发明还公开了一种搜索引擎分词装置。

说明书

技术领域

本发明涉及计算机科学技术领域，特别涉及一种通过预计算优化搜索引擎分词的 方法及搜索引擎分词装置。

背景技术

分词是搜索引擎最基本的功能，是搜索引擎根据用户提交的关键词串用各种方法进行 匹配的一种技术。现有搜索引擎为了达到较好的分词效果，分词词典容量一般都比较大， 并且采用明文分词词典，通过线上计算的方式生成内部的数据结构。现有搜索引擎一般采 用线性索引表、倒排表、散列(hash)和搜索树等数据结构。线性索引表和倒排表都是静 态索引结构。散列(Hash)是通过特定的散列函数和与之配套的处理冲突方法，将字符映 射到某个存储位置，在搜索时只要对字符进行Hash计算就能得到存储位置。

现有技术的缺点如下：

(1)、静态搜索搜索时间与分词词典的大小相关，当词典容量大的时候响应时间长， 难以达到O(1)的量级，并且静态搜索在词典变更时需要做的改动较大。

(2)、散列搜索速度快，时间复杂度能够优化到O(1)，但是空间利用率低，内存占用 大，并且查询时间也依赖于Hash冲突处理机制的设计。

(3)、分词词典大导致载入时间长，使得搜索产品应对故障的响应不够敏捷，容易 造成流量的大规模损失，同时模块启动时间长也会影响到日常产品运维的效率。

(4)、载入过程中大量的计算和频繁的IO操作，容易给线上服务的稳定性造成冲击。

发明内容

本发明的目的旨在至少解决上述技术缺陷之一。

为此，本发明的目的在于提出一种通过预计算优化搜索引擎分词的方法，通过优 先考虑Trie树子节点数目较多节点的转移字符以及空闲碎片的有效利用，提高了空间利 用率，并通过进行线下的预计算，提高了搜索引擎线上分词模块的载入速度，不需要耗费 大量计算资源和频繁IO，不会对线上服务的稳定性造成冲击。通过签名还能够有效避免词 典文件格式错误或者内容缺失对分词效果的影响。

本发明的第二个目的在于提供一种通过预计算优化搜索引擎分词的系统。

为达到上述目的，本发明第一方面的实施例公开了一种通过预计算优化搜索引擎 分词的方法。该方法包括以下步骤：按照Trie树子节点的数目对分词词典中字符进行 编码以生成序列码，其中，对所述Trie树子节点的数目多的字符优先进行编码；根据 所述序列码进行预计算以生成双数组Trie树的第一数组和第二数组；根据所述序列码、 所述第一数组和所述第二数组在所述分词词典中进行分词查询。

由于序列码是优先考虑Trie树子节点数目较多节点的转移字符，因此这部分子节点最 后在双数组存储的时候一般都是连续的，从而在查询时间保持O(1)的量级的同时提高了 空间利用率，降低了内存占用。

在本发明的一个实施例中，还包括：

将所述序列码、所述第一数组和所述第二数组转换为二进制文件，并生成相应的 签名。在搜索引擎线上服务时，分词模块能直接从二进制文件进行载入，载入速度快，避 免了大量的计算和频繁的IO操作，并且不会对线上服务的稳定性造成冲击。生成的相应签 名能够预防文件格式和内容的错误。

在本发明的一个实施例中，还包括：

将所述序列码、所述第一数组和所述第二数组进行尾部位置空间截断。尾部位置 空间截断能够有效节省内存。

在本发明的一个实施例中，所述按照Trie树子节点的数目对分词词典中字符进行 编码以生成序列码进一步包括：

计算每个字符的Trie树子节点的数目；

根据所述Trie树子节点的数目依次对所述字符的内码进行哈希计算以生成所述序 列码，并根据所述字符在所述分词词典中词语中的位置确定所述字符的节点位置。

在本发明的一个实施例中，所述根据序列码进行预计算以生成双数组Trie树的第 一数组和第二数组进一步包括：

根据所述Trie树子节点的数目依次将所述序列码中的字符填入所述第一数组和所 述第二数组。

在本发明的一个实施例中，其中，

如果所述字符所代表的词属于所述分词词典，则所述字符在所述第一数组中对应 的值为0，或者所述字符在所述第二数组中对应的值为负值；

如果所述字符为中间节点，则所述字符在所述第一数组中对应的值非0。

在本发明的一个实施例中，其中，

如果所述字符在所述第一数组中对应的值为负值，则表示向前查找空闲位置。对于 子节点数较少节点的转移字符，在填充数组的时候采用从前向后回溯的方式来填补前面产 生的空隙，将之前闲置的零散节点回收利用，从而更进一步提高了空间利用率。

本发明第一方面的实施例公开了一种搜索引擎分词装置，包括：

序列码生成模块，用于按照Trie树子节点的数目对分词词典中字符进行编码以生 成序列码，其中，对所述Trie树子节点的数目多的字符优先进行编码；

数组生成模块，用于根据所述序列码进行预计算以生成双数组Trie树的第一数组 和第二数组；以及

分词查询模块，用于根据所述序列码、所述第一数组和所述第二数组在所述分词 词典中进行分词查询。

搜索引擎分词装置中，由于序列码是优先考虑Trie树子节点数目较多节点的转移字 符，因此这部分子节点最后在双数组存储的时候一般都是连续的，从而在查询时间保持O (1)的量级的同时提高了空间利用率，降低了内存占用。

在本发明的一个实施例中，还包括：

转换模块，用于将所述序列码、所述第一数组和所述第二数组转换为二进制文件， 并生成相应的签名。在搜索引擎线上服务时，分词模块能直接从二进制文件进行载入，载 入速度快，避免了大量的计算和频繁的IO操作，并且不会对线上服务的稳定性造成冲击。 生成的相应签名能够预防文件格式和内容的错误。

在本发明的一个实施例中，所述转换模块还用于将所述序列码、所述第一数组和 所述第二数组进行尾部位置空间截断。尾部位置空间截断能够有效节省内存。

在本发明的一个实施例中，所述序列码生成模块进一步包括：

计算子模块，用于计算每个字符的Trie树子节点的数目；以及

生成子模块，用于根据所述Trie树子节点的数目依次对所述字符的内码进行哈希 计算以生成所述序列码，并根据所述字符在所述分词词典中词语中的位置确定所述字 符的节点位置。

在本发明的一个实施例中，所述数组生成模块根据所述Trie树子节点的数目依次 将所述序列码中的字符填入所述第一数组和所述第二数组。

在本发明的一个实施例中，其中，

如果所述字符所代表的词属于所述分词词典，则所述字符在所述第一数组中对应 的值为0，或者所述字符在所述第二数组中对应的值为负值；

如果所述字符为中间节点，则所述字符在所述第一数组中对应的值非0。

在本发明的一个实施例中，其中，

如果所述字符在所述第一数组中对应的值为负值，则表示向前查找空闲位置。

本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变 得明显，或通过本发明的实践了解到。

附图说明

本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明 显和容易理解，其中：

图1为根据本发明实施例的通过预计算优化搜索引擎分词的方法的流程框图；

图2为本发明具体实施例的Trie树示意图；

图3为根据本发明实施例的双数组内容示意图；以及

图4为根据本发明实施例的搜索引擎分词装置的结构图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终 相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参 考附图描述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

下面参考图1至图3描述根据本发明实施例的通过预计算优化搜索引擎分词的方 法。

在本发明的一个实施例中，分词词典里内容包括：啊、阿根廷、阿胶、阿拉伯、阿拉 伯人、埃及。根据分词词典生成的Trie树如图2所示。可以理解的是，上述分词词典以 及Trie树仅出于示例的目的，本发明实施例并不限于此。

步骤S110：按照Trie树子节点的数目对分词词典中字符进行编码以生成序列码， 其中，对Trie树子节点的数目多的字符优先进行编码。

按照Trie树子节点的数目对分词词典中字符进行编码以生成序列码进一步包括：

步骤S111：计算每个字符的Trie树子节点的数目。

步骤S112：根据Trie树子节点的数目依次对字符的内码进行哈希计算以生成序列 码，并根据字符在分词词典中词语中的位置确定字符的节点位置。(例如为中间节点 或叶子节点)

在本发明的一个实施例中，汉字的内码由两个字节组成，共计65536个，一般分词词 典中出现的字符小于内码总数，设计时将序列码为连续的。按照图2所示的Trie树对分 词词典中字符按照Trie树子节点的数目递减的顺序进行编码，生成序列码如表1所示，

  啊   阿   埃   根 ...   胶   拉   及   廷   伯   人   1   2   3   4 ...   5   6   7   8   9   10

表1

表1中第一行存储字符，第二行存储与该字符对应的序列码，例如，“啊”的序列码 为1，“阿”的序列码为2。采用code数组来表示序列表，选择适当的hash函数，使得 hash计算量小，并且序列码表的长度和出现过的字符数差距较小。当给定一个字符时，将 其内码通过hash函数进行转换，能够在O(1)的时间内得到该字符对应的序列码。可以理 解的是，上述序列码以及code数组仅出于示例的目的，本发明实施例并不限于此。

步骤S120：根据序列码进行预计算以生成双数组Trie树的第一数组和第二数组；

根据序列码进行预计算以生成双数组Trie树的第一数组和第二数组进一步包括：

步骤S121：根据Trie树子节点的数目依次将序列码中的字符填入第一数组和第二 数组。在本发明的一个实施例中，将第一数组记作数组base[]，将第二数组记作数组 check[]。从Trie树子节点数最多的节点开始，选择图2中第一层的转移条件“啊”、“阿”和 “埃”，根据表1得到对应的序列码分别为1、2、3，如图3所示，依次放入双数组对应的1、 2、3的位置上，再继续选择子节点最多的节点3，转移条件分别为“根”、“胶”和“拉”，根据 表1查出对应的序列码分别为4、5、6。由于序列码是优先考虑Trie树子节点数目较多节 点的转移字符，因此这部分子节点最后在双数组存储的时候一般都是连续的，从而提高了 空间利用率。对于子节点数较少节点的转移字符，在填充数组的时候采用从前向后回溯的 方式来填补前面产生的空隙，将之前闲置的零散节点回收利用，尤其对于含有大量专有名 字的分词词典，能够更进一步提高了空间利用率。如图3所示，“阿拉”在双数组对应的7 的位置上，“埃及”在双数组对应的8的位置上等。

步骤S122：如果字符所代表的词属于分词词典，则字符在第一数组中对应的值为 0，或者字符在第二数组中对应的值为负值。在本发明的一个实施例中，由于Trie树中 节点2是叶子节点，因此“啊”对应的base[1]标记为0，Check值标记为0，check值标记为 0表示对应的节点父节点为根节点；由于“阿胶”是一个分词词典中的词，因此“阿胶”对应的 base[6]＝0，check[6]＝-check[6]。

步骤S123：如果字符为中间节点，则字符在第一数组中对应的值非0。“阿”为中 间节点，设置“阿”对应的base[2]＝1。

在本发明的一个实施例中，每次为序列码中的字符查找存储空间时，不能使用字符的 序列码所对应的数组的位置，必须向前或者向后移动1个单位及以上。例如“根”的序列码 是4，那么即使base[4]和check[4]这两个位置目前是空闲的也不可以使用，需要向前或者向 后移动1个单位及以上。此处设置单位为数组的一个位置。可以理解的是，上述单位仅出 于示例目的，本发明不限于此。具体设置“阿”对应的base[2]＝1过程如下：词典中以“阿”为 前缀的词有“阿根廷”、“阿胶”和“阿拉伯”三个。“根”，“胶”和“拉”是“阿”的子节点，需要在 数组中为这些子节点找到合适的存储空间。根据表1得出“根”、“胶”和“拉”的编码分别是4、 5和6，首先从第一数组base[]和第二数组check[]中向数组后方移动1个单位，得出存在连续 的三个空位可以放入“根”，“胶”和“拉”三个子节点，即能满足base[1+4]＝check[1+4]＝0； base[1+5]＝check[1+5]＝0；base[1+6]＝check[1+6]＝0。因此设置base[2]＝1。

设置check[5]＝check[6]＝check[7]＝2，表示5、6、7这三个位置对应的节点的父节点是 数组的第二个位置上对应的结点，即“阿根”、“阿胶”、“阿拉”的父节点为“阿”。

步骤S124：如果字符在第一数组中对应的值为负值，则表示向前查找空闲位置。 例如，“阿拉伯”对应的base[10]＝-6。

步骤S130：根据序列码、第一数组和第二数组在分词词典中进行分词查询。

在本发明的一个实施例中，具体的查询过程为：s表示上一个状态时字符在数组中 的位置，c表示当前状态时字符的序列码，t表示下一状态转移后字符在数组中的位置，查 询过程的伪代码如下：

下面以查询“阿拉伯”是否在分词词典中为例描述查询过程：

(1)、查找“阿”在表1中对应的序列码为2，则“阿”对应双数组中第2个位置，查找双数组 得到base[2]＝1；

(2)、查找“拉”在表1中对应的的序列码为6，检查check[base[2]+6]的绝对值，也就是| check[7]|＝2；

(3)接着找到“伯”的序列码为9，检查check[base[7]+9]的绝对值，即|check[10]|＝7， 并且check[10]为负数，由以上定义可知“阿拉伯”为叶节点，表示“阿拉伯”在分词词典中， 是一个合法的分词，查询过程结束。可以理解的是，上述具体的查询过程仅出于实例目的， 本发明不限于此。

在本发明的一个实施例中，将序列码、第一数组和第二数组进行尾部位置空间截 断，按照设计的格式进行序列化后写入二进制文件，例如存储为word.bin，并生成相应的 签名。

将序列码、第一数组和第二数组进行尾部位置空间截断能够有效节省内存，并且在 搜索引擎线上服务时，分词模块直接从二进制文件进行载入，速度快，避免了大量的计算 和频繁的IO操作，不会对线上服务的稳定性造成冲击。生成的相应签名还能够预防文件格 式和内容的错误。

下面根据图4来描述根据本发明实施例的搜索引擎分词装置1000，其特征在于， 包括：序列码生成模块100，用于按照Trie树子节点的数目对分词词典中字符进行编 码以生成序列码，其中，对Trie树子节点的数目多的字符优先进行编码；数组生成模 块200，用于根据序列码进行预计算以生成双数组Trie树的第一数组和第二数组；分 词查询模块300，用于根据序列码、第一数组和第二数组在分词词典中进行分词查询； 转换模块400，用于将序列码、第一数组和第二数组转换为二进制文件。

在本发明的一个实施例中，分词词典内容包括：啊、阿根廷、阿胶、阿拉伯、阿拉伯 人、埃及。根据分词词典生成的Trie树如图2所示。可以理解的是，上述分词词典以及 Trie树仅出于示例的目的，本发明实施例并不限于此。

序列码生成模块100进一步包括：

计算子模块110，用于计算每个字符的Trie树子节点的数目；

生成子模块120，用于根据Trie树子节点的数目依次对字符的内码进行哈希计算 以生成序列码，并根据字符在分词词典中词语中的位置确定字符的节点位置。(例如 为中间节点或叶子节点)

在本发明的一个实施例中，汉字的内码由两个字节组成，共计65536个，一般分词词 典中出现的字符小于内码总数，设计时将序列码为连续的。计算子模块110对图2所示的 Trie树的每个节点进行计算，生成子模块120对字符的内码进行哈希计算生成序列码， 序列码如表1所示。表1中第一行存储字符，第二行存储与该字符对应的序列码，例 如，“啊”的序列码为1，“阿”的序列码为2。生成子模块120采用code数组来表示序列 表，并且生成子模块120选择适当的hash函数，使得hash计算量小，并且序列码表的 长度和出现过的字符数差距较小。当给定一个字符时，生成子模块120将其内码通过hash 函数进行转换，能够在O(1)的时间内得到该字符对应的序列码。可以理解的是，上述序 列码以及code数组仅出于示例的目的，本发明实施例并不限于此。

数组生成模块200根据Trie树子节点的数目依次将序列码中的字符填入第一数组 和第二数组。

在本发明的一个实施例中，数组生成模块200将第一数组记作数组base[]，将第二 数组记作数组check[]。数组生成模块200从Trie树子节点数最多的节点开始，选择图2 中第一层的转移条件“啊”、“阿”和“埃”，根据表1得到对应的序列码分别为1、2、3，如图 3所示，数组生成模块200依次将其放入双数组对应的1、2、3的位置上，再继续选择子 节点最多的节点3，转移条件分别为“根”、“胶”和“拉”，根据表1查出对应的序列码分别为 4、5、6。由于序列码是优先考虑Trie树子节点数目较多节点的转移字符，因此这部分子 节点最后在双数组存储的时候一般都是连续的，从而提高了空间利用率。数组生成模块200 对于子节点数较少节点的转移字符，在填充数组的时候采用从前向后回溯的方式来填补前 面产生的空隙，将之前闲置的零散节点回收利用，尤其对于含有大量专有名字的分词词典， 能够更进一步提高了空间利用率。如图3所示，“阿拉”在双数组对应的7的位置上，“埃及” 在双数组对应的8的位置上等。

如果字符所代表的词属于分词词典，则字符在第一数组中对应的值为0，或者字符 在第二数组中对应的值为负值。

在本发明的一个实施例中，由于Trie树中节点2是叶子节点，因此“啊”对应的base[1] 标记为0，Check值标记为0，check值标记为0表示对应的节点父节点为根节点；由于“阿 胶”是一个分词词典中的词，因此“阿胶”对应的base[6]＝0，check[6]＝-check[6]。

如果字符为中间节点，则字符在第一数组中对应的值非0。

在本发明的一个实施例中，数组生成模块200每次为序列码中的字符查找存储空间 时，不能使用字符的序列码所对应的数组的位置，必须向前或者向后移动1个单位及以上。 例如“根”的序列码是4，那么即使base[4]和check[4]这两个位置目前是空闲的也不可以使用， 需要向前或者向后移动1个单位及以上。此处数组生成模块200设置单位为数组的一个位 置。可以理解的是，上述单位仅出于示例目的，本发明不限于此。数组生成模块200具体 设置“阿”对应的base[2]＝1过程如下：词典中以“阿”为前缀的词有“阿根廷”、“阿胶”和“阿拉 伯”三个。“根”，“胶”和“拉”是“阿”的子节点，数组生成模块200需要在数组中为这些子节 点找到合适的存储空间。根据表1得出“根”、“胶”和“拉”的编码分别是4、5和6，首先从 第一数组base[]和第二数组check[]中向数组后方移动1个单位，得出存在连续的三个空位可 以放入“根”，“胶”和“拉”三个子节点，即能满足base[1+4]＝check[1+4]＝0； base[1+5]＝check[1+5]＝0；base[1+6]＝check[1+6]＝0。因此设置base[2]＝1。

数组生成模块200设置check[5]＝check[6]＝check[7]＝2，表示5、6、7这三个位置对应 的节点的父节点是数组的第二个位置上对应的结点，即“阿根”、“阿胶”、“阿拉”的父节点为 “阿”。

如果字符在第一数组中对应的值为负值，则表示向前查找空闲位置。

例如，“阿拉伯”对应的base[10]＝-6。

在本发明的一个实施例中，分词查询模块300具体的查询过程为：分词查询模块 300以s表示上一个状态时字符在数组中的位置，c表示当前状态时字符的序列码，t表示 下一状态转移后字符在数组中的位置，分词查询模块300查询过程的伪代码如下：

下面以分词查询模块300查询“阿拉伯”是否在分词词典中为例描述查询过程：

(1)、分词查询模块300查找“阿”在表1中对应的序列码为2，则“阿”对应双数组中第2 个位置，分词查询模块300查找双数组得到base[2]＝1；

(2)、分词查询模块300查找“拉”在表1中对应的的序列码为6，检查check[base[2]+6] 的绝对值，也就是|check[7]|＝2；

(3)分词查询模块300接着找到“伯”的序列码为9，检查check[base[7]+9]的绝对值， 即|check[10]|＝7，并且check[10]为负数，“阿拉伯”在分词词典中，分词查询模块300判 断“阿拉伯”为合法的分词，查询过程结束。可以理解的是，上述分词查询模块300具体 的查询过程仅出于实例目的，本发明不限于此。

转换模块400还用于将序列码、第一数组和第二数组进行尾部位置空间截断，并 生成相应的签名。

在本发明的一个实施例中，转换模块400将序列码、第一数组和第二数组进行尾 部位置空间截断，按照设计的格式进行序列化后写入二进制文件，例如存储为word.bin， 并生成相应的签名。转换模块400将序列码、第一数组和第二数组进行尾部位置空间 截断能够有效节省内存，并且在搜索引擎线上服务时，分词模块直接从二进制文件进行载 入，速度快，避免了大量的计算和频繁的IO操作，不会对线上服务的稳定性造成冲击。生 成的相应签名还能够预防文件格式和内容的错误。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示 例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或 者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意 性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者 特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以 理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、 替换和变型，本发明的范围由所附权利要求及其等同限定。