毕业设计（论文）-全文搜索引擎毕业论文.doc

《毕业设计（论文）-全文搜索引擎毕业论文.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）-全文搜索引擎毕业论文.doc（45页珍藏版）》请在三一文库上搜索。

1、 本科生毕业设计本科生毕业设计 目 录 I 目 录 设计总说明 .I INTRODUCTIONII 第 1 章绪论.1 1.1课题研究的目的和意义.1 1.2全文搜索引擎的发展现状和前景.1 1.2.1搜索引擎对用户提问的理解1 1.2.2对检索结果进行处理2 1.2.3提高搜索引擎的针对性2 1.2.4将搜索引擎的技术开发重点放在对检索结果的处理上2 第 2 章相关技术的介绍.4 2.1中文分词简介.4 2.1.1分词规范问题4 2.1.2基于词典的中文分词方法4 2.1.3分词中的词典机制7 第 3 章全文搜索引擎需求分析.10 3.1系统功能.10 3.1.1功能划分10 3.2功能描述

2、.10 3.2.1前台显示10 3.2.2后台管理10 3.2.3搜索引擎10 3.2.4LUCENE 索引.10 3.2.5网页分析10 3.2.6分词11 3.3分词模块需求.11 3.3.1功能需求11 3.3.2中文自动分词模块设计方案选择12 第 4 章全文搜索引擎系统设计.13 4.1系统功能结构图.13 4.2系统流程图.13 4.3分词组件图.14 4.4分词流程图.15 4.5分词时序图.15 4.6分词数据库设计.16 4.6.1数据字典16 4.7分词词典设计.18 4.7.1Dictionary 散列表的实现.18 4.7.2分词词典的查询19 4.7.3分词词典的创建

3、19 目 录 II 4.7.4添加未登录词19 4.7.5删除错误词汇21 4.8分词器设计.21 4.8.1预处理模块设计21 4.8.2自动分词模块设计22 4.8.3切分未登录词模块设计22 第 5 章系统实现和系统测试.24 5.1系统实现.24 5.2系统测试.26 总 结.28 鸣 谢.29 参考文献.30 附 录.31 设计总说明 I 设计总说明 搜索引擎（Search Engine）已经成为互联网不可缺少的工具，可以帮助人们更快的找到所要 的内容和信息。提高做事的效率，使互联网资源高效的利用。. 互联网搜索的使用水平可以反映全民的信息处理能力，几年前有研究发现美国用户比欧洲用户

4、 的互联网使用水平领先半年左右，主要是根据谁搜索时平均使用的关键词的个数多。中文用户的搜 索使用水平相对于西文用户目前仍然处于比较初级的阶段，而中文网站搜索功能的缺失也是一个重 要的因素。 网站拥有了较多内容后，首先考虑基于目录的内容分类，以解决信息快速定位的问题，随着内 容量的进一步增加，很多内容在发表之后就很快被湮没，成为“信息孤岛”，而不断加深的目录结 构也会让用户逐渐失去耐心，这时，关键词检索的优势就体现出来了：关键词检索可以让处于“信 息孤岛”状态的内容以一种更直接的方法提供给用户；和基于目录/分类的树形结构不同，基于关 键词检索还可以让内容之间实现网状的关联结构，从而大大提高信息的

5、引用密度。 基于传统数据库的关键词检索由于性能问题让很多网站放弃了搜索功能，问题的解决归根结底 还是需要一个全文引擎。而 Lucene 开源信息资源库的出现让这种原来被少数公司掌握的技术得到 了迅速的普及。 本文在对传统自动分词系统及目前已有的主要自动分词算法研究的基础上，对传统分词算法都 做了改进。主要工作如下：对传统的正向最大匹配算法进行了改进，将传统的固定最大匹配词长改 为分词过程中动态确定，充分体现了“长词优先”原则；对分词中的未登录词识别问题，对字符串 分别进行二元分词和数字处理，能在一定程度上提高算法的查全率，精确率和问登录词识别率。 综上所述，本文设计的自动分词方法，具有较好的分

