一种基于单词查找树实现的汉语拼音快速分词方法

摘要

本发明公开了一种基于单词查找树实现的汉语拼音快速分词方法，该方法通过计算机或者嵌入式可移动设备来实现，主要工作步骤如下：步骤一、根据所有已知的汉语单字拼音表建立汉语单字拼音查找树；步骤二、依据已建立的单词查找树，将查找树与哈希表结合，对给定的一串汉语拼音进行分词；步骤三、给出分词结果；步骤四、销毁查找树，释放资源。本发明利用字符串的公共前缀来节约构造空间，最大限度地减少无谓的字符串比较；利用带索引的冗余哈希表来提高查询效率，最大限度减小算法的时间复杂度。

权利要求

1.一种基于单词查找树实现的汉语拼音快速分词方法，该方法通过计算机或者嵌入式可移动设备来实现，其特征是，主要工作步骤如下：步骤一、根据所有已知的汉语单字拼音表建立汉语单字拼音查找树，主要包含以下步骤：(1)根节点不包含字符，除根节点外每一个节点都只包含一个字符；

(2)每个节点的所有子节点包含的字符都不相同；

(3)除叶子节点外，每个节点都有一个长度为26的哈希表，哈希表以26个英文字母的升序为索引，每个元素分别存储一个子节点，且子节点实际个数小于或等于26；

(4)每一个节点都包含一个标识字段，此字段取值0或1，用来标识从根节点到此节点，路径上经过的字符连接起来是否代表一个完整的汉语单字拼音；

步骤二、依据已建立的单词查找树，将查找树与哈希表结合，对给定的一串汉语拼音进行分词；

步骤三、给出分词结果；

步骤四、销毁查找树，释放资源。

2.如权利要求1所述的一种基于单词查找树实现的汉语拼音快速分词方法，其特征是，所述步骤二中，依据已建立的单词查找树，将查找树与哈希表结合，对给定的一串汉语拼音进行分词，主要包含以下步骤：a)从根结点开始一次搜索；

b)取得要查找关键词的第一个字母，并根据该字母从哈希表中选择对应的子树并转到该子树继续进行检索；

c)在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索；

d)迭代过程：取得关键词的第1、2……n个字母，继续查找。

3.如权利要求1所述的一种基于单词查找树实现的汉语拼音快速分词方法，其特征是，所述步骤三中，具体步骤如下：

1)在某个结点处，如果关键词的所有字母已被取出或节点的标识字段取值为1，则从根路径到当前节点依次输出所有字符和当前节点的标识字段值；

2)如果关键词所有字母已被取出，即完成查找；否则取得关键词的下一个字母，回到查找树的根节点继续迭代查找；

3)针对包含多个语义的关键词，输出分词结果。

4.如权利要求1所述的一种基于单词查找树实现的汉语拼音快速分词方法，其特征是，所述步骤四中，完成分词后，销毁查找树，释放资源，回收占用的内存。

5.如权利要求1所述的一种基于单词查找树实现的汉语拼音快速分词方法，其特征是，所述查找树是一种支持多态集合，包括插入、删除和查找操作的数据结构。

说明书

一种基于单词查找树实现的汉语拼音快速分词方法

技术领域

[0001] 本发明属于计算机或各种手持嵌入式可移动设备汉语信息处理技术领域，特别涉及一种基于单词查找树实现的汉语拼音快速分词方法。

背景技术

[0002] 从一串连续的汉语拼音中，通过计算机软件算法自动识别出每个单字拼音，是拼音输入法和搜索引擎（根据拼音型关键字再联想汉语语句）必须要使用的技术。将现存的所有汉语单字拼音作为关键字，建立一个哈希表，分词时通过从建立的哈希表中多次查找和匹配，可以实现将一串连续的汉语拼音进行分词，但此方法存在效率不高的问题。

[0003] 为提高效率，现有技术中对上述哈希表做出如下改良：以汉语单字拼音的首字母作为关键字，建立一个哈希表，哈希表每个元素都是一个单向链表，链表中存储着以哈希表关键字字母为开头的所有单字拼音。这样经过改良后，每次查找时，先根据首字母从哈希表中快速得到一个单向链表的首节点指针，然后再遍历单向链表，做出最终匹配。使用经过改良的哈希表已经提高了分词效率，但在处理多义词，诸如“xian”“piao”时，依然会存在需要特殊处理的问题，比如检索到“xi”后，一种方案是立即将“xi”从字串中移除，接下来继续检索“an”，但这样拼音“xian”就丢失了；第二种方案是在字串中保留“xi”，继续检索以字母x开头的拼音，直至找到单向链表的末尾，然后再移除“xi”，最后再继续检索“an”，这样就可以找到所有可能的拼音方案“xi”“an”“xian”，但这种方案查找效率比较低下。

