2024年6月12日发(作者：)

(19)中华人民共和国国家知识产权局

(12)发明专利说明书

(21)申请号 CN2.4

(22)申请日 2012.04.27

(71)申请人 清华大学

地址 100084 北京市海淀区100084-82信箱

(72)发明人 王瑀屏 汤茂杰 白石

(74)专利代理机构 北京清亦华知识产权代理事务所(普通合伙)

代理人 张大威

(51)

(10)申请公布号 CN 102662491 A

(43)申请公布日 2012.09.12

权利要求说明书 说明书 幅图

(54)发明名称

一种基于八叉树的拼音输入法

(57)摘要

本发明提出了一种基于八叉树的拼

音输入法，该拼音输入法包括如下步骤：

首先，将字词库中的字和词组织为带统计

信息的八叉树叶子节点；然后，建立八叉

树系统，将所有需要的字和词存储到八叉

树中，中间节点存入访问频率值；再后，

在八叉树上查找并快速返回请求的字或

词；最后，将八叉树中间节点、叶子节点

按使用频率进行排序。本发明的基于八叉

树的拼音输入法能够自动建立和组织用于

管理汉字和词的高效八叉树结构，通过对

汉字库中的字和词进行快速有效的组织，

实现字和词的合理存储并被高效的定位，

提高了字词的查找和定位速度。

法律状态

法律状态公告日

法律状态信息

法律状态

权 利 要 求 说 明 书

1.一种基于八叉树的拼音输入法，其特征在于，包括如下步骤：

S1：将字词库中的字和词组织为带统计信息的八叉树叶子节点；

S2：建立八叉树系统，将所有需要的字和词存储到八叉树中，中间节点存

S3：在八叉树上查找并快速返回请求的字或词；

S4：将八叉树中间节点、叶子节点按使用频率进行排序。

2.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在所述

叶

3.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在所述

4.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在所述

入访问频率值；

步骤S1中，所述八叉树叶子节点中存储有对应拼音的字和词，所述八叉树

子节点的统计信息中包含对应叶子节点的字和词被调用的次数。

步骤S2中，建立八叉树系统的规则包括：八叉树的根节点不包含拼音字母，

仅记录查找字或词的次数。

步骤S2中，建立八叉树系统的规则还包括：对字词库中的所有字和词的首

字 母进行统计，选出具有字和词的数量最多的7个首字母，根节

点是这7个首字母，最后一个子节点不包含字母，

个子节点是具有字和词的数量次多的7个

母，以此类推，直到所有字

点的前7个子节

不包含字母的子节点的前7

首字母，最后一个节点不包含首字

和词的首字母都包含在八叉树中。

5.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在所述

步骤S2中，建立八叉树系统的规则还包括：

从根节点到子节点形成一个路径，在路径上的字母依次排列形成对应子节

点的拼音，叶子节点存储字和词的内存地址，对

个叶子节点进行存储； 于有相同拼音的字和词，用多

中间节点和叶子节点中都记录该节点及相关子节点中字和词被选中的次

数；

对于词组，其各个字的首字母组成的路径的最后一个叶子节点指向存储所

6.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在所述

的

述词组的内存地址。

步骤S3中，当需要全拼模式时，按照八叉树从根向下的顺序逐个查找对应

字母，到达叶子节点时即返回相应的字和词；当需要智能拼音

叉树从根向下的顺序逐个查找对应的字母，对于

子节点包含的叶子节点所对应的字

模式时，按照八

路径上的最后一个节点的所有

和词都返回。

7.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在所述

点

步骤S4中，将八叉树中间节点按使用频率进行排序的方法为：根据中间节

的子节点中字和词的被选中次数重新排列包含字母的中间节点

权利要求4-5中所述的建立八叉树系统的规则。 的顺序，规则同

8.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在所述

点

步骤S4中，将八叉树叶子节点按使用频率进行排序的方法为：根据叶子节

对应的字和词被选中的次数重新从大到小排列叶子节点的顺序，