6、词效果，可以初步应用于全文检索及各种 中文文本处理。 关键词：正向最大匹配算法；中文分词；全文搜索；搜索引擎； INTRODUCTION II INTRODUCTION The Internet search engine has become an indispensable tool that can help people to find faster content and information, to improve the efficiency of work, make use of Internet resources efficiently. The use of Inte

7、rnet search can reflect the level of the power of national information processing. A few years ago, studies have found that American users of Internet had at least a half of years head start in processing information of the users of Europe, which is based on the investigation of the average number o

8、f words. Chinese users search level compared with western user is still in the primary stage, which is mainly leaded by the lack of function of Chinese websites. The website has more content, first will consider the content classification based on the list, in order to solve the problem rapidly posi

9、tioning information. With further increase of the size of the content, many content published in is neglected soon and become the “island of information”. And the deeding directory structure will also allow users to gradually lose patience. Then, the advantage of keywords search is reflected: allows

10、 the contents of “the island of information” in a more direct method to users; not as the directory/tree structure, it still can make the correlation between realize net structure, thus greatly improving the reference information. As the performance problems of the keywords searching based on the tr

11、aditional database, many websites abandoned search function. There must be a new full-text searching engine to resolve the problem ultimately. Then the engine Lucene opened have spread the technology up which was mastered by a few companies. Based on the traditional automatic word division of the ex

12、isting system and the main automatic word segmentation algorithm based on the research of traditional parting-words arithmetic are improved. Main job is as follows: the traditional maximum positive matching algorithm was improved, the traditional fixed maximal matching words long instead of dynamic

13、segmentation process, fully embodies the “long term priority“ principle, For the unknown words segmentation, identification of binary string separately and digital processing, can improve the algorithm to a certain extent, the accurate rate recall-precision login word recognition and ask. To sum up,

14、 this design of automatic word segmentation method has good segmentation results can be applied to full-text retrieval and various initial Chinese text processing. KEYWORDS: Forward maximum matching algorithm; Chinese word; full-text search; search engine; 广东海洋大学 2010 届毕业设计 1 全文搜索引擎全文搜索引擎 -分词分词 软件工程

15、，200611701205，陈磊 指导教师：梁春林 第 1 章 绪论 1.1 课题研究的目的和意义 搜索引擎已经成为互联网不可缺少的工具，它可以帮助人们更快的找到所要的内容和信息。提 高做事的效率，使互联网资源高效的利用。 互联网搜索的使用水平可以反映全民的信息处理能力，几年前有研究发现美国用户比欧洲用户 的互联网使用水平领先半年左右，主要是根据谁搜索时平均使用的关键词的个数多。中文用户的搜 索使用水平相对于西文用户目前仍然处于比较初级的阶段，而中文网站搜索功能的缺失也是一个重 要的因素。 网站拥有了较多内容后，最先会考虑基于目录的内容分类，以解决信息快速定位的问题，随着 内容量的进一步增加，

16、很多内容在发表之后就很快被湮没，成为“信息孤岛”，而不断加深的目录 结构也会让用户逐渐失去耐心，这时，关键词检索的优势就体现出来了：关键词检索可以让处于 “信息孤岛”状态的内容以一种更直接的方法提供给用户；和基于目录/分类的树形结构不同，基 于关键词检索还可以让内容之间实现网状的关联结构，从而大大提高信息的引用密度。 基于传统数据库的关键词检索由于性能问题让很多网站放弃了搜索功能，问题的解决归根结底 还是需要一个全文引擎。而 Lucene 开放源代码的全文检索引擎工具包的出现让这种原来被少数公 司掌握的技术得到了迅速的普及。 1.2 全文搜索引擎的发展现状和前景 搜索引擎经过几年的发展和摸索，