[0004] 中国专利（专利号：200710118921），一种电话号码映射域名服务器的内存处理方法及装置，这项专利虽然提到了查找树和哈希表，但是这项专利只是使用了查找树和哈希表存储和查找的基本功能，并没有经过任何的改良，也没有任何的延伸和改进；而且在使用的用途上也存在根本不同，此专利只是在查找树和哈希表的节点上存储了数据，只是单纯通过查找树和哈希表找到存储的数据的功能，而本发明主要实现的是通过查找树和哈希表的一种变种的结合完成汉语拼音快速分词，这项专利是查找存储的数据，本发明是完成汉语拼音的快速分词，两个文件在使用方式和用途上存在本质的区别。

[0005] 中国专利（专利号：200810129141.8），调整候选词顺序的方法和装置，这项专利虽然提到了查找树和哈希表，但是此专利中的检索树只是用到了查找树或者哈希树中的一种，并没有如本发明中一样把查找树和哈希表结合起来使用，在本发明中两者紧密结合，缺一不可；而且用途也不一样，此专利调整候选词顺序的方法和装置只是利用查找树或者哈希表进行存储，判断存储的拼音串是否为标准全拼，使用查找树或者哈希树并不是用作分词的功能，而本发明使用查找树和哈希树的变种的结合完成拼音的快速分词，最终形成拼音串。

[0006] 中国专利（专利号：200910107961.1），一种快速分词的实现方法，这项专利虽然也是一种分词的方法，但是此专利查找树是由一级索引表和HASH多叉树实现的，此专利的不足是：在处理多义词时，容易造成丟词的情况；如果不想出现丟词的情况，就需要采取降低查找效率的方法解决，虽然保证了查找结果的正确性，但是最直接后果就是造成了查找效率比较低下的问题。

[0007] 上述方案中的单向链表虽然有诸如内存中易维护、插入删除简单等优点，但存在查询性能低下、查找效率低或丟词的缺点。

发明内容

[0008] 本发明的目的就是为了解决上述问题，提供一种基于单词查找树实现的汉语拼音快速分词方法，将查找树与哈希表结合，使用哈希树的一种变种来完成对汉语拼音的快速分词，此种分词方式既避免了查询性能低下、效率低、丟词的问题，又提高了查找效率，实现了快速分词。

[0009] 为了实现上述目的，本发明采用如下技术方案：

[0010] 一种基于单词查找树实现的汉语拼音快速分词方法，该方法通过计算机或者嵌入式可移动设备来实现，主要工作步骤如下：

[0011] 步骤一、根据所有已知的汉语单字拼音表建立汉语单字拼音查找树；

[0012] 步骤二、依据已建立的单词查找树，将查找树与哈希表结合，对给定的一串汉语拼音进行分词；

[0013] 步骤三、给出分词结果；

[0014] 步骤四、销毁查找树，释放资源。

[0015] 所述步骤一中，根据所有已知的汉语单字拼音表建立单字拼音查找树，主要包含以下步骤：

[0016] （1）根节点不包含字符，除根节点外每一个节点都只包含一个字符；

[0017] （2）每个节点的所有子节点包含的字符都不相同；

[0018] （3）除叶子节点外，每个节点都有一个长度为26的哈希表，哈希表以26个英文字母的升序为索引，每个元素分别存储一个子节点，且子节点实际个数小于或等于26；

[0019] （4）每一个节点都包含一个标识字段，此字段取值0或1，用来标识从根节点到此节点，路径上经过的字符连接起来是否代表一个完整的汉语单字拼音。

[0020] 所述步骤二中，依据已建立的单词查找树，将查找树与哈希表结合，对给定的一串汉语拼音进行分词，主要包含以下步骤：

[0021] a)从根结点开始一次搜索；

[0022] b)取得要查找关键词的第一个字母，并根据该字母从哈希表中选择对应的子树并转到该子树继续进行检索；

[0023] c)在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索；

[0024] d)迭代过程：取得关键词的第1、2……n个字母，继续查找。

[0025] 所述步骤三中，具体步骤如下：

