基于双字哈希的PAT树词典机制的研究

论文摘要

中文自动分词是中文信息领域中的一项重要的基础性工作,同时中文信息处理技术也是重要的计算机技术,它已广泛地渗透到如数据库技术、计算机网络、软件工程等计算机应用领域中。由于中文文本词间无间隙且按句连写,因此在中文文本处理中,词的正确切分问题是首要问题。高效准确的分词系统在是信息处理的必要条件。本文论述了基于双字哈希的PAT树词典机制及基于该机制的分词词典的建立问题。本文对三种典型的分词词典机制、基于双字哈希的词典机制、基于PAT树的词典机制及四字哈希词典机制进行了探讨与研究,并针对这些机制存在的问题提出了改进措施。双字哈希的词典机制针对中文文本中双字词占较大比例的特点,利用哈希查找的高效性,对词条的前两字采用哈希散列的方法。通过实验证明,这种词典机制在双字词的处理上效率较高,但在多字词的处理上有待提高。基于PAT树的词典机制在时间效率上有优越性,但却需要更多的存储空间。针对这样的情况,本文提出了基于双字哈希的PAT树词典机制,并对基于该机制词典的查询及更新进行了详细的论述。基于双字哈希的PAT树词典机制不仅吸取了双字哈希处理双字词的高效性,同时也将多字词切分的时间效率提高。由于对前两字采用哈希散列,PAT树的深度也得到了控制。本文对基于双字哈希的PAT树词典的生成过程也进行了描述,并且在3GWS分词系统中加载了该机制的词典,对其时间及空间效率进行了测试。实验证明,基于双字哈希的PAT树词典机制,在时间效率上较逐字二分词典机制及双字哈希机制均有明显提高,在空间效率上较PAT树机制有了很大改善,并且在词典的更新方面效率也较高。本文分析了常用的机械分词方法和统计分词方法基础上,设计并实现了一个基于机械与统计相结合的分词系统。为使得机械分词方法和统计分词方法能有机结合,优势互补,最大发挥各自性能,本文在如下几方面作了深入研究：在机械分词阶段,将最大匹配长度的赋值方式由静态分配改进为动态分配,以减少不必要的匹配操作；将词频信息作为切分评估的另一标准,以弥补“长词优先”标准的不足。在统计分词阶段,为了提高统计操作的效率,对分词单位的概念进行了泛化,并把词频统计操作融合于机械分词操作,同时还采用了Hash表来存储词频统计的结果,从而提高机械分词速度。最后,本文分析了本词典机制的不足和需要进一步做的工作。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 中文自动分词常用的方法
• 1.1.1 基于字符串匹配的方法
• 1.1.2 基于统计的方法
• 1.1.3 基于理解的方法
• 1.1.4 基于语义的方法
• 1.2 中文自动分词研究的现状及问题
• 1.3 论文主要研究内容
• 1.4 论文组织
• 第2章 常用的分词词典机制
• 2.1 分词词典的查询方式
• 2.2 三种典型的分词词典机制
• 2.2.1 基于整词二分的分词词典机制
• 2.2.2 基于TRIE索引树的分词词典机制
• 2.2.3 基于逐字二分的分词词典机制
• 2.3 基于PAT树的词典机制
• 2.3.1 基于PAT树的词典机制
• 2.3.2 基于改进的PAT树词典机制
• 2.4 基于双字哈希索引的词典机制
• 2.5 四字哈希结构的词典机制
• 2.6 本章小节
• 第3章 改进的双字哈希词典机制
• 3.1 哈希函数及汉字编码问题
• 3.2 基于双字哈希的PAT树词典结构
• 3.3 词典结构中的参数及结构
• 3.3.1 首字哈希表
• 3.3.2 词次字哈希表
• 3.3.3 词余字PAT树
• 3.4 次字哈希表中冲突的解决
• 3.5 词条的查询
• 3.5.1 确定词条的查询
• 3.5.2 前辍词条的查询
• 3.5.3 最长词条的查询
• 3.6 词典的更新
• 3.6.1 词条的添加
• 3.6.2 词条的删除
• 3.7 初始词典的建立
• 3.7.1 初始词典的生成
• 3.7.2 成词原则
• 3.8 本章小节
• 第4章 实验及分词词典的性能测试
• 4.1 词典测试
• 4.1.1 词典的查询的算法及规则
• 4.1.2 分词的流程设计
• 4.1.3 词典的测试步骤
• 4.2 实验设计与结果分析
• 4.2.1 实验设计
• 4.2.2 实验结果分析
• 4.3 与其他词典机制的比较
• 4.4 本章小节
• 第五章 机械与统计相结合的分词系统的设计与实现
• 5.1 系统设计的基本思想
• 5.1.1 机械分词方法的设计思想
• 5.1.2 统计分词方法的设计思想
• 5.1.3 机械与统计相结合的设计思想
• 5.2 机械与统计相结合的分词系统的设计与实现
• 5.2.1 各模块数据流图
• 5.2.2 各模块设计及实现
• 5.3 功能界面的设计
• 5.3.1 系统实现的功能
• 5.3.2 分词系统界面设计
• 5.4 本章小节
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文及取得的科研成果
• 致谢
• 个人简历