17、越来越贴近人们的需求，搜索引擎的技术也得到了很大的发 展。搜索引擎的最新技术发展包括以下几个方面： 1.2.1 搜索引擎对用户提问的理解 为了提高搜索引擎对用户检索提问的理解，就必须有一个好的检索提问语言，为了克服关键词 检索和目录查询的缺点，现在已经出现了自然语言智能答询。用户可以输入简单的疑问句，比如 “how can kill virus of computer?” 。搜索引擎在对提问进行结构和内容的分析之后，或直接给 出提问的答案，或引导用户从几个可选择的问题中进行再选择。自然语言的优势在于，一是使网络 交流更加人性化，二是使查询变得更加方便、直接、有效。就以上面的例子来讲，如果用关键

18、词查 询，多半人会用“virus”这个词来检索，结果中必然会包括各类病毒的介绍、病毒是怎样产生的 等等许多无效信息，而用“how can kill virus of computer?” ，搜索引擎会将怎样杀病毒的信息 广东海洋大学 2010 届毕业设计 2 提供给用户，提高了检索效率。 1.2.2 对检索结果进行处理 基于链接评价的搜索引擎 基于链接评价的搜索引擎的优秀代表是 Google，它独创的“链接评价体系”是基于这样一种 认识，一个网页的重要性取决于它被其它网页链接的数量，特别是一些已经被认定是“重要”的网 页的链接数量。这种评价体制与科技引文索引的思路非常相似，但是由于互联网是在一

19、个商业 化的环境中发展起来的，一个网站的被链接数量还与它的商业推广有着密切的联系，因此这种评价 体制在某种程度上缺乏客观性。 基于访问大众性的搜索引擎 基于访问大众性的搜索引擎的代表是 direct hit，它的基本理念是多数人选择访问的网站就 是最重要的网站。根据以前成千上万的网络用户在检索结果中实际所挑选并访问的网站和他们在这 些网站上花费的时间来统计确定有关网站的重要性排名，并以此来确定哪些网站最符合用户的检索 要求。因此具有典型的趋众性特点。这种评价体制与基于链接评价的搜索引擎有着同样的缺点。 去掉检索结果中附加的多余信息 有调查指出，过多的附加信息加重了用户的信息负担，为了去掉这些过

20、多的附加信息，可以采 用用户定制、内容过滤等检索技术。 1.2.3 提高搜索引擎的针对性 垂直主题搜索引擎 网上的信息浩如烟海，网络资源以十倍速的增长，一个搜索引擎很难收集全所有主题的网络信 息，即使信息主题收集得比较全面，由于主题范围太宽，很难将各主题都做到精确而又专业，使得 检索结果垃圾太多。这样一来，垂直主题的搜索引擎以其高度的目标化和专业化在各类搜索引擎中 占据了一系席之地，比如象股票、天气、新闻等类的搜索引擎，具有很高的针对性，用户对查询结 果的满意度较高。作者认为，垂直主题有着极大的发展空间。其他的还有提供 FTP 等类信息的非 www 信息检索和提供包括声音、图像等多媒体信息的多

21、媒体搜索引擎。 1.2.4 将搜索引擎的技术开发重点放在对检索结果的处理上 纯净搜索引擎 这类搜索引擎没有自己的信息采集系统，利用别人现有的索引数据库，主要关注检索的理念、 技术和机制等。 元搜索引擎 现在出现了许多的搜索引擎，其收集信息的范围、搜索机制、算法等都不同，用户不得不去学 习多个搜索引擎的用法。每个搜索引擎平均只能涉及到整个 www 资源的 30-50%，这样导致同一个 搜索请求在不同搜索引擎中获得的查询结果的重复率不足 34%，而每一个搜索引擎的查准率不到 45%。 广东海洋大学 2010 届毕业设计 3 元搜索引擎是将用户提交的检索请求到多个独立的搜索引擎上去搜索，并将检索结果

