作者：王增才

邮箱：wzc@zencai.com

摘要 词典是许多中文分词系统的一个重要的组成部分。其查询速度直接影响到分词系统的处理速度。本文使用汇编语言设计了一种高效的基于哈希表和二叉树的分词词典。

关键词 中文分词 哈希表 二叉树 词典

Study on Chinese Word Segmentation Based on Hash Table and Binary Tree

Abstract 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（十六进制）。

下面我们来看一个验证上述理论的程序：

源代码a.asm：

.386

.model flat,stdcall

option casemap:none

include windows.inc

include user32.inc

includelib user32.lib

include kernel32.inc

includelib kernel32.lib

.data

szCaption db '消息框!',0

;汉字“保”的机内码

szText db 0b1h,0a3h,0

.code

start:

invoke MessageBox,NULL,offset szText,offset szCaption,MB_OK

invoke ExitProcess,NULL

end start

Makefile文件：

NAME=A

OBJS=$(NAME).obj

LINK_FLAG=/subsystem:windows

ML_FLAG=/c /coff

$(NAME).exe:$(OBJS)

Link $(LINK_FLAG) $(OBJS)

.asm.obj:

ml  $(ML_FLAG) $<

clean:

del   *.obj

我们使用机内码到其区位码的映射作为哈希函数。假设汉字的机内码key的第一个字节为char1，第二个字节为char2，即

f(char1)=(char1-160)

f(char2)=(char2-160)

f(key)=f(char1)*256+f(char2)-257

源代码B.asm如下：

.386

.model    flat,stdcall

option    casemap:none

include   windows.inc

include    user32.inc

includelib              user32.lib

include   kernel32.inc

includelib             kernel32.lib

include    HashTable.inc

include    masm32.inc

includelib       masm32.lib

include           ole32.inc

includelib       ole32.lib

.data

;哈希表的初始化

HashA     HashTable       23902    dup(<0,0>)

szCaption       db    '消息框!',0

szText     db               60000     dup(0)

filePath db 'e:\gb2312.txt',0

.code

; 用机内码到其区位码的映射创建哈希表的一个结点

;ht:ptr HashTable

;key:word--机内码

CreateNode    proc              uses        esi  ebx  ht:ptr    HashTable,key:word,data:dword

local char1:byte

local char2:byte

mov              esi,ht

mov        ax,key

;char1=ah,char2=al

;f(key)=(char1-160)*256+(char2-160)-257

;计算出存储位置

mov char1,ah

mov char2,al

sub  ah,160

mov ebx,256

movzx eax,ah

mul  ebx

movzx     ebx,char2

add  eax,ebx

sub  eax,417

mov              ebx,type               HashTable

mul               ebx

add               esi,eax

;寻址

mov        ax,key

mov        (HashTable   ptr [esi]).key,ax

mov              eax,data

mov        (HashTable    ptr        [esi]).data,eax

ret

CreateNode           endp

;用机内码到其区位码的映射查找某个结点

;返回data

HashSearch           proc        uses      esi ebx  ht:ptr      HashTable,key:word

local char1:byte

local char2:byte

mov              esi,ht

mov        ax,key

;char1=ah,char2=al

;f(key)=(char1-160)*256+(char2-160)-257

;计算出存储位置

mov char1,ah

mov char2,al

sub  ah,160

mov ebx,256

movzx eax,ah

mul  ebx

movzx     ebx,char2

add  eax,ebx

sub  eax,417

mov              ebx,type               HashTable

mul               ebx

add               esi,eax

mov eax,(HashTable       ptr [esi]).data

ret

HashSearch    endp

;初始化哈希表

InitHashTable               proc        uses      esi ebx  ht:ptr      HashTable

local key:word

local i:dword

local j:dword

mov              esi,ht

mov eax,1

mov i,eax

mov j,eax

;机内码key=(区码+160）*256+（位码+160）

AreaFor:

;区码i

mov eax,i

cmp eax,95

je InitHashTableReturnLine

mov ebx,1

mov j,ebx

;位码j

PosFor:

mov eax,i

mov ebx,j

cmp ebx,95

je IAddOne

;计算出key

add eax,160

mov ebx,256

mul ebx

mov ebx,j

add eax,ebx

add eax,160

invoke CreateNode,esi,ax,0

inc j

jmp PosFor

IAddOne:

inc   i

jmp AreaFor

InitHashTableReturnLine:

ret

InitHashTable        endp

;将哈希表每个元素的key复制到字符串中

WriteHashTable            proc        uses      esi ebx  ht:ptr      HashTable

local key:word

local i:dword

local j:dword

local index:dword

mov              esi,ht

mov eax,0

mov index,0

mov eax,1

mov i,eax

mov j,eax

;机内码key=(区码+160）*256+（位码+160）

AreaFor:

;区码i

mov eax,i

cmp eax,95

je WriteHashTableReturnLine

mov ebx,1

mov j,ebx

;位码j

PosFor:

mov eax,i

mov ebx,j

cmp ebx,95

je IAddOne

;计算出key

add eax,160

mov ebx,256

mul ebx

mov ebx,j

add eax,ebx

add eax,160

mov ebx,index

mov szText[ebx],ah

inc index

mov ebx,index

mov szText[ebx],al

inc index

inc j

jmp PosFor

IAddOne:

inc   i

jmp AreaFor

WriteHashTableReturnLine:

invoke MessageBox,NULL,offset szText,offset szCaption,MB_OK

invoke write_disk_file,offset filePath,offset szText,index

ret

WriteHashTable     endp

start:

;初始化

invoke    InitHashTable, addr       HashA

invoke     WriteHashTable,addr HashA

mov ax,0b1a3h

invoke     HashSearch,addr HashA,ax

invoke     ExitProcess,NULL

end               start

哈希表结构HashTable.inc：

HashTable       struct

key  word       0

data dword     0

HashTable       ends

nmake文件：

NAME=B

OBJS=$(NAME).obj

LINK_FLAG=/subsystem:windows

ML_FLAG=/c /coff

$(NAME).exe:$(OBJS)

Link $(LINK_FLAG) $(OBJS)

.asm.obj:

ml  $(ML_FLAG) $<

clean:

del   *.obj

参考资料：

1. 孙茂松等，《汉语自动分词词典机制的实验研究》，《中文信息学报》第14卷第1期

2. 胥桂仙等，《中文文本挖掘中的无词典分词的算法及其应用》，《吉林工学院学报》，2002年3月

3. 姚兴山，《基于Hash算法的中文分词研究》，《现代图书情报技术》，2008年第3期

4. 黄新亚等，《信息编码技术及其应用大全》，电子工业出版社，1994年8月

5. 国家标准局，《信息交换用汉字编码字符集—基本集》，1981年5月

6. 百度百科机内码词条