子节点对应的字和词也在字词库中排在前面。 排在前面的叶

9.如权利要求1所述的基于八叉树的拼音输入法，其特征在于，在步骤

S5：将新词加入到八叉树中。

10.如权利要求9所述的基于八叉树的拼音输入法，其特征在于，所述将

S4后还具有以下步骤：

新词加入到八叉树中的方法为：当新词被记录下

来时，生成新的叶子节点对其 进行记录，所述新的叶子节点排在

具有相同拼音的字和词的叶子节点的前面。

说 明 书

技术领域

本发明属于拼音输入技术领域，涉及一种字、词的组织和查找方法，特别

背景技术

拼音输入法是一种将各种拼音字母输入到计算机系统中且在汉语地区被

的

广泛应用的拼音编码方法。拼音输入法基于汉字的拼音规则，去除了拼音中

声调，通过计算机的键盘输入相应的拼音字母来进行字和词的输入操

来说，拼音输入法对字母的大小写不敏感，但若同时输入英文

取小写字母作为输入，而将大写字母作为英文输入。拼

种类型，即，全拼输入法、首字母输入法和双拼

通过输入所需字或词的拼音中的全部字母，

涉及一种基于八叉树的拼音输入法。

作。一般

则拼音输入法只

音输入法大体可分为三

输入法。其中，全拼输入法是

如：“音”-“yin”，“拼音”- “pinyin”等。首字母输入法(简拼输入法)是通过

中的第一个字母，如：“音”-“y”，“拼音”-“py”等。

汉语拼音中各个含多个字母的声母或韵母映射到

可以用最多两次按键打出，但是，双拼输

输入法结合在一起的输入方法。

输入所需字或词字的拼音

双拼输入法是通过将

不同的按键上，使得每个音都

入法的效率低于全拼输入法和首字母

目前，被广泛应用的输入法主要有搜狗拼音输入法、QQ拼音输入法、百

度输入法、紫光华宇拼音输入法、微软拼音输入法、谷歌拼音输入法和智能

ABC输入法。搜狗拼音输入法是由搜狐

汉字拼音输入法，基于搜索引擎技

汉语拼音输入法软件，运行

司基于百度搜索技术，

公司推出的一款Windows操作系统下的

术。QQ拼音输入法是腾讯公司开发的一款

于Windows操作系统系统下。百度输入法是百度公

通过建立内容丰富的词库，建立的支持Windows操作系 统系统的输入

文字、法。紫光华宇拼音输入法是紫光华宇自主开发基于汉语拼音的中

词及短语输入法。微软拼音输入法是一种基于语句的智能型的拼音输入

互

法，提供了模糊音设置。谷歌拼音输入法支持短句和长句输入，词库包含了

联网上的流行语汇和热门搜索词。以上这些主流输入法都不是基于八

入法，而八叉树技术在非图形学领域能够形成易操作且查找信

据结构。因此，利用八叉树技术实现字词的高速查找和

叉树的输

息效率极高的数

定位是一个重要课题。

发明内容

本发明旨在至少解决现有技术中存在的技术问题，特别创新地提出了一种

为了实现本发明的上述目的，本发明提供了一种基于八叉树的拼音输入

S1：将字词库中的字和词组织为带统计信息的八叉树叶子节点；

S2：建立八叉树系统，将所有需要的字和词存储到八叉树中，中间节点存

S3：在八叉树上查找并快速返回请求的字或词；

S4：将八叉树中间节点、叶子节点按使用频率进行排序。

本发明的基于八叉树的拼音输入法能够自动建立和组织用于管理汉字和

词的高效八叉树结构，通过对汉字库中的字和词进行快速有效的组织，实现

入访问频率值；

法，其包括如下步骤：

基于八叉树的拼音输入法。

字

和词的合理存储并被高效的定位，提高了

字词的查找和定位速度。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中

图1本发明基于八叉树的拼音输入法的流程图；

图2是本发明基于八叉树的拼音输入法的一个从拼音对应到字词的实施

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自