[0026] 1）在某个结点处，如果关键词的所有字母已被取出或节点的标识字段取值为1，则从根路径到当前节点依次输出所有字符和当前节点的标识字段值。

[0027] 2）如果关键词所有字母已被取出，即完成查找；否则取得关键词的下一个字母，回到查找树的根节点继续迭代查找。

[0028] 3）针对包含多个语义的关键词，例如：piao，既可以解释成“票”，也可以解释成“皮袄”，分词结果将输出所有可能的值。

[0029] 所述步骤四中，完成分词后，销毁查找树，释放资源，回收占用的内存。

[0030] 所述查找树是一种支持多态集合，包括插入、删除和查找等操作的数据结构。

[0031] 所述哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。

[0032] 本发明的有益效果：

[0033] 此发明在计算机或各种手持嵌入式可移动设备汉语信息处理技术领域是一个新的突破，全面解决了丟词、查找效率低的问题，提供了一种汉语信息处理技术领域的新思路。

[0034] 本发明利用字符串的公共前缀来节约构造空间，最大限度地减少无谓的字符串比较，这样不仅提高了拼音的查找效率，也会有效提高计算机或者各种手持嵌入式可移动设备的内存使用效率，有效提高了各种设备的运行效率；

[0035] 本发明利用带索引的冗余哈希表来提高查询效率，最大限度减小算法的时间复杂度。有效减少了节点的搜索数目，有效提高了算法的实时性，并保证了查找的准确性。同时，也有效提高了查询效率和有效节省了查询时间。

[0036] 本发明的分词方式既避免了查询性能低下、效率低、丟词的问题，又提高了查找效率，实现了快速分词。在分词技术上是一个新的突破，由于查询效率提高，分词效率提高，相应的也会提高汉语拼音使用者的工作效率，节省劳动时间,降低劳动强度。

附图说明

[0037] 图1：查找树分词流程图；

[0038] 图2：查找树的结构图；

[0039] 图3：分词过程流程图。

具体实施方式

[0040] 下面结合附图与实施例对本发明作进一步说明。

[0041] 如图1所示，首先根据现有汉语单字拼音表建立一个查找树和哈希表结合的哈希树，然后对给定的一串连续的汉语拼音进行分词，给出分析结果，最后销毁查找树，释放资源，回收内存。

[0042] 建立哈希树，根据所有已知的汉语单字拼音表建立一个单词查找树。查找树的根节点不包含字符，除根节点外每一个节点都只包含一个字符。查找树的每个节点的所有子节点包含的字符都不相同。查找树除叶子节点外，每个节点都有一个长度为26的哈希表，哈希表以26个英文字母的升序为索引，每个元素分别存储一个子节点，且子节点实际个数小于或等于26。查找树除根节点外，每一个节点都包含一个标识字段，此字段取值0或1，用来标识从根节点到此节点，路径上经过的字符连接起来是否代表一个完整的汉语单字拼音。

[0043] 分词处理，依据已建立的单词查找树，对给定的一串汉语拼音进行分词。从根结点开始一次搜索。取得要查找关键词的第一个字母，并根据该字母从哈希表中选择对应的子树并转到该子树继续进行检索。在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。同样的步骤，取得关键词的第三个、第四个、第n个字母，并对相应的子树进行检索。

[0044] 输出分词结果，在某个结点处，关键词的所有字母已被取出或节点的标识字段取值为1，则从根路径开始到当前节点依次输出所有字符和当前节点的标识字段值。如果关键词所有字母已被取出，即完成查找；否则取得关键词的下一个字母，回到查找树的根节点继续迭代查找。针对包含多个语义的关键词，例如：piao，既可以解释成“票”，也可以解释成“皮袄”，分词结果将输出所有可能的值。

[0045] 销毁哈希树，完成分词后，销毁哈希树，回收占用的内存。

[0046] 如图2所示，限于篇幅，图中只列出了部分具有代表性的汉字拼音。

[0047] “a”，根节点包含一个标识字段（取值0）和一个哈希表，从根节点哈希表的第一个元素（代表字符为a的子节点）往下，第一级子节点（字符为a）也同样包含一个标识字段，这时标识字段取值为1，因为字母a即代表一个完整的汉语拼音单字发音。

[0048] “ai”“an”“ao”，继续字符为a的节点，它也有一个哈希表，因为同样以字母a开头的不只“啊”一个拼音，还有“ai”“an”“ao”，所以a节点有字符为“i”“n”“o”的三个子节点，并且三个子节点的标志字段都取值为1。

