移动环境下的搜索引擎软件系统设计与实现终稿.doc

. . 移动环境下的搜索引擎软件系统设计与实现摘要在互联网时代,搜索引擎技术是一项重要的技术,作为核心的支撑技术之一,在搜索引擎技术的帮助和推动下,人们对互联网上丰富的信息进行有效而快速的检索,从而在信息库中及时获取自身所需的信息。而目前,随着以手机、平板电脑为代表的移动互联网终端的普及和使用,越来越多的搜索需求开始转变为在移动环境下,对网络信息的搜索和汇集,已经成为今后网络搜索技术发展的新热点。从目前的情况来看,移动互联网方面,特别是移动互联网终端方面的搜索技术发展还有待提高,用户体验和用户需求方面还需要进一步的挖掘,对资源搜索收到限制较多的移动互联网环境,如何在有限的条件包括移动互联网终端较小的显示屏幕,比较差的CPU处理速度以及时效性不高的移动互联网数据下,对移动互联网搜索进行深耕细作,开发出在移动互联网终端上进行快速检索的新型搜索引擎,同时结合用户的体验和移动互联网技术的发展进行不断的更新和优化,成为笔者在对相关领域进行研究时的主要动力之一。一般来说,关键字聚类搜索是目前国内互联网搜索引擎中常用的研究技术,通过关键字的检索,可以帮助移动互联网终端用户能够用更短的时间,搜索到最精准的信息,从而为自身的搜索应用提供良好的用户体验。本文针对目前移动互联网时代的大背景,设计了在移动互联网时代能够运用现代搜索技术,对手机移动端的搜索技术进行改良。建立在对关键字进行聚类分析的搜索引擎,是移动互联网目前发展的主流方向,也是本文也重点研究的领域,对于基于聚类搜索技术的应用,能够给以手机、平板电脑为代表的移动设备提供更好的互联网体验。而从搜索引擎服务提供商的角度来说,易用性强的搜索引擎技术能够给服务运营商带来更好的营销基础。本文在全文中,贯穿设计了一个能够在移动互联网领域运行的搜索引擎软件,即"妙搜"移动搜索引擎系统。通过改搜索引擎,我们能够在采集数据中,对搜索的结果及其列表进行聚类法搜索,很大程度上对搜索的结果进行分类和快速检索,方便客户快速得到所需信息和相关内容。此外,本文还对搜索内容的原文抓取,中文内容分析,以及对手机移动端的用户体验进行了详细的分析和设计,同时针对手机移动端的特殊情况,对搜索引擎软件进行了优化,解决了长期以来,移动客户端搜索引擎存在的不足和弊端,最大限度的满足目前移动互联网时代对移动端搜索引擎服务的各种需求。关键词： 搜索引擎；数据挖掘；聚类；lucene； Nutch； hadoop； carrot2； LINGO；结构第一章绪论1.1移动搜索的现状1.2目前存在的问题1.3本文的主要内容1.4本文的章节安排第二章搜索引擎关键技术介绍2.1搜索引擎的定义2.2搜索引擎的发展现状2.3搜索引擎系统运行的几个步骤2.4本章小结第三章LINGO聚类算法分析3.1聚类的概念3.2LINGO算法概要3.3LINGO算法基础之后缀数组3.4 LINGO算法基础之隐含语义分析3.5 LINGO算法过程分析3.6 LINGO聚类算法的优缺点3.7本章小结第四章妙搜移动搜索引擎系统的需求分析4.1系统研究背景4.2系统需求4.3系统功能目标4.4系统性能要求4.5本章小结第五章妙搜移动搜索引擎系统的分析与设计5.1系统总体目标5.2软件技术平台的选择5.3妙搜服务系统架构设计5.4内容爬取子系统设计5.5索引子系统设计5.6搜索处理子系统设计5.7中文分词算法设计5.8聚类设计5.9缓存子系统设计5.10通信接口层设计5.11本章小结第六章妙搜移动搜索引擎系统的实现6.1开发及部署环境6.2 Nutch运行环境安装与配置6.3 Nutch中中文分词的实现6.4 Nutch聚类实现6.5搜索处理子系统实现6.6移动客户端实现6.7本章小结第七章结论第一章绪论目前人类社会已经发展到互联网时代,互联网时代的典型特征即是电脑在人们的生活中所占的地位越来越重要。无论是PC端还是移动端,互联网对于人们学习和工作的重要作用有目共睹,通过互联网,极大的丰富了人们的生活内容和视野,也有利于人们通过互联网获得更高的生产力,从而极大的提高人类社会的物质生产水平,进而不断提高人民生活水平；同时,互联网的应用和推广,也给人类的精神世界带来了充足的养分,使得人们能够更加广泛的接触到世界各地的人文风土人情,了解不同文化的差异和世界各民族、国家的智力成果,通过资源共享,实现智力成果的交流和互通。在这样的大背景下,网络技术已经成为能够影响人类生活和生产活动的重要生产力,网络技术已经开始极大的影响和改变着人类文明的发展。随着商业互联网时代的进一步扩展,网络技术中的重要一环搜索引擎技术的作用和地位愈加凸显,成为在互联网相关领域技术中,最重要的内容之一。从世界各国的商业案例来看,互联网公司往往能够赢得比较好的商业预期和现实成果,而互联网公司中,专注于搜索引擎技术,或者以搜索引擎技术为主业的互联网公司,不仅股价上涨较快,而且公司的发展健康且持久,能够带来较高的经济效益,体现出较高的市场价值。但凡是拥有成熟的搜索引擎技术的互联网公司,其商业排名往往居于互联网企业的顶端,其商业价值和在互联网企业中的重要地位,不容小觑。目前,智能手机的普及率越来越高,对智能手机、平板电脑为代表的互联网移动端成为继PC端之后又一重要的互联网技术应用领域,手机为代表的互联网移动端,具有便携、易操作、普及率高,受场地、环境、基础设施建设影响较小的优点,有利于大规模的推广和普及。同时,由于智能手机的发展较为迅速,互联网技术中的搜索引擎技术,在互联网移动端的发展也愈加快速,成为互联网搜索引擎技术发展和创新的重点领域,更是互联网搜索引擎技术发展的新阵地。近年来,互联网搜索引擎技术正逐渐成为互联网时代商业与技术相结合的典型代表,而移动环境下的搜索引擎软件的开发和推广,也正在朝着理想的方向不断进步,本文所讨论和研究的移动环境下的互联网搜做引擎,是指通过移动设备,以其为终端,对互联网信息进行处理,通过为移动互联网用户,提供快速、便捷、准确的信息搜索渠道,不断提高和完善移动互联网层次,用户的搜索体验和搜索时间,在这样的背景下,以"关键字搜索结果聚类"为基础,为移动用户提供精准快速的搜索服务。关键字聚类是在这样的移动互联网发展的大背景下提出的新概念,它是一种重要的技术,通过关键字聚类的方法,可以在搜索的过程中,通过在搜索引擎客户端提供特征聚合服务,将关键搜索的结果按其相关的语义特征进行聚类。从而达到用数据挖掘的方法准确的将相关的信息聚合在一起并将其归类,进而提高对关键字话题研究和垂直搜索的快速检索。综上所述,在移动环境下对搜索引擎软件系统进行设计和研究,可以给移动互联网客户端的客户提供更为准确的搜索信息服务,让使用者最大程度的减少使用搜索引擎所耗费的时间,最大限度的提高搜索引擎的易用性和体验。同时为软件系统的开发商提供更为准确有效的商业营销和技术保障。所以,对于此类系统的研究,价值意义和实践意义俱佳,值得我们认真的进行分析研究和探讨,不断推动移动环境下搜索引擎软件系统的开发、应用和推广。1.1移动搜索的现状伴随着目前智能手机等移动设备的快速、大量普及,在移动环境下使用搜索引擎软件的前景和市场非常巨大,以全世界范围内的数据来看,截至2012底已经有3.35亿用户使用移动互联网搜索引擎技术这个新兴的技术。而对互联网移动端用户的调查显示,移动环境下,互联网搜索引擎的使用率非常高,3.35亿用户平均每人每天使用的搜索服务的次数为3.54次,这充分说明移动端互联网搜索引擎技术的前景非常看好,也正是这个原因,目前世界范围内几家大的搜索引擎服务提供商,都大力加强对移动端搜索引擎技术的研发和推广,并在下大力气将原有制约移动互联网技术发展的障碍排除。传统的移动互联网搜索引擎只是简单的讲互联网PC端的搜索服务移植到手机上,不能适应手机的具体情况,对不同型号、分辨力和CPU处理器的手机兼容性也不高,以我国最大的移动搜索引擎软件服务商百度为例,百度搜索在互联网方面,可以说是中文搜索的最高水平,但是在移动环境下的互联网搜索方面,百度搜索还存在着很多需要进一步完善的地方,例如,通过相同的关键字进行搜索,互联网网页 baidu. com>和手机网wap. baidu. com>,可以发现搜索的结果几乎一样,即：线性的呈现方式。因此,这样的手机网页搜索只是提供了传统的搜索服务,仅有区分WAP类型网页的功能；对于"聚合搜索",百度搜索是将搜索的结果进行分类,不是根据关键字所在的语义的聚合。市面上大多数所谓的聚合搜索只是将关键字搜索导航到各个不同的分类搜索网站。这样会带来手机用户对于搜索服务感觉无差异化以及用户体验的不好。作为手机、平板电脑等移动互联网设备终端,其位置的移动性和设备的局限性决定了移动环境下互联网搜索引擎必须具有自己的特点,不能与传统的互联网服务一概而论,需要通过细化用户市场,深入分析和总结目前存在哪些问题,从而对移动环境下的搜索引擎软件进行完善和提高,提供更适合于类似手机等移动设备使用人群的服务。1.2目前存在的问题纵观目前世界范围内,移动环境下搜索引擎的开发与应用,大多还处在开发的初级阶段,受PC端的互联网搜索引擎影响较大。目前全球范围内,所占比重比较大的移动端搜索引擎大多也是互联网界的巨头,如谷歌、百度、必应、雅虎等,他们的移动搜索引擎与互联网搜索引擎相差无几,所用的技术也大多是从互联网技术中移植过来的,对手机、平板电脑等移动端的互联网客户体验关注不多,或者说正在逐步的开发升级中。这些现有的移动端搜索引擎工作方式大抵相同,都是根据用户输入的查询返回以线性列表形式呈现的一组文档,但是在搜索排序方面,由于各家搜索引擎技术所有者的发展策略不同,对于同样的关键字搜索,出现的位置和频率略有差别,总的来说是越靠前的文档的相关性越高。所有的搜索引擎都是基于两种算法的,一种叫做排序算法,是利用搜索关键字在搜索结果中出现的不同位置和出现的频率进行排序的；另一种叫做PageRank算法,基于链接的一种搜索引擎技术算法。为了提高搜索的快速性和准确性,现有的搜索引擎技术一般会预先的搜索的结果和内容进行处理,通过诸如裁剪算法等方法,对结果进行筛选。但是还是难以解决用户面对海量的互联网信息,无法快速找到所要信息的问题,这个问题在屏幕容量有限的移动客户端上被更加放大,成为制约移动环境下搜索引擎技术发展的瓶颈之一。举例来说,在百度搜索中搜索"搜索引擎"会得到"117,500,000"项结果,而其中很多信息都是冗余信息,对用户不具有任何价值的,但是为了找出其中的有用信息,用户不得不在所有的信息中进行自行搜索,而在移动的环境下,这样的努力变的愈加困难,一方面由于屏幕有限,用户没翻一次页能获得的信息量大大小于电脑；另一方面,移动客户端往往数据传输信号不是特别稳定,一定程度上增加了用户对流量传输的担心和风险。基于以上两点,如果一个移动环境下搜索引擎不能够很快的搜索出用户需要的信息的话,用户往往会由于用户体验下降而放弃使用该搜索引擎。1.3本文的主要内容本文在借鉴现有移动环境下搜索引擎的发展经验和现状的基础上,深入发掘潜在的移动环境下搜索引擎用户需求,针对目前移动环境下搜索引擎发展的现状和特点,有针对性的解决用户最迫切的需求,将"聚类"这一更好的技术引入移动环境下的搜索引擎开发应用中,简言之,就是对搜索的结果进行聚类分析,将一组结果中类似的对象归入同一类,而不同的对象归入不同的类,这样的处理方式极大的提高了信息处理的效率和准确度,最大限度的减少了信息冗余的发生。使用聚类的方法能够大大提高用户的搜索准确度,提高搜索效率,同时能够根据客户的兴趣和常搜索的类别,对不同的客户进行不同的信息检索,进而能够提高搜索引擎与用户之间的互动和交流。本文的研究主要涉及移动环境下搜索引擎软件的开发和应用,主要的研究方向是针对当前流行的移动互联网搜索引擎的快速发展,探讨如何进一步完善和改进现有移动环境下搜索引擎技术。主要探讨如何将聚类方法合理地应用到搜索引擎的数据挖掘中去。由于聚类方法是一种无监督学习方法,经过聚类后得到的结果是根据对数据的相似性分析后得出的差异性分组结果。对提高搜索引擎结果的类别性划分十分有价值,是对关键字搜索技术的细化和分类,并且能够根据客户的不同情况,有针对性的提供搜索结果,便于客户提高搜索的兴趣和对搜索引擎的易用性。本文研究主要内容如下：介绍现有搜索引擎技术及其发展的经验和存在的问题介绍本文中设计实现的中文分词模块系统介绍文本聚类,并设计实现基于搜索结果LINGO聚类算法对"妙搜"移动搜索引擎技术进行设计和实现对"妙搜"移动搜索引擎技术的各个子系统、子模块进行分别介绍测试"妙搜"移动搜索引擎技术的运行并对结果进行分析评估1.4本文的章节安排根据写作安排,本文对移动环境下搜索引擎的开发、应用和实现分为七个章节分别阐述,各章节内容如下：第1章绪论,主要介绍了移动环境下搜索引擎的发展现状及研究意义。第2章搜索引擎关键技术介绍,是对国内外关于搜索引擎技术方面的研究成果的介绍和阐述,对现有的搜索引擎技术和搜索引擎服务的相关内容、步骤的阐述,对在移动环境下,搜索引擎技术面临的问题和新情况进行描述,对用户在移动环境下如何应用搜索引擎技术提出设想。第3章LINGO聚类算法分析,对本文中重点涉及到的重要理论"聚类"的思想进行介绍,从概念入手,逐步将"聚类"的思想和精髓分条阐述,并以本文中重点应用的聚类算法LINGO聚类算法为切入点,详细阐述了聚类算法的实现过程,并对其的应用价值和存在的隐患问题进行了分析,为后续设计提供了理论铺垫。第4章妙搜移动搜索引擎系统的需求分析,从系统研究背景入手,对移动环境下搜索引擎技术的用户需求,潜在用户市场和未来预期的用户领域进行了细致的分析,对新时代互联网搜索引擎在移动终端的应用,以及"妙搜"系统的预期功能目标进行了介绍,对"妙搜"系统与移动环境下互联网终端之间的磨合以及应对平板电脑为代表的移动互联网终端新趋势进行了展望。本章还对"妙搜"系统性能要求进行了介绍,力求全面的分析"妙搜"系统的用户前景和需求来源,从客户需求的角度,分析"妙搜"系统的可行性。第5章妙搜移动搜索引擎系统的分析与设计,本章是本文的主要内容和核心,是对移动环境下互联网终端搜索引擎技术的详细介绍,也是本文所设计的"妙搜"系统的最全面、完整的介绍。本章从系统总体目标开始,介绍了"妙搜"系统的软件技术平台选择,进而分节介绍了"妙搜"系统必要环节和各个子系统,分别是：妙搜服务系统架构设计、内容爬取子系统设计、索引子系统设计、搜索处理子系统设计、中文分词算法设计、聚类设计、缓存子系统设计、通信接口层设计。通过以上的设计,对"妙搜"系统的全部核心技术和需要应用到的原理进行逐一阐述,力求详尽的介绍"妙搜"系统的功能及其原理,为系统的实现奠定了理论和实践基础。第6章妙搜移动搜索引擎系统的实现。重点介绍了"妙搜"系统的应用与实现过程,通过对Nutch系统的安装启动进行详细的介绍,对中文分词和聚类模块给出了具体的实现,同时以安卓手机操作系统为基础,开发设计移动环境下搜索引擎客户端应用。最后对整体运行系统并对系统进行了测试运行。第7章 结论,是对全文的总结,也是笔者在对移动环境下搜索引擎技术进行大量的搜集调研的基础上,对现行的"妙搜"系统进行了设计、试运行和实现之后,提出对于"妙搜"系统而言,今后进一步开发、优化中所需要注意的重点问题和提出的下一步思考。第二章搜索引擎关键技术介绍 搜索引擎技术是互联网时代发展起来的现代科学技术之一,由于现代社会信息量爆炸,如何在海量的信息海洋中快速、准确的搜寻到自己所要的信息,成为现代互联网时代最重要的课题之一。因此,搜索引擎技术的发展伴随着互联网科学技术的发展而快速壮大。近年来,由于以手机、平板电脑为代表的移动互联网终端的快速发展,已经有很明显的趋势：未来的互联网技术发展,移动互联网技术将在其中占据重要地位,而移动环境下的搜索引擎技术,也成为科学研究的热门领域之一。本章重点将对移动环境下的互联网搜索引擎技术及具体的搜索引擎技术方法进行阐述,为下文中对"妙搜"系统的介绍和分析进行理论铺垫。2.1搜索引擎的定义根据大英百科全书的相关信息收录,搜索引擎,是现代互联网技术之一,目的是为了帮助互联网用户包括PC电脑用户在互联网上对信息进行查找的一种软件程序。它通过与用户进行网络互动,将所要查找的信息通过关键字、词组、短语的形式,进入互联网信息查找系统,并对互联网信息尽心扫描,以分类或者是其他分析方法的形式呈现在用户面前。现代搜索引擎技术的发展,使得用户可以通过各种互联网终端,对搜索的信息进行再搜索和分析处理,通过各种方法,实现对互联网信息的快速查找和检索,提高互联网应用的效率。目前常见的搜索引擎根据其查找方式的不同,可以分为三大类：第一种称为全文搜索引擎、第二种是目录索引类搜索引擎,最后一种也被称作元搜索引擎。进入新世纪以来,互联网技术中的搜索引擎技术有了突飞猛进的发展,实现了跨越式、交叉性、多学科的发展模式,在国内外的商业互联网巨头中,都产生了诸如谷歌、百度、必应、雅虎等互联网搜索门户网站,这些新兴的互联网商业帝国的快速成长,也印证了搜索引擎技术在整个互联网技术中的重要地位。面对着互联网时代信息量剧增的现实,今后互联网搜索引擎技术还将在多个领域继续快速发展。对用户的需求和拓展也在不断深入和继续。深化和开发互联网搜索引擎技术的新市场成为今后发展的重要方向之一。2.2搜索引擎的发展现状互联网时代的来临,给搜索引擎技术的发展带来了一个很大的机遇,互联网的发展与进步为搜索引擎技术的发展方向起了指导,使得互联网搜索引擎技术朝着以下几个方向发展：2.2.1.向智能化方向发展智能化是互联网技术发展的总体方向之一,对互联网的发展起着纲要性、指导性的作用。特别是随着移动环境下互联网技术的发展,智能化的方向也在指导着互联网搜索引擎技术的发展。智能化能够提升搜索引擎使用用户的搜索效率,能够提高搜索引擎的准确性,提高搜索引擎系统的易用性。此外,通过互联网搜索引擎技术的智能化,能够最大限度的实现搜索引擎系统与用户之间的交流与互动,为用户提供一个由系统智能处理后的最优搜索结果。2.2.2.向媒体化方向发展搜索引擎技术与媒体有着天然的联系,搜索的结果既可以以文字的方式呈现,也可以以媒体的方式呈现,随着用户对搜索结果的要求越来越高,互联网搜索引擎技术的发展中媒体化的趋势也愈加明显。通过媒体化,互联网搜索引擎技术的用户可以在结果中看到更多的视频、音频等多媒体信息,这也是互联网技术突飞猛进发展的必然结果,试想,随着互联网技术的快速发展,用户对媒体信息的检索需求也越来越多,而为互联网用户服务的搜索引擎技术也是大势所趋。2.2.3.向特异化方向发展特异化包括个性化和特色化,是对互联网搜索引擎用户的不同需求的描述和阐述。面对海量的用户需求和互联网技术的不断发展,满足不同的用户的不同需求,而不是千篇一律的提供同样的搜索结果,是互联网用户对互联网技术发展的必然要求,也是搜索引擎技术发展的方向之一。通过特异性的发展,搜索引擎技术能够充分利用这些特异性信息来提高用户的检索效率,并为用户提供全程帮助和服务,使得个性化搜索更符合每个用户的需求。2.2.4.向功能化方向发展搜索引擎技术的发展,与互联网技术的发展是息息相关的,目前互联网技术的发展,呈现出"科技改变生活"的理念,与现实生活中的各种活动结合的越来越紧密,因此搜索引擎技术的发展也离不开为用户的现实生活服务,这就是我们所说的功能化。功能化表现在搜索引擎技术在发展中不再满足仅仅表现为单一的搜索功能,而且通过其他的生活服务,为互联网用户的生活提供服务,在诸如新闻、百科、文档搜索、天气预报等方面,有利用搜索引擎技术对信息的即时性和敏感性,提供由于其他互联网服务的优质功能性服务。2.2.5.向商业化方向发展互联网上进行商业活动已经不是新鲜事物了,但是互联网技术中搜索引擎技术的商业化才刚刚起步,由于搜索引擎往往伴随着大量的用户浏览量,搜索引擎的商业价值一直以来被开发者所重视,从早期的提供互联网广告,到后期的提供推广型搜索服务,再到目前开始发展的互联网电子商务、电子物流、电子服务等。可以预期,今后互联网搜索引擎技术的发展将为搜索引擎技术的发展带来更大的服务和突破。它已经成为搜索引擎技术发展的主要动力,通过商业化的发展,搜索引擎的完善和扩展功能增添了无穷动力,为互联网技术的发展提供了有力的支持。2.3搜索引擎系统运行的几个步骤2.3.1内容抓取 搜索引擎技术的首要步骤是内容的抓取,简言之,就是对互联网信息和内容的抓取,一般是通过根据既定的规则对互联网上的网站内容,信息进行搜索、扫描和检索得到的。这其中涉及到的技术是对互联网站点进行深度优先遍历和广度优先遍历两种扫描模式,从一个网站的网页上转到另一个网站的网页上,如此往复,以保证所得到的信息是最大限度的为用户所使用。2.3.2中文分词中文分词技术是移动环境下互联网搜索引擎技术对中文文献搜索所需要涉及的核心技术,是对中文内容的检索核心技术。中文分词技术要解决的问题,是针对中文特有的语法习惯而设计的,比如说,中文相对于西方的文字来说,所有的词组都是有字组成的,而在连续的由文字组成的意思表达串中,如何将其根据中文的语法分解成为一个个有独立意思表示的文字单元,就成为中文检索需要解决的重要问题之一。纵观现有的互联网搜索引擎技术,对中文分词的作法,一般可以归纳概括为以下三种算法：第一种是基于字符串匹配的分词方法,也有很多学者将其称为机械类的中文分词法。它是能够基于中文搜索的请求,进行正向匹配配合负向匹配的一种综合算法,因而也具有中文分词算法简单易行,能够有效的提高中文分词的效率；第二种是基于统计的分词方法,它能够智能化的利用搜索过程中出现的文字频率,自动进行统计归类,将新出现的词语有效的进行分类识别,因为智能性更高,但是因为需要对数据进行统计和归类,因而在处理速度上,略逊于基于字符串匹配的分词方法；第三种是基于理解的分词方法,这种分词方法的智能化程度最高,也能够适应汉语的行文结构,它是利用计算机,通过模拟智能行为,对句子进行理解和分类,进而将中文语言的组成信息和各种语法元素,通过机器识别、解读的方法进行读取,因为这方面的技术还不够成熟,因此这种分词方法还处在研究阶段,在实际中的应用十分有限,但是体现了未来搜索引擎技术发展的智能化趋向,因此前景十分广阔。2.3.3索引由索引进行的搜索引擎系统技术是搜索引擎技术的重要组成部分,它能够对系统通过程序搜集的各种信息进行处理和分析,从中进行提炼和检索,特别是对互联网的网页信息,索引的方法可以很容易的将包括网页所在URL、编码类型、页面内容包含的所有关键词、关键词位置、生成时间、大小、与其它网页的链接关系等在内的网页内容进行有效的处理。索引的本质是利用一定的相关度算法对搜索引擎技术的应用中进行的大量计算进行处理,同时根据每一个网页的文字与所搜索的相关关键字的联系程度建立相关的索引数据库,同时根据结果进行归类。在索引的过程中,重点需要注意以下几点内容：有连贯的被索引的信息文件。通过索引能够运用语法分析或者是语言处理的方法,使索引内容形成Term<系列词>。通过索引能够形成索引词典或者通过反向索引形成表格。索引的内容能够储存并读写进入硬盘。2.3.4排序搜索引擎系统中所指的排序,是指在搜索引擎的运行过程中,能够从网页信息的索引中找到相关数据库,并通过相关关键词,以网页的形式展示搜索结果。同时,还能够根据相关网页信息内容与所要检索的关键词的关联程度,自动将相关度较高的网页信息或者内容排列在搜索结果展示网页的前列。通过排序,能够提高用户的体验,是搜索引擎技术的重要成果性技术。2.3.5用户搜索接口所谓用户搜索接口,是特指为用户提供的相关界面,用于在用户在搜索引擎输入界面输入关键字进行搜索之后,由搜索引擎系统将用户的搜索结果以链接和页面显示内容摘要的方式,组织起来,为用户提供搜索服务。通过给用户提供搜索接口,能够将搜索的内容返回给用户,并将搜索的内容以一定的组织形式呈现出来。关于用户搜索接口,需要特别说明以下的几个方面：用户搜索的需要输入的语句。对用户的搜索关键词或者语句进行分析得到的Terni<系列词>。通过对搜索关键词的语法分析进行查询得到的查询树。利用搜索将索引读入内存。利用搜索的查询树索引,将每个词的文档链表进行交叉,从而得到搜索的结果文档。对搜索的结果文档进行排序依据与查询关键词的相关性将查询的结果以特定的形式返回给用户,完成搜索。2.3.6搜索引擎工作流程总结一般来说,在移动环境下的互联网搜索引擎的主要工作流程是：利用搜索关键词,将内容进行抓取,每个一段时间,将读取URL列表该列表来自网页服务的URL服务器上同时,再根据深度优先或广度优先的算法,将前述所抓取的URL列表统一的分配到文档中,将该文档命名为唯一的ID类型,并将该文档进行一定程度的压缩之后,将其与所在网页上的所有链接存入到系统的数据库中。需要特别指出的是,在搜索引擎系统进行抓取内容的同时,特定的切词系统或者索引系统,将对抓取的网页或者文档进行自动的切词处理,以便能够根据不同的词汇在网页或者搜索信息中所出现的频率和存在的位置进行计算,得出其存在和出现的权重,将切词处理后的结果存入到索引文件中,以备后期使用。紧接着,在全部的抓取工作和索引工作完成之后,及时更新全部的索引文件和整个数据库,将用户所查询的网页信息,以最快最全的方式,通过查询器对信息进行处理,并将处理的结果和全部的网页链接、简要内容,以该信息在整个结果中的相关度或权重为依据进行排序,将排序的结果以搜索结果的形式呈现在用户的面前。2.4本章小结本章主要是对互联网搜索引擎技术的基本技术和基本原理的介绍,首先对搜索引擎技术的定义进行了阐述,对搜索引擎技术的发展、搜索引擎技术的主要分类,以及搜索引擎技术的发展方向进行了描述和分析,再通过介绍搜索引擎系统运行的几个步骤,阐明互联网技术发展的方向,以及搜索引擎技术下一步发展的重点领域,并为下文对"妙搜"系统的介绍和阐述奠定基础。第3章 LINGO聚类算法分析文档的聚类<Clustering>是一种重要的聚类,它的理论基础是一个有名的假设,即相同种类的文档之间的相似程度是很高的,不同种类的文档之间的相似程度很低,在聚类的分类中,不需要专门的训练过程,能够自动的对文档进行手工标记类别,这样一来,文档的聚类就具有比较高的自主性和自动处理的功能,也就能够大大提高对关键字文本的处理能力,提供处理效率。因此,文档的聚类一般来说,被视作是一种无监督的学习方法英文为Unsupervised learning>。3.1聚类的概念严格来说,聚类是一种方法,这种方法把一组信息体按照各自不同的特点或者相似程度分为几种不同的类别,在专业领域也被称作是组或者是簇。这种方法使得同类个体相互之间的距离很小,不同种类的个体之间距离很大,这样非常有利于同类个体相聚,异类个体分离。正因为如此,聚类经常被用于进行数据挖掘,对数据进行多元统计和分析,成为一种重要的非监督模式的识别方法。区别与分类,聚类对类别的划分并非人为设计和进行安排的,而是由计算机系统根据一定的程序设计自主进行的分类,因此,聚类被称为非监督学习,即是根据不同数据之间的相似程度和差别,自主的发掘数据的内在规律,进而对数据进行更加准确和深刻的归类。这种方法远胜于分类的那种由人为预先设定的方法,分类也被成为是一种监督学习的方法。3.1.1文本聚类的基本思想文本聚类是利用聚类的思想,对文本之间进行的一种归类,它根据的理论是运用聚类的方法,对文本进行智能识别和分析,根据不同文档中的信息,找出其特定的内在联系和相似程度分析,从而对文档进行集合、归类和搜寻,便于用户充文档中快速、准确发现信息。其理论基础也是聚类的思想假设,即相同种类的文档之间的相似程度较高,不同种类的文档之间的相似程度较低,通过这种理论,作为无监督学习方法的一种,聚类的思想在搜索引擎的应用中,使得系统不需要事先对文档的类别进行人为的标注,自动的就能够有效的处理信息并进行聚类分析。3.1.2文本聚类的过程根据目前研究的成果,文本聚类的一般工作流程是,将非结构的问题进行一定的归类和安排,使其相对的结构化,然后利用特定的数据挖掘技术,对文本信息进行聚类。通过首先的文本进行处理,从中提取关键词,然后对文本的特征、类标签进行提取,发现不同的类别,整理归类其内容,从而使得文本可以通过结构化的形式进行描述,然后再根据不同的应用需要和客户的需求,选择不同的聚类算法,最后将全部的聚类效果进行评估,以期能够改进聚类的过程。如下图所示：图例1图3. 1聚类过程图3.2LINGO算法概要作为一种被广泛使用,并受到良好赞誉的聚类算法,LINGO算法在运行中,能够充分的考虑到标签特别是一个方便理解和能够准确表达类信息的标签在分类中所起的重要作用和收到的良好效果。区别于其他普通的算法,LINGO算法不是对数据先进行聚类然后对标签进行提取,LINGO算法的方案似乎有些与众不同,它首先将方便理解的类标签进行提取,之后再对文档进行分配,利用后缀树组SuffixArray来对关键词进行提取,并在构造词文档矩阵中利用奇异值的分解方法来发现搜索的结果中可能存在的抽象概念,而这些抽象的概念往往是存在于不同的标题之下的。随后,LINGO算法通过对搜索关键词或者关键词组与信息中的抽象的概念之间比较关联度,对相对度比较高的N个标签作为类标签,进而将文本分配到相关度最高的类别中,便于用户的搜索和应用。3.3LINGO算法基础之后缀数组3.3.1短语完整性短语是具有词语顺序的多个词或者字所组成的初级汉语单位,LINGO算法的特点在于在对短语中的关键词或者关键字的寻找和提取中,能够将关键性的短语<key phrase>,准确的找寻到,这样既能够准确的解读文档中的关键信息,同时能够大大提高聚类的可读性。提取出来的短语首先要确保的是其完整性。提出了短语完整性的概念。设文档T,其长度为N,T的完整子字符串S定义为：S称为T的完整子字符串,当S在T中出现互不相同的k次的位置P, P2. ., Pk时,其中至少存在一对吏得T中第</0-1个字符与第个字符不相同左完整性,并且,其中至少存在一对</,/><1_/0使得了中第<p, +|<s1>个字符与第</ +岡>个字符不相同<右完整性>。我们以文档T= "tobeornottobe"和T的子字符串"to_be"为例,说明一下以上的概念。左完整：子字符串"to_be"是左完整的,比较第<0-1>个字符,和第13-1>个字符"",两者不同,根据以上概念定义,"tobe"是左完整的。右完整：子字符串"to_be"也是右完整的,比较T中第<0+5>个字符"一"和第13+5>个字符<T的结尾处,两者不相同,根据以上概念定义,"tobe"也是右完整的。根据完整字符串的定义,"to_be"就是T的完整字符串。3.3.2后缀数组在LINGO算法中,后缀数组<Suffix Array>是一个重要的数据的结构,这种数据结构的特点就是效率特别的高,高效率来自于它能够准确的对文档或者文本中的信息进行充分的解读,并从中找出关键性的短语。设一个文档T,长度为N,T的后缀数组S指将T所有的后缀按照字符顺序排序,而令后缀起始的位置按排序后的顺序构成的数组。例如,设文档T ： to_be_or_not_to_be?它的后缀集合为rs,则有下表所示：表3.1后缀数组表表1表3. 2后缀数组表表3. 2从上述表格可以看出,实际需要存储的仅仅是表格的中间一列,很明显后缀数组的存储只需要0<aO的空间,其中N为文档的长度。而创建后缀数组的算法的期望时间复杂度也是0<aO,查找一个长度为P的字符串只需要0<尸+ logJV>的时间。3.4 LINGO算法基础之隐含语义分析隐含语义其实是汉语语法中的一个重要的特色,在其他语言中也有所体现,简言之,隐含语义分析就是针对日常用语中的同义词或者近义词进行有效的归类和合理的分析,同时对具有相同意思表达的词组短语进行有效的应用,例如,在汉语中,"教师"和"先生"是完全不一样的两个词,但是在词语的词义和实际的应用中可以做到语义互换,能够表达出同样的含义。如果利用向量空间模型对所有的词语或者关键词进行完全匹配,必然无法将同义词这种意思相同表达不同的词语做到完全区分,即如果将"教师"作为关键词进行搜索,那么对文档进行聚类分析之后,以"先生"为关键词内容的相关意思一致的文档也就无法显示出来,这给我们的搜索引擎发展带来了技术性的瓶颈。事实上,在搜索引擎的实际应用中,对词组或者是关联词的使用,是搜索引擎技术发展的一个必由之路,因为在汉语中,有很多类似的隐含语义分析的词组短语,而它们在外表上看是格格不入的。例如,"高等院校招生","高等院校"和"招生"是两个相互独立、又有一定联系的关键词,如果用户搜索"招生",就会显示出含有"招生"作为关键词的文档匹配项,但是很可能有一部分包含有"高等院校"的内容,但是不包含"招生"。所以我们认为这两个词存在着一定的语义关系,这类文档也可能包含了用户所需信息。作为一种常用的信息检索技术,隐含语义分析Latent Semantic Indexing, LSI>的出现最重要的作用是弥补向量空间模型所存在的缺陷。根据隐含语义分析Latent Semantic Indexing, LSI>的观点,词语的选择背后是隐含着一种来自语言含义方面的信息流,这种信息流是搜索的精髓,如何利用隐含语义分析的方法,从词中提取的抽象概念替换或者取代与搜索关键词意思相同的内容。即将向量空间模型中简单的词汇的匹配替代为语义的匹配。如果把用来检索的文档之间的内容看做是词空间下面的一个子空间,那么任意两个不同的文档之间的子空间距离越小,则这两个文档之间的语义上就越相关,因此,词往往被视作是一个文档空间内下属的一个子空间,通过对两个词语之间的子空间距离进行的判断,可以对两个词语之间的相关程度进行大致的判断和分类。在实际操作中,由于词与词,文档与文档,以及词语文档之间的子空间的分布不是随机分布的状态,而是出于全文整体语义、词义的内容之中的,因此会受到上下文和整个文章所要表达的思想的束缚和限制。在这种情况下,语义空间表现出了词-词、词-文档、文档-文档之间在语义上相关性。而在实际操作中,由于词文档矩阵的数据往往非常庞大,而且鉴于汉语文化的博大精深,常常会出现一词多义,多词一义的情况,这种情况的出现在现代汉语语文的行文和应用充非常常见,因此会给我们的判断带来干扰和迷惑,在这种情况下,与向量空间模型中的文档高维表示不同,潜在语义标引还需要利用数学工具将原来的文档高维表示投影到低维的空间、即潜在语义空间中,简化语义的空间结构,从而达到缩小问题规模,消除并减少常见的迷惑和干扰。进而在得到潜在语义空间之后,就可以根据各个词和文档的向量坐标进一步进行分析。3.5 LINGO算法过程分析3.5.1文本预处理所谓的文本预处理,是指为了进一步提高取类标签的准确性,将文本以聚类算法可用处理的形式进行预处理,具体包括两个阶段：第一个阶段叫做特征表示,第二个阶段称为特征提取。一般常见的理论认为,文本的特