分词系统中常用的分词词典机制.doc

分词系统中常用的分词词典机制有:(1)基于整词二分;(2)基于TRIE索引树;(3)基于逐字二分.

、一、基于整词二分的分词词典机制
这是一种广为使用的分词词典机制.其结构通常分为三级，前两级为索引，如图3.1听示。

图3.1基于整词二分的分词词典机制

1.首字散列表
词首字散列函数根据汉字的国标区位码给出。通过一次Hash运算即可直接定位汉字在首字散列表中的序号。也就是将词首字的国标码与其在首字散列表中的序号相对应。我国的GB2312-80标注规定汉语字符的交换码由两个ASCII码构成：第一个是区码，取值从OxA1到OxF7，共87个区，第二个是位码，从OxA1到0xFE，共94位。区码为OxA1到0xAE的存储全角符号，如标点、字母等。GB2312-80汉字的编码空间是BOA1-FIFE，共有72*94=6768个码位，实有6763个汉字，其中一级汉字3755个，接着是5个空位，后面是3008个二级汉字。设id是词首字在首字散列表中的序号，c1和c2是词首字的区码和位码，利用Hash方法求Id则有:
Id=(c1–176)*94+(c2-161)(3-1)
这种Hash方法实质上是一种一一映射。

首字散列表的一个单元包括两项内容：
1)入口项数(4字节)：以该字为首字的词的个数。
2)第一入口项指针(4字节)：指向第一入口项在词索引表中的位置。

2.词索引表
因为词的长度可变(实际系统中还包括附属于该词的各类信息)，故以选择不定长存储为宜，此外必须实现对词的随机访问，这两条决定了必须建立词索引表。词索引表的一个单元仅含一项内容：
1)词典正文指针(4字节)：指向词在词典正文中的位置。

3.词典正文
以词为单位的有序表，词典中的同一首字的词条按升序排列，通过词索引表和词典正文的配合，很容易实现指定词在词典正文中的整词二分快速查找。

在整词二分查询任意一个汉字串W[1…n],W[1]表示该字串首字，W[n]表示首字后面的n个汉字，查询的过程为：
1)根据首字散列表得到W[1]入口项指针和以它为首字的词在词索引表中所占的范围。
2)根据1)中得到的范围在词典正文中对汉字串W[n]进行二分查找。如果查询成功则W[l…n]为分词词典中的一个词.
整词二分法查询的基本原理很简单，但是每次查询都只能对汉字串W[l…n]是否为一个词进行判断，它不能从查询的中间过程中发现汉字串W[1…n]中所有可能包括的词。而且它查询的范围较大，总是在以W[1]为首字的所有词表范围内。而我们在分词过程中，需要得到一个汉字串S中所有可能切分出的词，也就是说要找出S中所有以W[1]为首字的词，如果用整词二分法来查询的话就需要进行多次的试探，即每改变一次待查字串W[1…n]的n值就要对词典进行一次查询，而且每次的查询过程都要在以W[1]为首字的所有词表范围内.因此整词二分法的查询效率不高.

二、基于TRIE索引树的分词词典机制
TRIE索引树是一种以树的多重链表形式表示的键树。
基于TRIE树的分词词典由两部分组成，如图3.2所示。

图3.2基于TRIE索引树的分词词典机制
1.首字散列表
同基于整词二分的分词词典机制。首字散列表的一个单元是所对应汉字的TRIE索引树的根结点.
2.TRIE索引树结点
TRIE索引树结点是以下述结构为单元的，按关键字排序的数组：
关键字(2字节)：单一汉字。
子树大小(2字节)：以从根结点到当前单元的关键字组成的子串为前缓的词的个数。
子树指针(4字节)：子树大小非0时，指针指向子树，否则指向叶子。

在TRIE索引树上查询任意一个词W[1…n]的过程为：
1)根据首字散列表得到W[1]TRIE索引树，沿相应指针移动至目标结点NODE，i=2。
2)在NODE的关键字域中对汉字W[i]进行二分查找。
如果与NODE的第j个单元的关键字匹配成功则沿该单元的子树指针移至目标结点，并令该结点为新的NODE，i=i+1，否则查找失败，退出此过程。
3)重做2)，直到NODE为叶子结点。
4)如果到达叶于结点时i>n，则
查询成功，W[l…n]为分词词典中的一个词，否则查询失败。

与整词二分的分词词典机制形成鲜明对照的是：基于TRIE索引树的分词词典机制每次仅仅只比较一个汉字，不需预知待查询词的长度，且在对汉字串S的一遍扫描过程中，就能得到所有可能切分的词。这种由短词及长词的确定性工作方式避免了整词二分的分词词典机制不必要的多次试探性查询。由于TRIE索引树已蕴含了词条信息，因此词典中不必再显式地罗列词条，可直接存储词的附属信息（叶子指针直接指向这些信息)。
TRIE索引树分词词典机制的主要缺点是其构造及维护比整词二分复杂。

基于TRIE索引树的另外一种构造方式就是：所有字都采用Hash散列的方式。其结构与图3.2基