22、集中统一 处理，以统一的格式提供给用户，因此有搜索引擎之上的搜索引擎之称。它的主要精力放在提高搜 索速度、智能化处理搜索结果、个性搜索功能的设置和用户检索界面的友好性上，查全率和查准率 都比较高。目前比较成功的元搜索引擎有 metacrawler、dopile、ixquick 等。 广东海洋大学 2010 届毕业设计 4 第 2 章 相关技术的介绍 2.1 中文分词简介 根据定义,中文分词就是将一段中文的字序列切分成词序列的过程。例如：“我是一个学生” 的切分结果为“我是一个学生” ，然而虽然现在中文分词领域己经有了相当多的技术积累,但是 中文分词问题仍然未能得到完美的解决，就像上面的例子中“

23、我是一个学生”的英文表达为“I am a student” 。计算机可以简单地通过空格知道“student”是一个单词,但是计算机却不能很容易地 明白此处“学”和“生”两个字合起来才构成一个词。 中文分词不仅在分词算法的实现上存在难点,而且中文分词本身存在着规范标准问题。 2.1.1 分词规范问题 中文分词的规范难以确定，不确定性主要有两个点:第一点，汉语词的概念尚待研究“什么是 词”(词的具体界定)，这个问题一直模糊不清，迄今拿不出一个公认的、具有权威性的词表来。一 方面是单字词与语素之间的划界难以确定;另一方面是词与短语(词组)的划界也模糊不清。此外， 对“词”的认识，不同应用领域的标准有

24、较大差异。对汉语词认识上的差异，必然会给自动分词造 成困难。汉语的词汇平面构成了现阶段中文信息处理应用领域的主要支撑平台，摆在人们面前的， 不是单纯的学术问题，也是一项颇具规模的语言工程。目前没有得出合理的可操作的理论;第二点， 服务目的的不同造成对分词单位认识上的差异，多年来，人们发现分词系统的通用性、适应性普遍 不足。一般研制自动分词软件一定要满足某种需要，由于服务的目的不同，可能会有不同类型的分 词系统。其分词结果很难采用统一的通用的分词标准来评价。许多中文处理系统，根据服务目的编 制适合自己需要的分词系统。分词单位界定的大小不同，必然造成统一评价分词系统的困难。 2.1.2 基于词典的

25、中文分词方法 基于词典的分词方法一般又称为机械匹配法, 这种方法要事先准备一个“充分大的”词典，词 典里包含所有可能出现的词，将给定的待分词的字符串按某种确定的原则分割成子串，然后将待切 分的子串按照一定的扫描规则与词典中的词条进行匹配，如果匹配成功,则将这个词切分出来,否则 进行其他相关处理。继续分割剩余的部分,直到剩余部分为空或者不匹配,如此则该子串不是词。 根据切取子串的方向,机械匹配法又分为正向匹配法和逆向匹配法。 2.1.2.1正向最大匹配分词法 正向最大匹配法（Maximum Matching Method） ，简称 MM.。MM 又可以分为增字法和减字法。增 字匹配法需要一种特殊

26、结构的词典，这种方法能够达到非常高的分词效率。在这里将较为简略的介 绍 MM 的增字法。用 Maxlength 表示最大词长，按照从左到右的顺序，首先从汉字中取长度为 Maxlength 的子串在分词词典中查找匹配词条。若词中存在这个词，则切分出这一子串，下标后移 Maxlength 个汉字继续切分，否则，子串长度减一，再与词典继续匹配。若长度为二的子串还不能 在词典中查到，则此次切分结束。根据每次匹配失败后是增加还是减少子串长度，再分为正向增字 广东海洋大学 2010 届毕业设计 5 最大匹配法和正向减字最大匹配法。正向最大匹配算法流程图如图 2-1 所示。 开始 取M个字 切分长度=0 往

27、词典链表中index 位置插入未登录词 获得查找index时向 上一级的Dictionary 对象Sub 判断sub的类型 判断是否需要创建 Dictionary对象 调整sub的范围 调整sub对象之后 的Dictionary对象的 范围 创建Dictionary对象 Cur 是 HashBinaryDictionary是 BinaryDictionary 否 调整Cur对象之后 的Dictionary对象的 范围 结束 否 图4-9 往词典添加未登录词流程图 4.7.5 删除错误词汇 删除错误词汇的流程与添加未登录词的流程相似，不同之处在于一个是做添加操作，一个是做 删除操作，其余地方并没

