石家庄经济学院本科生毕业论文
主要有：基于Trie索引树的词典、基于整词二分法的词典和逐字二分法的分词词典机制。 下面首先介绍下着几类词典机制，然后再讲述本系统采用的词典机制。 3.2.1 基于整词二分法的词典[7]
首字HASH表
入口项个数
第一项指针
词索引表
词典正文指针
啊 阿 ?? 大 ?? 鼾 顸 005 089 ?? 794 ?? 002 000 . . ?? . ?? . ^ . . . . . . ?? . . . ?? .
词典正文 啊 啊哈 啊呀 啊哟 啊唷 阿 阿Q ?? 鼾声
图3-4基于整词二分法的词典机制
如图3-4 ，基于整词二分法的词典机制包括首字散列表、词索引表、和词典正文三部分。其中，首字散列表是根据所有的首字确定一个影射,由该字可以直接定位到该字对应的入口该入口包括以下部分:数组长度(以该字开始的词的个数)和 数组首指针(该字开始的词列表的开始位置)；词索引表包括词典指针，因为词典长度可以变化，所以需要选择不定长存储；词典正文是以词为单位的有序表,可以实现二分查找 ，当我们获得首字后，可以进行多次试探，来检索所需要的词语。这种算法的数据结构简单占用空间小构建及维护也简单易行但由于采用全词匹配的查询过程效率较为较低。 3.2.2 基于Trie 索引树的词典[7]
- 14 -
石家庄经济学院本科生毕业论文
首字Hash表 入口项个数 子树指针 啊 阿 ?? 大 ?? 鼾 顸 005 089 ?? 794 ?? 002 000 . . ?? . ?? . ^ 大字的TRIE索引树 关键字 子树大小 子树指针 ^ 案 把 坝 白 ?? 0 2 2 0 5 ?? . . . . . ?? ^ 要 0 1 . . ^ 菜 话 鼠 天 0 0 0 0 0 . . . . . 大 案 案 0 . 大 白 大 白 菜 大 白 话 大 白鼠 大 白天 大案要案 图3-5 基于TRIE索引树的词典机制
如图3-5所示，基于TRIE索引树的分词词典机制由首字散列表和TRIE索引树结点两部分组成。
TRIE索引树的优点是在对被切分语句的一次扫描过程中，不需预知待查询词的长度，沿着树链逐字匹配即可；缺点是它的构造和维护比较复杂，而且都是单词树枝(一条树枝仅代表—个词)，浪费了一定的空间。
3.2.3 基于逐字二分法的分词词典[7]
这种词典机制是前两种机制的一种改进方案。逐字二分与整词二分的词典结构完全一 样，只是查询过程有所区别：逐字二分吸收了TRIE索引树的查询优势，即采用的是“逐字匹 配”，而不是整词二分的“全词匹配”，这就一定程度地提高了匹配的效率。但由于采用的仍是整词二分的词典结构，使效率的提高受到很大的局限。 3.2.4 本文的分词词典机制———子字典机制
本文在吸取了以上词典的基础上，通过对汉字编码体系和中文分词特点的分析，采用了一种新的词典机制：子字典机制，这种词典是由一个链表实现的词典，在词典里每一项都是一个子词典的数据结构，以便在词典库中快速查找词。其数据结构如3-6图。
- 15 -
石家庄经济学院本科生毕业论文
字典首项，每项指 向一个子字典
?? ?? n词长
图3-6 基于子字典的分词机制
单词 2词长 3词长
3.3 小结
本章主要讲解了双向匹配的算法思想和算法流程，双向匹配是建立在传统的单向匹配的算法基础上，同时吸取了最大正向匹配和最大逆向匹配算法的优点，同时双向匹配对于发现歧义有一定的优势，对于将来研究消除歧义的算法打下了良好的基础。本章还讲解了基于词典的分词算法的分词机制，由于基于词典的分词机制是建立在“查字典”的基础上，因此，字典在内存中如何存储，这在很大程度上影响了分词的效率，本文提出的子字典机制，将字数相同的词放在一起存储，能够提高分词的效率。
- 16 -
石家庄经济学院本科生毕业论文
4 中文分词系统的设计与实现
在综合了上面讨论的中文分词技术和具体的算法思想的情况下，本文实现了一个可以进行中文分词的系统。编程语言为JAVA，开发环境为Windows 7,编译环境为eclipse。输入为GB2313格式的中文，输出为经过分词的中文。所用训练语料库为来自经典文章和网络新闻，本系统的分词算法采用了基于词典的分词算法，本系统很好的将最大正向匹配算法和最大逆向进行了结合，实现了双向匹配的算法。
由于设计和实现是纯工程性问题，下面将详细讨论这个部分，并附带了字典在计算机内存中的存储数据结构，在第五章对该系统的分词进行了实验验证，实验显示该系统具有较高可行性。
4.1 系统设计与原则
中文分词系统的设计原则包含三个方面：精确性、高效性和可维护性，分别描述如下：
1） 精确性：精确性是最能反映出中文分词系统好坏的核心标准。由于中文本身语言的复杂性，对于中文分词本身所遇到的切分歧义问题、未登录词做到没有错位完全实现几乎是不可能的。所以，如何在现有研究基础上，尽可能的提高分词的精确度是至关重要的。
2）高效性：高效性是反映中文分词系统性能的一项重要指标。由于大多数分词系统是基于词典的，在分词系统过程中需要对对中文语句进行反复的匹配，查找，对计算机而言时间消耗也是一个不小的问题。所以尽可能的提高分词的速度也是我们设计需要遵循的原则之一。
3）可维护性：任何系统必须具有较好的可维护性，中文分词系统也是一样，由于是基于词典的中文分词系统，所以词典的选择应该具有灵活性，在用户想要更换词典的时候应该具有良好的接口，从而使分词系统更加完善，更加具有实用性[8]。
4.2 中文分词系统的设计
本中文分词系统分为四个功能模块：词典加载模块，预处理模块，中文分词模块和分词结果保存模块。其结构如图4-1所示。
- 17 -
石家庄经济学院本科生毕业论文
开始 打开系统 词否 典
加是否添加字典 载模 是 块
选择词典并加载
选择带切分文档 预 处理文本预处理，断句
模 块预处理输出结果
最大正向匹配算法 中文
分 最大逆向匹配算法 词模
块 双向匹配算法 保输出分词结果 存
模 块保存分词结果
结束 图4-1 中文分词系统
1）词典加载模块：在进行分词时面对的是不同长度的词，本文将同一首字下不同长度的词放入不同的子字典，每个子字典的长度是相同的，形成了2字词表、3字词表??等，以链表方式存储。这样我们在进行匹配的时候，对于不同长度的词可以直接定位到以该词的首字为索引的相同长度的子字典，提高了查询速度。另外本系统为了达到系统设计的可维护性，支持字典的选择性加载，用户在进行分词前可以选择加载专业词典或者是用分词自带的字典进行分词，词典的加载需要一定的时间，但是加载词典只需要一次，以后用户就可以直接使用加载过的词典。
2）预处理模块：这个功能模块的作用是对输入的待切分文档进行预处理，识别出明显的非中文字符，例如英文，数字等，从而消除了一部分歧义的产生。具体的流程是对输入的文本进行预处理，在进行分词前，先进行字符检查,检查是否是有效字符,比如是否是中文,英文字符等,包括全角和半角等，如果判断的字符与上一个字符是同一类字符的话则进行下一个判断，如果是不同的字符的话则在两者之间加入空格，例如对于“你的编号是12345，Welcome!”
- 18 -