论文部分内容阅读
互联网飞速发展,中文信息处理在获取有价值信息方面起到不可替代的作用,而中文分词在中文信息处理的过程中重中之重,又在信息检索、智能输入、自动摘要、中外文翻译文等各个领域都有重要应用。中文分词是将汉语中连续的字序列切分成具有实际意义的最小单位的词语。汉语的历史悠久与博大精深决定了它的复杂性,提高分词算法的划分精度和划分速度,具有重要的理论意义和现实意义。 本文首先阐述了中文分词的研究背景、研究意义以及发展现状,以及目前存在的困难,并研究现有分词算法,包括基于词典的机械分词算法、基于统计的分词算法和基于理解的算法。三种基本的分词算法各有利弊,第一种分词算法简单高效,在目前的各种分词系统中都广发应用,第二种分词算法是运用统计学理论训练大规模语料库,算法复杂而且效率较低,第三种分词算法是想通过模拟人的思维达到高精度的智能分词,虽然目前尚不成熟,有很大的发展空间。 本文选择研究全切分算法,全切分算法的切分结果是能够最大限度的保留正确分词结果,全切分形成的分词结果是一个切分词树,切分词树形成有向无环图,对进行全切分后形成的有向无环图求取最短路径进行深入研究,利用N-最短路径算法进行求取最短路径,是贪心算法的应用,由于其进行重复遍历,导致时间复杂度较高,本文在此基础上提出基于频数统计与动态规划相结合的分词算法,即采用动态规划的思想倒叙遍历全切分后形成的有向无环图,通过记忆化搜索的方式,旨在降低时间复杂度,提高分词速度,并通过实验证明了此算法具有一定的可行性,同时,对Trie树的词典结构进行研究。 本文对基于频数与动态规划相结合的算法进行复杂度分析和速度测试,在理论和实践上证明该算法在一定程度上提高了分词的速度。 中文分词算法应用广泛,本文选取搜索引擎Nutch作为一个应用场景,对Nutch进行学习研究,Nutch中预留的中文分词算法是逐字切分,是没有实际意义的中文分词,本文则是将算法应用到Nutch分词器中,使得Nutch具有中文分词的功能,研究比较分词结果。