28、有不同的地方。 4.8 分词器设计 分词器主要由以下四部分组成： 预处理： 对文本进行初分，将字符串分批次读入待切分字符数组， ，并对待切分字符串开头字 符进行判别，使用恰当的分词方法切分待切分字符串。 自动分词：利用一定的分词算法，对预处理后的字符串进行自动分词。本文利用一种改进的最 大正向匹配法进行自动分词。分词算法的基本思想已在前文中介绍过，在下面将给出算法的流程图。 未登录词切分：完成对未登录词的切分，主要是对未登录词进行二元切分和数字判断。 4.8.1 预处理模块设计 预处理流程如下： （1） 判断上一次分割点的结束位置：如果结束位置为 0 或者不大于读取的字符串长度，那么 将上一次

29、的分割点结束位置作为这次分割的起始点。如果上一次分割点为负数表示需要 读取更多的字符来被分割，如过分割点大与字符串长度，则表示分割结束。 广东海洋大学 2010 届毕业设计 22 （2） 判断待切分字符串起始点的字符，决定使用什么分词算法来切分字符串 （3） 将字符串进行分词，切分结束后得到切分的最后位置。 （4） 重复 1-3 步骤。 4.8.2 自动分词模块设计 自动分词是采用基于中文词典的正向最大匹配中文自动分词算法并辅之以二元分词对未登录词 的进行召回。在自动分词的过程中除了会使用到正向最大匹配算法外，还会涉及到二元分词和数字 处理。自动分词流程图如下： 开始 获取待切分字符串 截取长

30、度为Min的 字串 将上一个字符串切 分出来 是否有匹配 Min+ 上一个字符串 是否有匹配 判断切分出来的词之前是否 有未被切分的字符串 将字符串二元分词 和数字处理 否 记录匹配的字符串 及其开始，结束位 置 是 是 否 是 Min ascWords, int initialCapacity, float loadFactor, States state, Map map) this(ascWords, 0, 0, ascWords.size(), initialCapacity, loadFactor, state, map); public HashBinaryDictionary(L

31、ist ascWords, int hashIndex, int start, int end, int initialCapacity, float loadFactor, States state, Map map) this.ascWords = ascWords; this.start = start; this.end = end; this.count = end - start; this.hashIndex = hashIndex; subs = new HashMap/* */(initialCapacity, loadFactor); createSubDictionari

