基于Hash机制的分词词典的设计与实现

论文摘要

中文作为人类传播信息的重要语言工具之一,中文信息处理已经成为信息处理领域的热点研究问题。中文自动分词是中文信息处理的重要组成部分,而词典处理效率是影响中文自动分词系统性能的关键因素,因此,建立高效的分词词典具有显著的意义。本文对中文分词系统的词典结构进行了深入研究,取得了一定研究成果,已用于国家863项目中的垃圾短信监管处理,并将设计的算法申请提交了相关专利,主要研究成果如下:1.比较分析并改进了几种的词典存储和处理方法:数组—数组机制使用数组存储词条行,采用二分查找,在操作效率上不高,不利于词典的更新;双字哈希对前词条两个字哈希,使用深度为2的TRIE树,结构复杂;四字哈希机制只对四字成语有效,在应用上有局限性。本文对这些方法作一定的改进来解决效率问题。2.根据汉字GB码的特点,提出了一种比较高效的词典存储算法,将相同首字的词条作为一个文本行进行存储,而每个词条格式化为:去掉首字词条名、词条哈希值和相关属性,提高了存储空间利用率。3.利用Hash表在查找效率上优势,提出了基于Hash机制的词典查找、更新、删除、添加等操作新算法。设计一个实用的Hash函数,经实验验证冲突率极小,适合中小型词典,通过将该函数改进为适合大型词典的无冲突Hash函数。4.实现数组、链表、AVL树、Hash表(带极小冲突和无冲突两种)五种词典结构算法,对这些算法从时间复杂度和空间复杂度等方面进行详细的分析和评估,从载入、写出、文件大小和操作时间等几个方面进行实验对比,验证了基于Hash机制的词典结构算法在空间利用率比传统算法提高了近2倍,在时间效率上提高了5～6倍。5.用Java实现了基于Hash机制的词典结构模块,并提出了对该算法在词条属性上的扩充方案。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 国内外研究现状
• 1.2 本文的选题依据和研究意义
• 1.3 本文的主要内容
• 1.4 论文组织
• 1.5 本章小结
• 第二章 分词词典机制分析
• 2.1 词典内容构建
• 2.1.1 词典内容构建方式
• 2.1.2 短信词典内容构建方式
• 2.2 几种常用的分词词典结构
• 2.2.1 传统的分词词典结构
• 2.2.2 几种高效的分词词典结构
• 2.3 算法分析与对比
• 2.4 本章小结
• 第三章 基于Hash机制的词典结构
• 3.1 汉字GB码
• 3.2 词典在内存中的表示
• 3.3 词典在磁盘上的存储
• 3.4 算法设计与实现
• 3.4.1 哈希函数
• 3.4.2 算法设计与实现
• 3.5 词条频度属性的实现
• 3.6 词典算法的应用
• 3.7 算法存在问题及讨论
• 3.8 本章小结
• 第四章 词典结构算法的实现
• 4.1 算法实现工具
• 4.2 Hashtable与Hashmap
• 4.3 算法编程实现
• 4.3.1 使用带极小冲突哈希函数算法实现流程
• 4.3.2 具体算法实现
• 4.3.3 使用无冲突哈希函数算法实现
• 4.4 使用链表解决冲突算法实现
• 4.5 使用AVL树算法实现
• 4.6 本章小结
• 第五章 算法评估和实验
• 5.1 算法比较
• 5.2 实验
• 5.3 本章小结
• 第六章 总结与未来工作展望
• 致谢
• 参考文献
• 攻硕期间取得的研究成果