基于哈希表和二叉树的词典研究(一)

作者:王增才

邮箱: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。

第一字节 第二字节
十进制区位码 17(区码,十进制) 03(位码,十进制)
转换为十六进制区位码 11(区码,十六进制) 03(位码,十六进制)
第一个字节和第二个字节分别加上20(十六进制) 31(十六进制) 23(十六进制)

机内码即国标码在电脑内的编码,它与国标码、区位码有一个对应关系。为了不与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. 百度百科机内码词条

关于王 增才

致力于自然语言理解研究(包括词库、中文分词、句法、语义等方面的研究,开发的产品涉及智能搜索引擎、机器翻译、专家咨询系统、机器人语言系统等人工智能领域)。
此条目发表在中文分词分类目录,贴了, , , 标签。将固定链接加入收藏夹。

基于哈希表和二叉树的词典研究(一)》有 9 条评论

  1. 52nlp说:

    非常感谢!

    [回复]

  2. boycat说:

    太牛了!
    汇编都忘光了,看起来挺费力的了

    [回复]

  3. fool说:

    很好奇:
    1. 为什么要用首字母hash+二叉树,为什么不全部使用hash,是因为内存问题嘛?
    2. 为什么要用汇编?既然是研究,既然是写出来让大家学习,为什么不选择一个高级语言来介绍?难道是做硬件开发集成的,直接把工作中的代码粘过来给大家看?

    [回复]

    王 增才 回复:

    是首字哈希,不是首字母哈希。二叉树,是为了方便分词。(一家之言)。
    采用汇编,是因为我在研究中使用的编程语言就是汇编语言(个人偏好),若有时间,会考虑将其翻译为C语言的。

    [回复]

    necrostone 回复:

    首字母哈希可以看做初选,因为字母表庞大时,查询时间很重要,而后续字母与前出现的字母间存在关系,两者出现的概率不独立,所以可以用别的算法,因为可以节省空间。

    空间和时间复杂度一般就是这种拉锯,成反相关,根据情况选择合适的算法。

    [回复]

  4. necrostone说:

    作者个人能力应该很强,呵呵。

    不过要是想和大家交流算法,最好用规范的伪码,这样便于评估复杂度。

    词典的构建结构可以看Trie,可以参看wiki,并有从Trie衍生出的其他方法。

    [回复]

    911 回复:

    用汇编是因为可以对底层操作更方便,个人认为伪码虽然很抽象,逻辑清晰,容易理解,但要真的让其变成可以执行的代码,还需要阅读者自己翻译一遍,有点麻烦。在此征询下大家的意见,我个人还熟悉C语言,C#语言,看是采用哪种语言来描述算法较好。

    [回复]

  5. zhangkaixu说:

    跟双数组trie树(double-array trie)比呢?
    双数组trie树相当于每个字都是hash(直接查下标),而且不会有任何冲突。
    时间复杂度O(n),n是句子长度,复杂度跟词典大小无关。
    如果是二叉树,复杂度会跟词典大小有关吧。

    [回复]

  6. gooshell说:

    本人也基于哈希表和二叉树开发了的词典检索,具体实现上与楼主不一样,我是采用整词HASH然后对指定的数取模(这个数由调用者在初始化时指定,这个数更大占用的资源越多但性能越好,此数越小占用资源越少但性能越差,可以视具体情况动态调整).

    另外,本人还做了一些优化,比如通过词的长度做额外的标记,可以直接降低比较的次数.本人练手的网站(点击名称可以直接访问)上现有近两百万个词,性能还算可以.

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注