始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元

件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，

理解为对本发明的限制。

例的结构组织示意图。

将变得明显和容易理解，其中：

述中变得明显，或通过本发明的实践了解到。

而不能

在本发明的描述中，需要理解的是，术语“纵向”、“横向”、“上”、“下”、

本

“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”“内”、“外”等指

示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述

发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定

以特定的方位构造和操作，因此不能理解为对本发明的限制。的方位、

本发明提供了一种基于八叉树的拼音输入法，如图1所示，其包括如下步

S1：将字词库中的字和词组织为带统计信息的八叉树叶子节点；

S2：建立八叉树系统，将所有需要的字和词存储到八叉树中，中间节点存

S3：在八叉树上查找并快速返回请求的字或词；

S4：将八叉树中间节点、叶子节点按使用频率进行排序。

图2是本发明基于八叉树的拼音输入法的一个从拼音对应到字词的实施

织

例的结构组织示意图。要从拼音对应到字词，首先，将字词库中的字和词组

为带统计信息的八叉树叶子节点，在八叉树叶子节点中存储有对应拼

词，八叉树叶子节点的统计信息中包含对应叶子节点的字和词

然后，建立八叉树系统，将所有需要的字和词存储到八

访问频率值，在本实施方式中，建立八叉树系统

不包含拼音字母，仅记录查找字或词的次

母进行统计，选出具有字和词的数

点是这7个首字母，最后一

个子节点是具有字和

母，以此类推，直到

首字母为i、

有字母；

入访问频率值；

骤：

音的字和

被调用的次数。

叉树中，中间节点存入

的规则包括：八叉树的根节点

数；对字词库中的所有字和词的首字

量最多的7个首字母，根节点的前7个子节

个子节点不包含字母，不包含字母的子节点的前7

词的数量次多的7个首字母，最后一个节点不包含首字

所有字和词的首字母都包含在八叉树中，由于汉字中没有

v、u的字和词，因此，八叉树中的首字母为除i、v、u之外的所

这样，从根节点到子节点就形成了一个路径，在路径上的字母依次排

列形成对应子节点的拼音，叶子节点存储字和词的内存地址，对于有相同拼

音 的字和词，用多个叶子节点进行存储；中间节点和叶子节点中都记录

相关子节点中字和词被选中的次数；对于词组，其各个字的首

的最后一个叶子节点指向存储所述词组的内存地址。

该节点及

字母组成的路径

建立起八叉树系统后，在八叉树上查找并返回请求的字或词的方法为：当

需要全拼模式时，按照八叉树从根向下的顺序逐个查找

节点时即返回相应的字和词；当需要智能拼音模

顺序逐个查找对应的字母，对于路径上的

子节点所对应的字和词都返回。

对应的字母，到达叶子

式时，按照八叉树从根向下的

最后一个节点的所有子节点包含的叶

在八叉树上查找并返回请求的字或词后，将八叉树中间节点、叶子节点按

字

使用频率进行排序，具体中间节点的排序方法为：根据中间节点的子节点中

和词的被选中次数重新排列包含字母的中间节点的顺序，规则同建立

统的规则。具体叶子节点的排序方法为：根据叶子节点对应的

次数重新从大到小排列叶子节点的顺序，排在前面的叶

在字词库中排在前面。

八叉树系

字和词被选中的

子节点对应的字和词也

在本实施方式中，在将八叉树中间节点、叶子节点按使用频率进行排序后

词

还可以具有以下步骤，即将新词加入到八叉树中，具体的方法可以为：当新

被记录下来时，生成新的叶子节点对其进行记录，所述新的叶子节点

相同拼音的字和词的叶子节点的前面。 排在具有

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、

说

“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体

特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本

明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。

而且， 描述的具体特征、结构、材料或者特点可以在任何的一个或多

中以合适的方式结合。 个实施例或示例

尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理

解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、

修改、替换和变型，本发明的范围由权利要求及其等同物限定。