（计算机软件与理论专业论文）基于hash机制的分词词典的设计与实现.pdf

中文攘要 中文摘要 中文作为人类传播信息的重要语言工具之一，中文信息处理已经成为信息 处理领域的热点研究问题。中文自动分词是中文信息处理的重要组成部分，丽 词典处理效率是影响中文自动分词系统性熊的关键因素，因此，建立高效的分 词词典具有显著的意义。本文对中文分词系统的词典结构进行了深入研究，取 得了一定研究成渠，已建予冒家8 6 3 项霹中的垃圾短信监管处理，并将设计豹 算法申请提交了相关专利，主要研究成果如下： 1 比较分析并改进了凡种的词典存储和处理方法：数组数组机制使用数组 存储词条行，采用二分查找，在操作效率上不高，不利于词典的更新；双 字哈希对前谪条两个字哈希，使用深度为2 的憾e 树，结构复杂；西字 哈希机制只对四字成语有效，在应用上有局限性。本文对这些方法作一定 的改进来解决效率问题。 2 根据汉字g b 码的特点，提出了一种比较高效的词典存储算法，将相同首 字的词条作为一个文本行进行存储，而每个词条格式化为：去掉首字词条 名、词条哈希值和裙关属性，提高了存储空闻利用率。 3 利用h 础表在查找效率上优势，提出了基于h a s h 机制的词典查找、更新、 删除、添加等操作新算法。设计一个实用的h 蕊函数，经实验验证冲突 率极小，适合中小型词典，通过将该函数改进为适合大型词典的无冲突 h a s h 函数。 4 实现数组、链表、越阻树、h 劬表( 带极小冲突和无冲突两种) 五种词典结 构算法，对这些算法从时间复杂度和空间复杂度等方面进季亍详细的分析和 评倍，从载入、写出、文件大小和操俸时闻等几个方面进行实验对比，验 证了基于h a s h 机制的词典结构算法在空间利用率比传统算法提高了近2 倍，在时间效率上提高了5 嗡倍。 5 用j a v a 实现了基于h 础机制的词典结构模块，并提出了对该算法在词条 属性上的扩充方案。 关键词：分词词典，h a s h ，a v l 树，t r 压索引树 a b s t r a c t a bs t r a c t ( ：k n e s e1 a n g u a g ei n f 0 眦a 垃o np r o c e s s i n gh a sb e c o m ea p o p u l a rr e s e a r c _ hs u b j e c ti n m ei i l f o m a t i o np r o c 鼯s i n gf i e l da s 也ec 1 1 i n e s eb e c o m 伪a ni i i l p o r t a i l tt 0 0 1f o ri 1 1 f o m l a t _ i o nt r a i l s l i t t i i 培a n dc 0 删m l i l i c a t i o n q 血e s ea u t o m a t i cs e g m t a t i o ni sa ni l i l p o r t 觚t p a r to fc h i n e s ei i l f 0 m a t i o np r o c c s s i l l 岛髓dw o r dp r o c e s s i l l ge 伍c i e n c yi sak e yf a c t o r t 0m ep e r f o 衄趾c eo fc b i n c s ea l l t o m a t i cs e g m 饥t a 石o ns y s t e i l l t h e r e 内r e ，e s t a ：b l i s l l i n ga l l i 曲e 伍c i e n c yd i c t i o n a 巧h 嬲s i g i l i f i c a n tm c a n i l l g h ln l i sp a p w em a d ead e 印s t u d y o nm ed i 甜o n a r ys 砸l c _ t l l r eo fc h i n e s ew o r ds e g m e n t a t i o ns y s t e m s o m eo ft l l er c 础l a c l l i e v e m e n t sw em a d eh a v e b e e nl l s e di i l 也en a t i o n a l8 6 3j u i l km e s s a g em a i l a g e m e n t p r o j e c ta n d 、ea l s o 印p l i e dp a t e n t 如rt h ea l g o r i 1 m s t h em 抽r e s e a r d hr c s m t sa r e 弱 f o l l o w s ： 1s e v e r a lk i n d so fd i 以o n a r ys 锄a g ea n dp r o c e s s i n ga l g o r i 幽 n sw e r ec o m p 鲫e d ， 趾a l y z e d ，a n di i n p r 0 v e d t h ea r r a 【y - a r r a ym e t h o du s e sa 盯a yt 0s t o r a g ew o r d1 i 一 懿柏db i n a r ys e 锄c ha l g 嘶t l l 】【n st 0 丘n dm e m ，b u ti ti sl o wi n 叩e r a 妇ge f j f i c i e - n c ya n dh 嬲ad i s a d v a n t a g ei nm ed i c t i o n a r yu p d a t e t h e ( 1 0 u b l e w o r d - h a s h m e d l o dh a s h e sm e 丘r s t 锕ow o r d s ，u s e sa ( 1 印t l lt w ot r m m 砖b u ti t ss 协j c t u - r ei sc o m p l e x t h ef o u r 、釉r d - h a s hm e m o do i l l yw o r k sf o rf o u r - 、阳r di d i o m ss o t l l e r ea r e1 i l i 】【i t a l j o l l si na p p l i c a t i o n h lt h i sp 印m e s em e m o d sw e r e i i n p r o v e d t os o h r ea l ee 伍d e n c yp r o b l e m 2a c c l o r d i n gt 0m e c h 锄l c t 翻s d c so fc e s eg bc o d e s ，ar e l a t i v d ye 伍c i e ms t - o r a g ea l g o d n l l ni sp r o p o s e d w b 咖r et e n n s 砌c hh a v et l l es 锄ec 印i t a l 舔a s 曲百et e x tl i i l e ，僦l o v en l et e r mc 印i t a l ，t e n nh a s hv a l u ea n dr e l e v 雒ta t 缸i b u t e ss oe v e 巧t 锄c 姐b ef o n n 甜e d ，n l em 锄。巧u s i n ge 伍c i e l l c yi sa l s oe i l l l - a n c e d 3n e wh 砒b a s e dd i c t i o n a 巧s e 锄c h i n 舀u p d a t i n 吕d e l e t i i l ga i l da d d i i l ga l g o r i m n 坞w e r ep r o p o s e da c c o f d i n gt 0 吐l a th a s ht a b l eh a s 鼬a d v a n t a g ei ns e a r d h e 伍c i e n c y w bd e s i 弘e da1 l s e 觚h a s h 劬c t i o n e x p 甜m e 觚s h o wm a t i t sc o l 一 1 i s i o nr a t ei se x 缸锄e l yl o w ，v e 巧s u i t a b l ef o r 锄a l la n dm e d i u m s i z c dd i “o n - a i yl a 唱ed i c t i o n a d e sc a na l s ou s ei ta r e ri i l l p r o v e m e n t s a b s 瞰( 冀 4 5 t h ea 玎a y s ，l i l l k e dl i s t ，a v l 仃e e ，h a s h1 弘l e ( 、) l ，i t hb o mm 诚m a lc o l l i s i o na i l d l l i s i o 玲蠡氆醴掺蚪鑫l g o 矗惑掇sw e 恐遗攀l e m 嘲。df 懿p e 蕊v e 甄硎奄掰鑫d e 鑫 d o t a j l e da n a l y s i sa n de v a l u a 廿o no fm e s ea 1 9 0 r i 锄n so n 缸m ec o m p l c x i t ya 1 1 d 攀a c ec o 撒p l e x i 锣a 蹲e c 螅。w e m p 鲫醯也el l e wm 礤l 醚s 鑫程d 蠡e 乜丽i 畦。曩a l o n e so nl o a d i i l g ，w 订t i n 吕矗l es i z ea n do p e r a t i n gh o u r s ，a n de x p 嘶m e n ts h o w e d m a to u ra l g o r i t h m si s 栅。甑e sh i 曲镙嫩m e m o 拶e 壤c i 铋c y 髓d 纛v et os 坟 如e s 缱曲e r m t i m e e 釜c i 锄c y m a t 也e o l d o n e s 硼kh a s h 小a s e dd i c t i o n a r ys 咖c _ t u r ep r o 黟锄m o d l l l ew a sf i l l i s h e di nj a v a l 黻g u a g e 黼da ne x p a 薹l s i o ns o l 埘强o nw o l 畦蛐穰宝蜒b 瑶销o f 蕊sm 如o dw 鼬 s 颧v e n k e y w o r d s ：s e 舯e i l t a t i o nd i 砸o n a 吼h a s h ，a v l 缸馋，t r i ei n d e x i n g 缸e e i 鬻索零l 图索引 图2 1 词条的记录格式9 图2 - 2 索引文件中的结点结构1 0 图2 - 3 双字哈希槐制1 4 图2 4 词典是内存中的表示 图2 5 相同词条索引项2 0 图2 - 6 词条在磁盘上的存储形式2 0 蚕2 0以“爱”字开头诿条在内存孛的逻辑格式2 2 图3 1 词典结构在内存中的表示2 6 图3 - 2 词条在内存中的表示2 7 图3 - 3 善字在内存孛的结构2 7 图3 4 词典磁盘存储2 7 图3 5 词条行实例2 8 图3 6 词典操作3l 图垂l内存中酶词典结构毒8 图4 - 2 词条在内存中的结构4 8 图4 _ 3词条在磁盘上的存储。4 8 图4 4 词典部分截图。4 9 图4 5 哈希查找流程图。5l 图4 石词条更新流程图5 2 图4 - 7 删除词条流程图，5 2 图垂8 添加词条流程图5 3 图4 9 带序列号的词条结构。5 4 图4 1 0 基于链表的查询流狸图。5 4 图垂ll 基于整毽树调条查找薛流程圈5 5 图4 1 2 测试界面5 6 v i 表索引 表索引 表5 1 算法时间复杂度比较5 7 表5 2 实验结果对比5 9 v i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的资料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：二皇掣日期：年月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行查阅，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：耗 日期：年月日 第一章绪论 第一章绪论 随着中文在全世界的推广和对中文研究的深入，中文信息处理已经成为目前 研究的一个热点问题，而中文分词是中文信息处理的前提，其广泛应用到中文检 索、中文翻译，以及中文垃圾邮件、短信处理上。词典处理的效率是影响中文信 息处理系统性能的关键因素，中文自动分词系统的一个基本组成部分。因此建立 高效快速的分词词典具有显著的现实意义。本文根据分词系统处理的需求提出了 一个新的基于h 础机制的词典存储和操作算法，并对该算法进行设计与实现，来 解决传统算法在时间和空间利用率不高的问题。 1 1 国内外研究现状 在信息处理系统的实用化进程中，分词词典已经成为人们开发的焦点。因为 信息处理的基本信息都来自词典语言知识库。包括两大块内容，其中之一就是词 典，另外一块是语法语义等规则也叫文法，而规则也正是依据分词词典中给出的 种种信息才一步步运算出对自然语言理解的种种结果来。因此可以说分词词典是 语言工程化的基础，没有好的分词词典任何语言工程都无法进行。 在现代语言学理论中语言事实的描写己从语法规则转移到词库上来，即所谓 的词汇语义。随着词汇地位的提高，词典在语言信息处理中变得越来越重要，单 就中文信息处理来说已在字词处理的基础上进一步发展到句处理阶段。要在句处 理上有所突破必须建立大规模的语言知识库，语言知识库主要包括词的语法属性， 词的语义属性，语法语义规则，其中非有语法分词词典、语义分词词典不可。随 着计算机应用领域的拓宽，知识工程的发展信息量的急剧增长，词汇资源日益引 人注目。在计算语言学界越来越多的语言学家和计算语言学工作者视分词词典建 筑的规模和质量为信息处理系统的瓶颈，把其看作是信息处理的支柱和语言工程 的基石【1 1 ，词典是信息处理系统工程化的一个重要方面，因此国外近年来非常重视 分词词典的研究和建设，一些发达国家的政府和企业界投入了巨额资金和大量人 力。 另外随着文本信息处理技术的发展，文本分类和分词研究的深入，分词系统 成为研究中文信息的一个主要方式，目前最为出名的分词系统是由中科院研究的 电子科技大学硕士学位论文 i c t c l a s 免费版本的系统，以此为代表的分词系统在分词时候都要通过调用词典 来匹配所读取的句子的一部分是否能够以词语的形式切分开，所以从词典中的查 询词条的效率直接决定了整个分词系统的效率，由于目前词典的数量迅速增加， 对词典的存储空闻利用率和操俸效率提出更高的要求，另外分词词典是信息处理 所需的重要知识源，它以机器可读形式存储。信息处理过程中的静态信息绝大部 分来自分词词典。一部好的分词词典既要包含信息处理所需的丰富知识( 如：词形、 词性、句法、语义以及搭配信息等) ，又要有灵活的信息组织结构及查询效率，这 些在很大程度上都影响着信息处理的结果。 近年来对分词系统词典的研究己经成了一种专门的学问帮分词词典。分词词 典是信息处理系统工程化的一个重要方面，因此国外近年来非常重视分词词典的 研究和建设，一些发达国家的政府和企业界已经投入了巨额资金和大量人力。1 9 8 6 年日本提出了一个信息处理用的分词词典研究计划。这个计划的目的是实现大型 的、高水平的分词词典，以满足下一代信息处理的需要。为了实现这个蹈标，墨 本政府投资一亿美元并成立了日本分词词典研究所( 简称e d r ) ，计划在九年时间 内，开发包括日语和英语的十部分类词典和概念描写词典等，种类包括基本词典、 术语词典、搭配词典、概念分类词典和概念描写词典等。欧洲共阊体也资助了多 项分词词典的研究课题。 国内爨8 0 年代孛后期就开震了中文电子词典煞研制，最初的一般是按照拼音 来设计分词词典结构的，在文献【2 】中提出了使用汉字拼音来建立和以索引的方式 来检索词典，这种方式效率由于汉字同音字比较多很难设计一个合适的方式来解 决该问题，也有相关的专利描述以拼音的方式建立词典，这些算法效率不高。以 前的词典有采用b + 树( 或其变种) 作为词典索弓l 数据结构洲3 1 ，也有利用现成的关 系数据库技术的闷，还有一些系统由于词汇量不是很大，也有用没有格式化的纯 文本方式的【5 1 。之所以采用b + 树( 或其变种) 作为索引的数据结构，是因为早期计 算机主存容量的不足和操作系统存储管理方式的缺陷，采用这种结构可以有效地 降低i o 次数，提高词典的访问性能。但随着硬件技术的不断提高，主存容量大大 增秀翼，采用b + 树( 或其变种) 作为词典索弓l 数据绪构的优势已基本丧失；另外，嚣前 主流的d b m s 大多采用b + 树( 或其变种) 作为文件组织方式，利用关系数据库技术 构建的词典在访问时也会涉及到大量的的操作，势必影响效率；采用纯文本方式 构建词典，由于数据没有经过有效组织，内部查找时的计算复杂度为o ( n ) ( n 为词 典中的词条数) ，这釉访问效率必须大大改进。 目前眈较流行的分词谲典机制主要有：基于整词二分的词典机制、基于t r 遁阐 2 第一章绪论 索引树的词典机制和逐字二分机制【丌，通过后续章节的分析可知这些算法也存在效 率上的问题，有需要改进的地方，比如整词二分虽然数据结构简单、占用空间小， 构建及维护也简单易行，但由于采用全词匹配的查询过程，效率低下，而基于t r 树的词典机制数据结构复杂、空间浪费较为严重，树的构造和维护也较为繁琐，第三 种分词词典机制( 基于逐字二分) 虽然采用了较为高效的逐字匹配，但并没有改进 “整词二分”的数据结构，使得匹配过程并不是完全意义上的逐字匹配，这就导致查询 效率并没有得到最大限度的提高。 而文献 8 】中提出的使用数组来建立词典的机制是一个比较高效的算法，但是 由于该算法针对相同首字词条也使用数组，这就在更新词典上存在很大的缺陷。 文献 7 】提出了一种双字哈希机制，该机制由三部分组成的：首字h 砒索引、次字 h 砒索引和剩余字串组，双字哈希机制只对前词条两个字哈希，使用深度为2 的 t r i e 树，结构复杂，另外剩余字串组使用的仍然是基于数组的二分查找，存在一 定的效率问题；文献 9 】提出了一种四字哈希机制的词典构造方法，和文献 7 的方 法相似，但是只适合处理四字的成语词条，具有很大的局限性。文献 1 0 提出了一 种使用双数组的机制是一个是对基于t i 皿树的词典机制的一个改进，结构上复 杂，在灵活上有一定的缺陷。文献 8 】及文献 1 1 】【1 2 】 1 3 】和中科院开源分词系统使 用数组一数组词典机制对相同首字词条行的使用数组进行存储的，查找都是二分 查找，时间复杂度为0 ( 1 0 9 n ) ，效率不及h a s h 表，另外由于数组增加和删除元素比较 困难导致更新词典比较低效。本文针对以上问题，采用数组和h 柚表的结合来处 理词典的存储和操作。 词典物理存储一般通过文本或者关系数据库来实现，因为关系数据库会牵涉 到更多的i o 次数，会降低访问的效率，随着目前计算机硬件的发展，计算机内存 已经有足够大来容纳整个词典调入内存中，所以本文通过对文本文件的规划来实 现对词典的物理存储，然后当分词系统在启动时将整个词典调入内存，这样就大 大地提高了词条的查找速度。 总之，为了使分词词典的操作效率与分词系统的分词速度相匹配，近年来对 分词词典的研究越来越深入，设计了多种算法来提高分词词典的操作效率，本文 通过详细分析多个算法之后，提出了一种基于h 础机制的分词词表结构算法。 1 2 本文的选题依据和研究意义 本论文的选题依据是国家高新技术研究发展计划( 8 6 3 计划) 所支撑的项目， 电子科技大学硕士学位论文 该项目的基金号为：2 0 0 6 a a l 0 1 8 4 1 4 3 ，题目为“海量短信流的智能监管及关键技术 研究”，属于信息网络安全领域的范畴，是针对目前垃圾短信的处理而进行的。垃 圾短信问题在国内外移动通信市场都大量存在，而且正日益泛滥。垃圾短信不仅 危害了国家安全，违背了社会主义精神文明建设，扰乱了社会主义市场经济秩序， 干扰了人民群众的正常生活，而且耗费了大量的公共资源，扰乱了信息服务的正 常秩序，造成了严重的不良影响。到了人人喊打的地步，必须严加惩治，对其处 理势在必行。本项目的主要任务就是通过分析短信文本将垃圾短信提取出来，然 后将其过滤掉。 由于基于关键字的内容过滤技术是目前垃圾短信防范的主流技术，该技术不 仅用户过滤垃圾短信，而且被广泛用于垃圾邮件过滤、病毒防治、网络不良信息 过滤等众多领域。因此建立一个关键字词典对与内容过滤技术有很大的帮助，关 键词匹配技术通过预先设定一系列关键词列表，然后检查每一条短消息中是否包 含这些关键词列表中的某个词或者某些词，如果包含则判其为垃圾短信。关键词 匹配的基础是字符串匹配技术。字符串匹配技术已经得到广泛的研究，在文本编辑、 全文检索系统、查询系统、网络入侵检测系统、内容过滤、生物科学计算、新闻 主题提取等众多领域得到广泛的应用，取得了丰硕的成果。 对垃圾短信的处理一般通过内容过滤来判断的，内容过滤时需要抽取短信内 容特征，由于短信长度有限( 般小于7 0 个字符) ，因此表达的内容有限。由于 在国内的垃圾短信以中文为主，可以利用中文分词系统对中文垃圾短信进行分词， 然后通过特征提取提取出特征词建立垃圾短信特征库，从而挖掘出垃圾短信，分 词词典结构的设计是中文分词系统的基础部分，也是提高分词速度的关键所在。 另外，在词典词条内容方面，由于本项目研究的是垃圾短信，短信的特点为长度比较小， 语言简洁导致包含的词语长度一般小于5 个字，短信的另一特点为使用的流行词语比较 多，比较口语化，因此与网络上流行词语比较相似，都是比较新的词语，导致以前的词 条相当一部分已经不适合本项目的研究，本文通过使用搜狗上发布的一个比较新的词典 ( f r e q ) 来解决此问题。 本文针对以上问题来深入研究中文分词词典结构的各种算法，提出了一个高 效的词典操作和存储新算法，设计一个实用的哈希定位函数，并提出了解决冲突 的各种方案，经实验本文提出的词典机制的实用的，很好的解决词典的查找和分 词系统分词速率不匹配的问题以及词典的更新问题，为国家8 6 3 项目的完成提供 了很大的帮助。另外已经将该算法作为一个主要创新点申请提交了一个相关专利， 4 第一章绪论 目前该专利已经通过初审，所以本论文研究的内容不但有理论价值，而且有很大 的实际应用价僮。 l 。3 本文的主要内容 本文针对目前分词词典存储空间利用率和操作效率不高的问题，主要融合各 种电子词典存储算法【卜硪，利用汉字g b 的特点，探索了电子词典存储和处理方法， 提出了一个新的词典存储和操作算法，做了如下研究工作： 1 ) 根据汉字g 8 码的特点，提出了一种跣较高效的存储算法，将相闲首字的 词条作为一个文本行进行存储，而每个词条格式化为：去掉首字词条名、 词条哈希值和楱关属性格式进行存储，从焉提高了物理空间利用率。 2 ) 利用h a s h 表在查找效率上优势，提出了基于h 砒函数的电子词典查找、 更新、删除、添加等操作新算法； 3 ) 设计一个实用的h 袖函数，经实验验证冲突率极小，适合中小型词典，并 通过对该函数改进构造出适合大型词典的无冲突的h a s h 函数； 4 ) 通过实现数组、链表、a v l 树、h a 矗表( 利用带极小冲突和无冲突函数两 种算法) 五种词典结构算法，对这些算法从时间复杂度和空间复杂度等方面 进行详细的分析和评信。 5 】对五种机制从载入、写出、文件大小和操作时间等几个方面进行比较，实 验表明新算法的在空阗效率上比传统算法提高了近2 倍，在时间效率上提 高5 倍。 6 1 详细分析目前常用的分词词典结构算法，包括传统算法五种和比较高效算 法四种，进行对比分桥并对其中一些算法傲相关的改进以提高效率。 7 ) 用j a v a 实现了基于h 釉机制( 带极小冲突和无冲突) 的词典结构算法， 并提崽了以后算法的扩充机制。 本文在对传统上的多种算法和目前比较高效算法深入研究的基础上，提出了 基于h a s h 机制的新算法，通过第五章的理论评估和实验证明该算法具有一定的先 进性，提高了存储空间利用率和操作效率。 1 4 论文组织 本论文其余部分组织如下： 5 电予科技大学磺士学位论文 第二章讨论短信的特点和短信词库的建立方案，介绍了五种传统的和四种比 较高效的分词词典结构算法，对这些算法进行分析对比，以及对部分算法进行改 进。 第三章阐述基于h a 娥机制( 带极小冲突和无冲突算法) 和其镳几种词典结构 算法的设计，并介绍了词条属性的实现方案。 第四章详细阐述基于h a s h 机制( 带极小；孛突和无、冲突算法) 的词典结构算法、 链表解决冲突算法和a v l 树算法的具体实现过程。 第五章对基于h a 始机制( 带极小冲突和无冲突算法) 的词典结构算法、链表 解决冲突算法和a v l 树算法在时间复杂度和空间利用率上进行评估，从载入、写 出、文件大小和操作时间等几个方面实验对比。 第六章描述全文总结与展望。 l 。5 本章小结 本章主要描述了分词词典在国内外的发展现状和在中文处理中的重要地位。 介绍了本文选题的项目支撑以及分词词典和该项醺的研究意义和价值，详细介绍 了研究的内容，对并对本文的剩余部分的规划做简单阐述，后续章节将按照论文 组织方式进行展开。 6 第二章分词词典机制分析 第二章分词词典机制分析 本章介绍了手机短信的特点和词典内容的构建方式，重点描述了常用的和比 较高效的几种分词词典机制，详细分析这些机制，对其优缺点进行对比，另外对 部分算法的缺点提出了改进方案，对基于整词二分的分词词典机制、双字哈希机 制、中科院词典机制中的二分查找部分改成哈希查找以提高查找效率，其中哈希 定位函数使用第三章中设计的哈希函数进行定位，由于二分查找的时间复杂度为 o ( 1 0 印) ，而哈希查找一般一次就能成功( 解决冲突后要增加一定的时间复杂度) ， 因此大大提高了查找上的时间复杂度。 2 1 词典内容构建 本节分析了手机短信的一些特点和目前词典内容的构建方式，最后描述了针 对手机短信词典内容的构建方式。 2 1 1 词典内容构建方式 目前建造分词词典主要有两类研究方向：第一类着眼于对现有己经总结好的语 法语义知识的运用，主要依赖于大量人工的参与来描述词条信息；另一类着眼于对 各种各样大规模真实文本的分析，以获取有关的词汇信息来构建分词词典，依赖 的方法主要是概率统计及相对简单的语言模型。 在实际建造分词词典时，所采用的方法也就分别从属于这两类研究方向，一 般有三种方法。 第一种方法是在机器辅助下，主要依靠人工的输入来生成词典，其投入大量 的人力来描述词条信息，耗资巨大。典型的例子如：日本的分词词典开发计划e d r ) ， 还有美国普林斯顿大学认知科学实验室的m l i i e f 、b e c k w 洫等众多知名的心理语言 学家历时8 年所构造的，有名词、动词、形容词组成的带有同义、上下义、反义 等语义位系统性信息的w 6 r d n e t 。 第二种方法是从现有词典的印刷版本出发，将之转化为机器版本( m i ) ，然 后从中抽取各种词汇知识建立分词词典m t d ( m a c l l i n e1 r a c t a b l ed i 幽o n a r y ) ； 7 电子科技大学硕士学位论文 第三种方法，是通过对大规模真实文本的分析，即对语料库的分析，来获取 有关词汇信息来构造分词词典。 通过分析，上述前三种方法中，前两种应归属与第一个研究方向之下，因为 它们主要借助的还是语言学知识，同时依靠计算机的处理分析；而第三种方法则显 然归属与第二个研究方向。以上三种方法各有其优缺点，从目前国内研究现状看， 专家们对第一种方法着力较多提出了，很多对词汇、短语、句子、知识的分类标 准并在各自的分类标准上建立自己的语义信息库，鉴于国外的经验，用这种方法 建立词典周期长、耗资大，而且由于语言学家和计算语言学家在语言现象的具体 问题上还有许多分歧，因此在短时间内投入实际应用的可能性不大。第二种方法 目前看来是最适用的，本文是利用手工输入和借助比较新的词典来构建短信词典 的。 2 1 2 短信词典内容构建方式 1 手机短信特点 手机短信语言是信息时代发展的产物。人们将各种祝福语、甜言蜜语、调侃 挑逗语等等发往对方手机，转化成幽默的“空中语言”，通过它来释放自己的情绪， 放飞自己的心灵。它不仅使我们的生活平添了许多乐趣，也使我们感觉到了交流 的无穷魅力，甚至在一定程度上改变了我们的语言习惯。它以其经济简洁、随意 自由、隐秘快捷的特点，倍受手机一族的青睐。在手机短信语言中有一朵艳丽的 奇葩，将中文的灵活性演绎得淋漓尽致，充分展现了中文汉字的独特魅力。手机 短信大致有如下特点： 1 ) 主题突出：问候祝福、交待事情等目的明确。 2 ) 简明扼要：短信不超过7 0 字，一般是三五十字。另外，双方都明白的事情 注意用词简洁。 3 1 语言得体：短信的语言、内容必须注意场合、双方的身份、一般要注意礼 貌，语言文明。 4 1 构思别致：精彩的短信应有精巧的构思，才会让人过目不忘。如：让平安 坐上开往冬天的地铁，让快乐与你不见不散，让健康与吉祥一个都不能少， 让温馨和幸福没完没了，祝新年快乐1 5 ) 富有文采：好的短信应讲究文采，要特别注意修辞手法( 对偶、比喻、排 比等) 的运用。 第二章分谲谣典税剃分析 而垃圾短信也有四个明显的特点： l 批量发送； 2 ) 内容违法、违规或涉及广告宣传； 3 违背焉户主观意志； 4 ) 客观上造成对用户骚扰或其它权益的侵害。 因此，垃圾短信不仅发送量极大，丽且虑容危害力度也很大。在内容上垃圾 短信和正常短信有相似的地方，即比较灵活，口语化，使用的都是比较流行的词 语，有些词语是将人名地名的专有词语歧义化得到的，因此建立一个短信词库是 比较困难的。 2 短信词典构建 由于缀信里面都是比较新的词语，文献【1 4 】里面牧集的词条稳当一部分已经不 适合本项目的研究。针对垃圾短信的特点，本文通过使用搜狗上发布的一个比较 薪的词典( 钢) 来鳃决此问题，是因为搜狗上发布的词典都是网络上流行的词语， 与短信的词语很相似，很适合本项目的需要，另外采取手工输入的方法输入一些 比较有代表性的词语，比如不法广告和危害社会稳定的一些词语，来完善短语词 典。 2 2 几种常用的分词词典结构 本节主要介绍五种常用的和四种蒿效的分词词典结构，分析其优缺点，并对 部分算法提出具体的改进方案。 2 2 量传统的分词词典结构 般，设计一个分词词典结构的主要昌标是提高查询的效率以及更新词典的 灵活性和扩展能力，另外还有词典的存储空间的利用率。 ( 1 ) 基于拼音的索引机制 文献f l 】根据基于删c n 心静2 秘1 乃的中文自动分词词典机制设计了词典嘲 和索引文件格式。主词典采用记录文件格式，每条记录表示一个词条，每条记录 的格式如图2 1 。 词条 l 拼音 l 词性集合i 频度 l 类属关系指针i 层次关系指针i 语义描述指针l 图2 1 词条的记录格式 9 电子科技大学硕士学位论文 其中，词条字符串类型( 1 6 ) 拼音集合类型 词性集合一集合类型 频度整型 类属关系指针一长整型 层次关系指针一长整型 语义描述指针长整型 其中，汉词是存储的词条，为唯一的主关键字，并建立其索引文件；词性集合 包含了该词条的所有词性；频度指示该词条被使用的频率；类属关系指针、组成关系 指针及语义描述指针分别指向与该词条相应的语义属性。 索引文件采用删c 认仃e e ，关键词定义为主词典的词条记录的词条字段， 关键词作为二进制位串记录在树的结构中。索引文件中的节点结构如图2 2 。 图2 2 索引文件中的结点结构 其查找方式采用的并发查找，其依据是全切分在对字序列进行词典的检索过程中， 存在并发检索和持续检索的可能性。 该算法是采用拼音和树型索引结构来实现的，首先拼音由于汉字同音字的大量 存在致使目前的词典结构很少利用拼音在文件上组织词条，而树型结构是比较复 杂的，在内存里建立时间比较长，因此本文认为该词典结构机制高效不高，直接 影响到中文分词系统的效率 1 9 】，很难得到实际上的应用，在这里不再进行详细分 析并提出改进意见。 ( 2 ) 基于b + 树的词典结构 b + 是b 的变种，b 树是一种动态平衡树，由r b a y e r 和e m c c 商曲t 正式命名， 一棵m 阶的b 树定义如下【2 0 】： 1 ) 所有叶子结点都位于同一层上； 2 ) 除根结点外的所有内部结点至多有m 个非空子结点，至少包含m 2 个非空 子结点； 3 ) 内部结点中的关键字数目比非空子结点数少1 ； 4 ) 根结点最多有m 个子结点，如果它非叶子结点，至少有两个子结点；或者 整棵树只包含根结点 b + 树是b 一树的一种变种，叶子结点按关键字的升序( 或降序) 链接起来形成顺 1 0 第二章分谲词典祝翎分析 序集，比较适合作为数据库文件的索引。b + 树也有一些变种，如b k n k 树，同一级上 的内部结点通过指针连接起来，文献【2 l 】讨论了并发环境中b 敞树闻发性数据重组 算法，推导出间发性重组操作的最优时间间隔以提高响应速度；文献 2 2 中所论述 的n b 十树冼普遴b + 橱具有更高的空间剩用率帮有效性。文献【2 3 磷 出了物理聚 类o m y s i c a l 幽t e 曲妨的b + 树b c ，将逻辑上邻接的数据块聚集在同一存储单元中， 以减少寻道时间；文献【2 4 】则论述了在并行数据库环境中利用改进8 + 树1 b 树( 根 结点中增加了最大索引值域和最小索引值域两个特殊域) ，提出了基于r a l l g e 划 分策略的并行b + 树j o i n 算法和基于h a s h 划分策略的并行b + 树j o i 珏算法；所有 这些结构在沈方面具有相同的数量级，下面对此具体分析在文献【2 5 】中指出，b 树类的查找速度是以i o 次数来确定的，查找效率是查找树中任意一个记录所需 的；平均存取结点数，如将报到所求结点的路径所存取的结点数定义为路长，则查 找效率归结为求平均路长的问题对b + 树而言，实质上就是树的高度。 原有的词典管理系统使用了b + 树组织聚集索弓 方案f 以最常用的属性如词的 首字来作索引) ，下面简单分析一下利用b + 树聚集索引作为文件组织形式的电子 词典( 我们称之为t o ) 的数据查找与数据操作过程。 1 ) 数据查找 t o 的查找过程分为两步，第1 步为找顺序集中相应的结点，从根结点开始， 一直找到妒树的叶子结熹，显然需要的吾次数为毡又每一层都有一个绪点调入 主存，由于关键字有序，可以进行二分查找，这一步所需内部查找总次数为h 1 0 孑d 数量级；第2 步在数据链中找相应的记录，这一步至少需要1 次抛，所需的内部查 找次数为l o 矿数量级；若记玎d 为读取一次磁盘的平均时间，跆为平均内部查找 一次所需时间，某一诞条查找所需的平均时间姚，则有公式2 1 ： 纪塘( a + 1 ) 玎d ( 毳l 0 9 2 d + l 0 9 2 e ) 括 ( 2 - 1 ) 一般有燃括，故燃主要由嚣d 次数来决定。 2 ) 数据插入 首先根撼输入词条进行查找，在数据链中找到相应的位置，若数据块记录数小 于2 e ( 尚未充满) ，则将所有大予输入词条( 内褥比较) 的词条后移，然后将结果写 回磁盘；否则还要进行数据块的分裂或拉链乃至修改b + 树的叶子层，需要更多的 嚣操作。若记数据插入过程所需的平均时闻为勿i ，则有公式2 - 2 ： 加f 加+ t ，d ( 2 - 2 ) 3 ) 数据删除 奄子科技大学硬士学位论文 在删除某一特定的词条前，首先要在数据链中找到该词条，然后进行删除操 作，可能涉及修改转+ 树的叶子层。若记数据删除过程所需的平均时闻为勿蠢，鲻有 公式( 2 3 ) ： 彩露嬲锺7 d g - 3 ) 4 ) 数据更新 更薪某个词条属性的过程相对来说要簿单一些，找到特定词条后更新其属性 即可记数据更新过程所需的平均时间为幻甜 国群嫡 0 4 ) 该算法由于是使用b + 树来实现对词典的操作，由于在内存中建立一课树型结构比 较复杂浪费的时闻也比较长，所以在将词典调入内存时时闻是魄较长的，另努查 找效率也不高，所以该算法不是一个效率高的词典机制算法。 ( 3 ) 基于整词二分的分词词典机制分析与改进 该机制的词典结构分为词典正文、词索引表、首字h 勰h 表等三级。 词典正文是以词条为单位以有序表方式存储在磁盘上，词条索引表是指向词典 委文中每个词的指针表，用来定位每个词在该有序表中舱位置，利用首字g b 码计 算得到哈希值，通过首字h a s h 表的哈希定位和词条索引表很容易确定指定词在词 典正文中的可能位置范围，进两在词典正文中通过整词二分快速查找进行定位。 通过对该词典结构的介绍可以看到，此算法虽然通过首字的哈希值很容易定 位找到索引表，并且理论上不存在哈希冲突，从索引表中找到该词在有序表中相 同首字所在的位置范围，通过二分快速查找所要查找的词条，该算法存在一定的 效率问题：首先我们知道二分查找只适合数组并不适合有序表结构，也就是说二 分查找有序表效率并不高，所以可以将该算法进行一定的改进以提高效率，在索 引里面放置整个词条的哈希值，该哈希值可以通过本文设计的哈希函数求得，这 样可以通过两个哈希运算直接定位所要查找的词条，当然这样巍于是在整个词典 里面定位该词，所以发生冲突的可能比本论文提出的算法也多得多，必须设计出 无冲突的算法该改进才能生效。 ( 4 ) 基于t r i e 索引树的分词词典机制 t r m 树是搜索树的一种，来自英文单词”r e 砸c v a l ”的简写，可以建立有效的 数据检索组织结构，是中文殛配分词算法中词典的一种常见实现。它本质上是一 个确定的有限状态自动机( d f a ) ，每个节点代表自动机的一个状态。在词典中这 此状态包括“词翦缀”，“已成词”等。 1 2 第二章分词词典机制分析 t i 皿索引树是一种以树的多重链表形式表示的键树。t 砌e 索引树的优点是 在对被切分语句的一次扫描过程中，不需预知待查询词的长度，沿着树链逐字匹配 即可；缺点是要将所有的子树指针都要扫描一遍，相当于一棵树的宽度优先搜索， 查找效率不高，另外树的构造和维护比较复杂，而且都是单词树枝( 一条树枝仅代表 一个词) ，浪费了一定的空间，调入内存时的时间也比较长。 基于t r m 索引树的分词词典机制由首字h 砒表和咖索引树结点两部分 组成。比如要查找“啊哈”词条时，首先按照”啊”的g b 码得到一个哈希值，然后通 过子树指针找到“呀”字，直到子树指针为空并且能和查找的词条完全匹配表示查找 成功。 1 r i 皿树在字符串匹配方面是比较高效的，但是和本文设计的数组和哈希表结 合查找算法相还是有很大差距的，另外由于每个结点都要保存很多的信息，比如 各个汉字的哈希值，因此每个结点占的空间比较大，在内存中建立这样一棵树在 空间上和时间上都比较低效的。 ( 5 ) 基于逐字二分的分词词典机制 这种词典机制是前两种机制的一种改进方案。逐字二分与整词二分的词典结 构完全一样，只是查询过程有所区别：逐字二分吸收了n 皿索引树的查询优势，即 采用的是“逐字匹配”，而不是整词二分的“全词匹配”，这就一定程度地提高了匹配的 效率。但由于采用的仍是整词二分的词典结构，使效率的提高受到很大的局限。 从以上四种典型词典机制的介绍可以看出：整词二分和t l 溉索引树是分词词 典机制的两个极端。前者的数据结构简单、占用空间小，构建及维护也简单易行，但 由于采用全词匹配的查询过程，效率低下；后者的数据结构复杂、空间浪费较为严重， 树的构造和维护也较为繁琐，但它采用的查询过程是“逐字匹配”，所以查询效率较 高。第三种