|
作者：王增才
摘要
关键词 Study on Chinese Word Segmentation Based on Hash Table and Binary TreeAbstract The dictionary mechanism serves as one of the important components in a lot of Chinese word segmentation systems. Its perfomance influences the segmentation speed significantly. In this paper,we design a highly efficient dictionary mechanism in Assemble language, which is based on Hash table and binary tree. Key words Chinese segmentation; Hash table; Binary tree; Dictionary 一 介绍虽然有人提出了不需要词典的中文分词算法，如胥桂仙等人利用统计提出了基于“找最长字共现”原则的分词算法。[2] 但是，不管是基于规则方法还是统计方法，大部分中文分词算法都有自己的词典。词典的查询速度直接影响到分词系统的处理速度。本文使用汇编语言（编译器MASM32V10）设计了一种高效的基于哈希表和二叉树的分词词典。该算法为：将所有的汉字利用哈希表存储，即根据汉字机内码的编码规律，通过直接寻址哈希函数实现词语首字的快速查找，其查找时间为O(1)；然后将首字相同的词语用二叉树存储；最后将二叉树的内存地址与哈希表进行绑定。 二 首字哈希算法一个汉语词典动不动就上十万条词语，词典的查询速度是决定分词算法效率的决定性因素之一。为了提高查询效率，本文词典对词语的首字采用哈希表来存储。 在具体阐述首字哈希算法之前，我们需要明确三个概念：国标码，区位码，机内码。 国标码是汉字信息交换的标准编码，又称汉字交换码。例如中华人民共和国国家标准局于1981年5月颁布了《信息交换用汉字编码字符集—基本集》，代号为GB2312-80，即著名的国标码GB2312-80。该编码共对6763个汉字和682个图形字符进行了编码，每个字符用两个字节表示。[5] 所有的国标码汉字及符号组成一个94行94列的二维代码表中。在此方阵中，每一行称为一个”区”，每一列称为一个”位”。这个方阵实际上组成一个有94个区（编号由01到94），每个区有94个位（编号由01到94）的汉字字符集。每两个字节分别用两位十进制编码，前字节的编码称为区码，后字节的编码称为位码，此即区位码，其中，高两位为区号，低两位为位号。这样区位码可以唯一地确定某一汉字或字符；反之，任何一个汉字或符号都对应一个唯一的区位码，没有重码。如“保”字在二维代码表中处于17区第3位，区位码即为“1703 ”。[6] 国标码并不等于区位码，它是由区位码稍作转换得到,其转换方法为：先将十进制区码和位码分别转换为十六进制的区码和位码，;这样就得了一个与国标码有一个相对位置差的代码，再将这个代码的第一个字节和第二个字节分别加上20(十六进制)，就得到国标码。如：“保”字的国标码为3123H。[6]它是经过下面的转换得到的：1703D－>1103H->+20H－>3123H。
机内码即国标码在电脑内的编码，它与国标码、区位码有一个对应关系。为了不与ASCII码发生冲突，机内码采用的是变形的国标码，其变换方法为：将国标码的每个字节都加上128，即将两个字节的最高位由0改1，其余7位不变，如：由上面我们知道，“保”字的国标码为3123（十六进制），前字节为00110001（二进制），后字节为00100011（二进制），高位改1为10110001（二进制）和10100011（二进制） 即为B1A3（十六进制），因此，“保”字的机内码就是B1A3（十六进制）。 |
|
|
转载▼