[0049] “ang”，同样，字符为n的节点也在哈希表中包含了一个字符为g的子节点，且子节点的标志位也为1。所以将从根节点开始的路径上经过的a–n–g连接后得到拼音“ang”。

[0050] “pi”“po”“pian”，推导原理同上。

[0051] 如图3所示，本流程图中部分使用类C的伪代码来描述子流程。

[0052] 整个流程图，描述了完整的分词过程，细分为一个主流程和三个子流程。包括处理拼音串中的多义词方法，处理多义词时，使用了递归调用方式。

[0053] 流程的开始是输入一串汉语拼音和初始化局部变量，pc1用来记录一次单字分词的开始；pc2是一个动态游标，标识当前字符；pc3用来记录一次单字分词的结束，目的是为了处理多义词；pt是一个动态游标，标识当前查找树节点。

[0054] 主流程是一个迭代过程，根据pt节点的标志位、pc2指向的字符和pt节点的子节点的值进行一系列的判断，然后再跳转到不同的子流程。

[0055] 主流程的工作步骤为：

[0056] 步骤1，输入待分词拼音串；

[0057] 步骤2，声明下列变量：（1）字符指针pc1,pc2,pc3，（2）查找树节点指针pt；pc1=pc2指向拼音串的第一个字符pc3=null;

[0058] 步骤3，pt＝查找树的根节点；

[0059] 步骤4，判断pt节点的标识字段是否等于1，如果是就进入子流程1，如果否就进入步骤5；

[0060] 步骤5，判断pc2指向的字符是否为空，如果是就进入子流程2，如果否就进入步骤6；

[0061] 步骤6，判断以pc指向的字符为索引，在pt节点的哈希表中能否找到子节点；如果是就进入步骤7；否则进入子流程3；

[0062] 步骤7，执行pc2++，pt=子节点；返回步骤4；

[0063] 子流程1，当pt节点的标识位为1时，代表找到了一个完整的单字拼音，此时输出此单字拼音，然后根据pc3（多义词标记变量）的值继续递归处理多义词，最后跳转回主流程。

[0064] 子流程1的详细步骤为：

[0065] 步骤（1-1），输出从pc1到pc2-1指向的所有字符，并报告此为一个单字拼音；

[0066] 步骤（1-2），判断pc3是否为空，如果是就进入步骤（1-4），如果否就进入步骤（1-3）；

[0067] 步骤（1-3），截取从pc3到pc2-1指向的所有字符，从本流程的开始递归调用，进入步骤（1-4）；

[0068] 步骤（1-4），pc3=pc2；返回主流程的步骤5。

[0069] 子流程2，pc2指向的字符为空时，代表已经到达待分词拼音串的结尾，此时如果pc1（代表一次单字分词的开始）不等于pc2，输出pc1到pc2-1指向的所有字符，并报告为非法字符串，最后跳出整个分词流程。

[0070] 子流程2的详细步骤为：

[0071] 步骤（2-1）判断pc1是否等于pc2，如果是就结束，如果否就进入步骤（2-2）；

[0072] 步骤（2-2）输出从pc1到pc2-1指向的所有字符，并报告此为非法字符串，然后结束。

[0073] 子流程3，在pt（当前查找树节点）的子节点中未找到匹配的节点，此时根据pc3（多义词标记变量）的值做进一步判断，如果pc3为空值，则代表遇到了非法的字符（例如字符i，其不是任何汉语单字拼音的开始字符），输出此非法字符，重置变量后，跳转到主流程的开始；否则代表需要回到pc3的位置（例如pipi，现在pc1在串的开头，pc2和pc3都在第二个p的位置），同样是重置变量值后，跳转到主流程的开始。

[0074] 子流程3的详细步骤为：

[0075] 步骤（3-1）：判断pc3是否为空，如果是，进入步骤（3-2）；如果否，就进入步骤（3-6）；

[0076] 步骤（3-2）：输出从pc1到pc2指向的所有字符，并报告此为非法字符串；进入步骤（3-3）；

[0077] 步骤（3-3）：判断pc1==pc2是否成立，如果是，就进入步骤（3-4），如果否，就进入步骤（3-5）；

[0078] 步骤（3-4）：pc2++;进入步骤（3-5）；

[0079] 步骤（3-5）：pc1=pc2;进入主流程的步骤3；

[0080] 步骤（3-6）：pc1=pc3；pc2=pc3；pc3=null；进入主流程的步骤3。

[0081] 上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。