32、es(state, map); /* * 创建分词典映射，为构造函数调用 * * 即将字典内的所有词的开头字相同的词单独构成一个字典 并将这些字典存储到 subs 这个 hashmap 当中 */ protected void createSubDictionaries(States state, Map map) if (this.start = ascWords.size() return; / 定位相同头字符词语的开头和结束位置以确认分字典 int beginIndex = this.start; int endIndex = this.start + 1; char beginHash

33、Char = getChar(ascWords.get(start), hashIndex); char endHashChar; for (; endIndex = s.length() return (char) 0; return s.charAt(index); /* * 将位置在 beginIndex 和 endIndex 之间(不包括 endIndex)的词语作为一个分词典 * * param hashChar * param beginIndex * param endIndex * param state * 0 表示自动创建，1 表示是插入词条是调用，需自己插入 list *

34、/ public void addSubDictionary(char hashChar, int beginIndex, int endIndex, Map map, States state) / subdic 是一个个包含了多个根据关键词首字母划分的字典类 int thisstate = state.getState(); state.setState(thisstate + 1); Dictionary subDic = createSubDictionary(ascWords, beginIndex, endIndex, state, map); SubDictionaryWrap

35、subDicWrap = new SubDictionaryWrap(hashChar, subDic, beginIndex); map.put(thisstate, subDicWrap); subs.put(keyOf(hashChar), subDicWrap); /* * 返回的是一个包含了多个根据关键词首字母划分的字典 这是一个多级的字典，比如说一二三四，则以一为 开头的词建立一个字典，在这个字典内， * 又建立以二为开头的字典。 * * param ascWords * param beginIndex * param endIndex * return */ protected

36、 Dictionary createSubDictionary(List ascWords, int beginIndex, int endIndex, States state, Map map) 附 录 34 int count = endIndex - beginIndex; if (count 0 / 记录当前正在检视(是否是词典词语)的字符串在 beef 中的始止位置(包含开始位置，不包含结束位置) int curSearchOffset = offset, curSearchEnd; / 记录当前被检视的字符串的长度，它的值恒等于(curSearchEnd - curSearchO

37、ffset) int curSearchLength; / 当前检视的字符串的判断结果 Hit curSearch = null; / 限制要判断的字符串的最大开始位置 / 这个变量不随着程序的运行而变化 final int offsetLimit; if (point != -1) offsetLimit = point; else offsetLimit = limit; / 记录到当前为止所分出的词典词语的最大结束位置 int maxDicWordEnd = offset; 附 录 36 / 记录最近的不在词典中的字符串(称为孤立字符串)在 beef 的位置，-1 表示没有这个位置 in

38、t isolatedOffset = -1; / 详见本方法后面对 maxDicWordLength 的应用以及 shouldBeWord()的实现 int maxDicWordLength = 0; / 第 1 个循环定位被检视字符串的开始位置 / 被检视的字符串开始位置的极限是 offsetLimit，而非 limit for (; curSearchOffset = 0) dissectIsolated(collector, dog, isolatedOffset, curSearchOffset); isolatedOffset = -1; if (maxDicWordEnd = li

39、mit | dog.charAt(curSearchEnd) = maxDicWordEnd) isolatedOffset = curSearchOffset; break; / end of the second for loop if(word!=null) if (!word.isNoise() collector.collect(word.getText(), wordoffset, wordend); word=null; curSearchOffset=wordend; if (maxDicWordEnd 2 return point = -1 ? limit : point;

40、附 录 38 3.进行未登录此切分 protected void dissectIsolated(Collector collector, Dog dog, int offset, int limit) int curSearchOffset = offset; int binOffset = curSearchOffset; / 进行一般二元分词的开始位置 int tempEnd; while (curSearchOffset curSearchOffset) curSearchOffset = tempEnd; binOffset = tempEnd; continue; tempEnd

41、= skipNoiseWords(collector, dog, curSearchOffset, limit, binOffset); if (tempEnd curSearchOffset) curSearchOffset = tempEnd; binOffset = tempEnd; continue; Hit curSearch = noiseCharactors.search(dog, curSearchOffset, 1); if (curSearch.isHit() binDissect(collector, dog, binOffset, curSearchOffset); b

42、inOffset = +curSearchOffset; continue; curSearchOffset+; if (limit binOffset) binDissect(collector, dog, binOffset, limit); protected int collectNumber(Collector collector, Dog dog, int offset, int limit, int binOffset) int curTail = offset; int number1 = -1; int number2 = -1; int bitValue = 0; int

43、maxUnit = 0; boolean hasDigit = false;/ 作用：去除没有数字只有单位的汉字，如“万”，“千” for (; curTail = 0; curTail+) if (bitValue = 0 number1 *= bitValue; maxUnit = bitValue; else number1 += number2 * bitValue; number2 = -1; if (!hasDigit) return offset; if (number2 0) if (number1 = 0) / 二元分词先 if (offset binOffset) 附 录

44、40 binDissect(collector, dog, binOffset, offset); collector.collect(String.valueOf(number1), offset, curTail); if (units != null) / 后面可能跟了计量单位 Hit wd = null; Hit wd2 = null; int i = curTail + 1; while (wd = units.search(dog, curTail, i - curTail).isHit() wd2 = wd; i +; if (!wd.isUnclosed() break; i -; if (wd2 != null) collector.collect(String.valueOf(number1)+wd2.getWord().getText(), curTail, i); return i; return curTail;