（教育技术学专业论文）基于主题相关领域搜索引擎的研究.pdf

摘要 随着互联网的发展，一些主题网站和内部局域网的信息量也大幅增长。人们 发现在通用搜索引擎上面搜索某类主题信息的及时性和准确性还不理想。目前虽 然己经有g o o 酉e 、百度这些优秀的通用搜索引擎，但是它们并不能很好的解决这 个问题。一方面，由于局域网内部信息检索的需要，不能对百度与g o o 西e 公开： 另一方面，通用搜索引擎的页面更新比较慢，信息的实效性、准确性都无法保证。 因此，为了提高提高主题类网站或者局域网内信息检索的效率，本文研究并实现 一个基于主题搜索的小型搜索引擎。 本课题要研究了面向主题领域的搜索引擎。它是一个典型的专业搜索引擎。 希望通过本课题的研究，能够开发一个基于相关领域、相关信息完整的搜索引擎 系统，并在系统中重点研究信息的搜索算法和分词技术，以便对搜索引擎技术、 搜索算法和中文分词有更进一步的了解和掌握。 论文的主要工作主要有：阐述了网络蜘蛛页面爬行算法与原理，在分析总结 基于关键词算法与基于概念的算法之上，使用了用分析超链接改进主题爬行的策 略。通过实验数据，对比引入链接分析前后的结果，论证了其实现可行性与可操 作性，为实现定向信息采集奠定了良好的基础；设计了分词器的“正向最细粒度 最长算法 分词算法，提高了分词准确率并具有高速处理能力，满足了搜索引擎 的使用，并对系统进行了测试和性能分析。 关键词：主题搜索；小型搜索引擎；l u c e l l e a b s tr a c t w i 1t h ed e v e l o p m e n to ft h ei n t e m e t ， t h eq u a l l t i t yo ft h ed a t ao fm a i l yw e b s i t e s a i l di i l 协a j l e t si si n c r e a s i n gs h a 印l y i tw a sf o u l l dt l l a tt h et i m e l i n e s sa l l da c c u r a c yo f t l l e s e a r c hr e s u l to fm e s eg e n e r a ls e a r c he n 百n e sw h e nt h e ys e a r c hc e r t a i nt y p eo f i n f o 咖a t i o na r en o tv e 巧w e l l a 1 m o u 曲a tt h em o m e n tu s e r sc a ne m p l o yg o o 百e 龃d b a i d u ，t l l e s eo u t s t a n d i n gg e r a ls e 鲫c h 朗西n e sc 锄t ts o l v ct l l i sp r o b l 锄，e i t l l 既o n m eo n eh a l l d ，s o m e 曲南姗a t i o nw h i c hn o wi n 廿l ei n 把m e tc a i ln o tb eo p e nt ob a i d u 狮dg o o 酉e ；m eo t h e rh a n d ，g e n e r a ls e a r c he i l 西n ep a g eu p d a t e dm o r cs l o w l ys 0t h e e 虢c t i v e i l e s sa i l da c c u m c yo fi n f b m a t i o nc a l ln o tb eg u a r 狮t e e d t h e r e f 0 r e ，i no r d e rt 0r a i s et h ee 伍c i e l l c yo fi n f 0 m a t i o nr e t r i e v a lo fw 曲s i t e s a n di m a i l e t s ，m i sp a p e r 咖d i e s 趾i dd e v e l o p e sas m a l lt o p i cs e a r c he 姆n e n et o p i c s e 盯c he n 酉n e ，o r i e l l t e dt ot l l es e a r c ho fc e r t a i nt 1 1 锄e s ，i sat y p i c a lp r o f e s s i o n a l s e a r c he 1 1 百n e h o p i n gm a t 伽0 u 曲t l l es t u d yc 狮p e o p l ed e v e l 叩as e 锄c he i l 孚n e s y s t 锄b a s e do nr e l a t e df i l e d sa 1 1 dr e l e v a i l ti n f 0 1 m a t i o n a n dt h i sp a p e r f i o c u so nm e s t u d yo ft 1 1 es e a r c ha l g o r i t h m sa 1 1 ds e 舯e n t a t i o nt e c l l i l i q u e so fi n f o m a t i o ni no r d e rt o 龟n h e ru n d e r s t 姐d 锄d 蓼a s pt h es e a r c he n 百n et 池l o g y ，s e 鲫c ha l g o r i 砌m e c 1 1 i n e s ew o r ds e 舯e i l t a t i o n t h ep 印e ra i m st o ：g h j d yn c t w o r ka l g o r i t h m s 趾dp d n c i p l e so fs p i d e r sc m w l i n g ， s t i l d yt h em e t h o d so fi m p r o v i n gf o c u s e d - c r a w l i n gb ya i l 2 l l y z e i n gh y p e d i r l l ( so nm e b a s i so f 锄a l y z e i n ga i l d 渊撕z i n gk e y w o r d b a s e da l g 嘶t 1 1 ：m sa i l dc o n c e p t - b a s e d a l g o r i t h m s n u g ht 1 1 ee x p e r i m e n t ，t h i sp a p e rc o m p a r e dt h e 研or e s u l t s ( o n ei sm e r e s u l to b t a i n e db e f o r et h ei m p r o v 锄e n t ，锄dt h eo t h e ri s t l l ee x p e n m e n t a lr e s u l t ) ， e x p o u n d e do nt l l e 矗蕴s i b i l 时a 1 1 do p c r a b i l 时o fi t si m p l e m e i l t a t i o na 1 1 d 1 a i d ag o o d f o u n d a t i o nf o rt a r g e t e di n f o n l l a t i o nc o l l e c t i o n ；d e v e l o p e daw 6 r ds e 舯e n t a t i o n a 1 9 0 r i t l l mt h el o n g e s tb e i n gt h em o s tf i n e - g r a i n e da l g o r i t h m f o rw o r dd e v i c e ，” i m p r o v e dm ea c c u r a c yo ft l l ew o r ds e g m e n t a t i o na i l di to w n a h i 曲一s p e e dp r o c e s s i n g c 印a b i l i t y t om e e t l eu s e so fs i n a l l s e a r c he n 舀n e s ，a 1 1 dt e s t e d 觚d 锄a l y z e dt h e s y s t a nt e s t k e y w o r d s ：t o p i cs e a r c h ；s m a l ls e a r c he i l 舀n e ；l u c e i l e n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得叁鲞竖整盘堂或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 签名：舀j ：燃日期：幽 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有 权将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印 或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机 构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：列亟燃导师签名： 日期：列蜂目 fi 1 1 本文研究背景 第1 章绪论 搜索引擎是一款特别的软件系统，能够从互联网上自动收集信息，并为用户 提供查询服务搜索引擎对原始文档进行了一系列的整理和处理。用户的查询结果 是搜索引擎按照某种规则计算获得的。搜索引擎为网民提供了资源查找和导航的 有效手段。 搜索引擎技术的市场不仅限于门户网站，专业网站同样也需要快速有效的搜 索。互联网的迅猛发展使其所含的信息数量激增，在这样一个无限、无序、浩瀚 无边的信息空间里，快速查找并获得所需要的信息已成为人们最迫切的需求。现 在的互联网用户，不是为找不到信息而发愁，而是为如何从海量的信息中发现自 己需要的信息而迷惑。在通用搜索引擎中键入检索词，得到的输出结果是多方面 的，包含多个主题和领域。虽然众多网络用户的需求是多方面的，但是对某个具 体身份的用户而言，他很可能需要特定的，通用的搜索引擎的排序的结果不能满 足这些特殊用户的需求。开展专业搜索引擎的排序作研究，就有很大的现实意义。 综合搜索也将肯定迈入细分领域，例如百度在推出的m p 3 ，图片，视频，新闻等 专题搜索表明主题搜索的存在意义【l 】。 主题搜索引擎是相对通用搜索引擎的信息量大、查询不准确、深度不够等提 出来的新的搜索引擎服务模式，通过针对某一特定领域、某一特定人群或一特定 需求提供的有一定价值的信息和相关服务。其特点就是“专、精、深，且具有 行业色彩，相比较通用搜索引擎的海量信息无序化，主题搜索引擎则显得更加专 注、具体和深入。 1 2 搜索引擎的发展 随着近几年小型主题搜索引擎的快速发展。在国内，一方面，很多基于主题 领域的小型搜索引擎得到很好的发展，一些音乐搜索引擎以及医药方面的搜索都 有很好的应用。另一方面，在越来越多的学校、企业、比较大型的网站如b b s 都开始建立了自己的搜索引擎。在国外，比较著名的有：美国教育资源信息搜索 的a s k e r i c ，实现医药文献搜索的h i 曲w i r e 等，小型专业的搜索引擎涵盖了很 多方面。g 0 0 百e 公司在2 0 0 7 年决定向小型网站提供专门的搜索服务。0 8 年g o o 誊e 推出的音乐搜索推动了g o o 舀e 在中国市场的占有率上升了4 个百分点。百度也 分出了新闻，网页，m p 3 ，视频等主题搜索【8 1 。 在小型搜索引擎快速发展的同时，越来越多的人致力于研究和发展这些小型 搜索引擎开发技术，l u c e i l e 和n u t c h 是其中的最为优秀的代表成果。l u c e l l e 是 一个高性能、纯j a 的全文检索引擎，完全开源、免费。l u c e n e 几乎适合于任 何需要全文检索的应用，尤其是跨平台的应用。在成为a p a c h e 下的一个子项目 后，l u c e l l e 得到快速发展，它的设计目标就是为各种中小型应用程序加入全文 检索功能。 小型搜索引擎与通用搜索引擎相比有很多优点，由于它本身的信息量小，它 不可能取代通用搜索引擎。但是，它是对通用搜索的很好的补充。随着w e b 上 信息的进一步扩大，小型搜索引擎也将会进一步发展。 1 3 本文的主要工作 本文深入研究了通用搜索引擎基本原理、系统架构设计和搜索核心技术的基 础上，以现有的网站为实验平台，利用并改进了已有的网络蜘蛛进行网页的预分 析和抓取，结合开源的l u c e i l e 引擎工具包设计并实现了一个可扩展、可复用的 小型的搜索引擎系统。本文的具体工作有，研究了网络蜘蛛页面爬行算法与原理， 在分析总结基于关键词算法与基于概念的算法之上，研究了用分析超链接改进主 题爬行的策略。通过实验数据，对比引入链接分析前后的结果，论证了其实现可 行性与可操作性，为实现定向信息采集奠定了良好的基础；设计了分词器的“正 向最细粒度最长算法 分词算法，提高了分词准确率并具有高速处理能力，以满 足小型搜索引擎的使用，并对系统进行了测试和性能分析。 2 第2 章搜索引擎相关技术 本章主要研究了搜索引擎的工作原理。首先从页面搜索模块的工作原理、页 面搜索和建立索引、数据检索模块的工作原理三个方面描述了搜索引擎技术原 理；然后描述了主题搜索引擎的技术特点和信息采集技术；最后分析了n u t c h 一 一开源搜索引擎。 2 1 搜索引擎的工作原理 在浩瀚的信息海洋中找到想要的信息，搜索引擎便是一个最好的工具。搜索 引擎本身是一个十分复杂的应用系统，需要进行自然语言处理。而中文搜索引擎 又由于汉语本身的特点，必须引入对于中文语言的处理模块，其系统实现更为复 杂。搜索引擎的工作原理，大致分为分成三步：从互联网上页面采集一分析原始 网页并建立索引数据库一在索引数据库中搜索排序。如图2 1 所示，是一个典型 的搜索引擎系统架构图，搜索引擎的各部分都会相互交错相互依赖。 图2 一l 搜索引擎的工作原理 3 2 1 1 页面采集模块的工作原理 页面采集模块通常又由管理子模块、s p i d e r 程序、解析子模块、页面信息数 据库等部分组成。管理子模块负责向s p i d e r 程序提供遍历策略；s p i d e r 负责访问、 采集网页；解析模块首先对所采集到的数据进行进行语法解析、剔除语法标签， 将网页的页面内容送至页面信息数据库保存，同时判断所采集的网页是否是新增 或更新的网页，若是则将其文档内容提交给页面处理模块处理；若s p i d e r 无法 采集访问u r l ，则直接向数据组织模块发送删除此u r l 相关信息的指令。 互联网上中文信息资源非常多，但受数据库存储空间等诸多因素的制约，搜 索引擎只能遍历一定数量的网页。s p i d e r 遍历完规定数量的网页后即停止，同时 清空u r l 队列，再由人工指定或按一定算法从页面信息数据库中提取一定数量 的u r l 作为初始种子u r l ，开始新一轮周期的网页遍历。对于搜索引擎来说， 要抓取完互联网上所有的网页几乎是不可能的，从目前公布的数据来看，容量最 大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。这其中的原因一 方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页的链 接中找到；另一个原因是存储技术和处理技术的问题，如果按照每个页面的平均 大小为2 0 k 计算( 包含图片) ，1 0 0 亿网页的容量是1 0 0 2 0 0 0 g 字节，即使能 够存储，下载也存在问题( 按照一台机器每秒下载2 0 k 计算，需要3 4 0 台机器 不停的下载一年时间，才能把所有网页下载完毕) 。同时，由于数据量太大，在 提供搜索时也会有效率方面的影响【2 1 。因此，许多搜索引擎的网络蜘蛛只是抓取 那些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深 度。在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先，如图 2 2 所示。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再 选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的 方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指 网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再 转入下个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候 比较容易。 4 广度优先抓取顺序： 卜bc def - - h 卜i 深度优先抓取顺序： a 一卜g 一e h 一卜b ( _ d - e 图2 2 广度优先与深度优先算法 由于不可能抓取所有的网页，有些网络蜘蛛对一些不太重要的网站，设置了 访问的层数。例如，在图2 2 中，a 为起始网页，属于0 层，b 、c 、d 、e 、f 属于第l 层，g 、h 属于第2 层，l 属于第3 层。如果网络蜘蛛设置的访问层数 为2 的话，网页i 是不会被访问到的。这也让有些网站上一部分网页能够在搜索 引擎上搜索到，另外一部分不能被搜索到。 另外还有一种i p 段扫描的策略。其基本思想是以某种策略找到一批起始i p 地址。从设定的i p 段开始，按照i p 地址递增的方式搜索后续的每一个i p 地址中 的信息。这种方法可以解决网络蜘蛛对h t m l 文件中指向其他w 曲站点的超链 接地址的过度依赖。能够发现新的孤立资源。但是此策略计算范围巨大，不适合 大规模的搜索，但可以配合其他策略在小范围内全面搜索。 对于网站设计者来说，扁平化的网站结构设计有助于搜索引擎抓取其更多的 网页。网络蜘蛛在搜索引擎中占有重要位置，对搜索引擎的查全、查准都有影响， 决定了搜索引擎数据容量的大小，而且网络蜘蛛的好坏直接影响搜索结果页中的 死链接( 即链接所指向的网页已经不存在) 的个数。目前如何发现更多的网页、 如何正确提取网页内容、如果下载动态网页、如何提供抓取速度、如何识别网站 内容相同的网页等都是网络蜘蛛需要进一步改进的问题。 5 2 1 2 页面分析和建立索引 网络机器人或网络蜘蛛采集的网页，还要有其它程序进行分析，根据一定的 相关度算法进行大量的计算建立网页索引，才能添加到索引数据库中。数据的索 引分为三个步骤：网页内容的提取、词的识别、标引库的建立。互联网上大部分 信息都是以h t m l 格式存在的，对于索引来说，只处理文本信息。因此需要把 网页中文本内容提取出来，过滤掉一些脚本标示符和一些无用的广告信息，同时 记录文本的版面格式信息。词的识别是搜索引擎中非常关键的一部分，具体通过 字典文件对网页内的词进行识别。中文分词一直是中文搜索引擎的关键点，中文 不同英文，英文每个单词是用空格分开，而中文一个句子往往是一些词的连结， 没有分割符，人可以很容易的看懂句子的意思，但是计算机很难看懂。目前中文 分词方法几乎都是有自己的中文词典，分词时去词典匹配，达到分词目的，分词 的好坏，和词典关系很大。由于中文信息没有特定的词组边界，因此从特定文本 里提取有效的关键词就较英文资料困难许多。假如简单地以单个汉字作为信息处 理的基本单元，既缺乏必要的语义表达，又会带来大量的冗余信息。识别出网页 中的每个词，并分配唯一的w o r d i d 号，用于为数据索引中的标引模块服务。标 引库的建立是数据索引中结构最复杂的一部分。一般需要建立两种标引：文档标 引和关键词标引。文档标引分配每个网页一个唯一的d o c i d 号，根据d o c i d 标引 出在这个网页中出现过多少过w o r d l d ，每个w o r d i d 出现的次数、位置、大小写 格式等，形成d o c i d 对应w o r d i d 的数据列表；关键词标引其实是对文档标引的 逆标引，根据w o r d i d 标引出这个词出现在那些网页( 用w o r d l d 表示) ，出现在 每个网页的次数、位置、大小写格式等，形成w o r d i d 对应d o c i d 的列表。大多 数中文搜索引擎的页面处理模块采用字表法( 又称“单汉字标引法”) 对网页的 文档内容进行标引。字表法的标引原理是以单汉字作为标引词，依次读入网页文 档内容中的字，通过禁用字典剔除禁用字；再确定每个非禁用字在文档中的位置， 建立包括文档编号、字符具体位置等标引记录，生成一个临时表单，最后将此表 单提交至数据组织模块处理。另外，也有少数中文搜索引擎采用抽词法标引，这 种方法要求先对网页内容进行分词处理，然后按一定规则从中抽取反映网页内容 的关键词，生成一个以关键词为核心内容的临时表单【6 】。抽词法标引实现起来难 度较大，现有中文搜索引擎较少采用。 6 搜索引擎建立网页索引，处理的对象是文本文件。对于网络蜘蛛来说，抓取 下来网页包括各种格式，包括h t m l 、图片、d o c 、p d f 、多媒体、动态网页及 其它格式等。这些文件抓取下来后，需要把这些文件中的文本信息提取出来。准 确提取这些文档的信息，一方面对搜索引擎的搜索准确性有重要作用，另一方面 对于网络蜘蛛正确跟踪其它链接有一定影响。数据组织模块对页面处理模块提交 的表单数据通常采用倒排文档进行组织。倒排文档以字还是以词作为索引来组织 表单数据，与页面处理模块采用何种标引方法有直接关系：若采用字表法标引， 索引数据库就以字为索引来组织数据；若采用抽词法标引，索引数据库则以关键 词为索引来组织数据。数据组织模块除了对索引数据库进行及时的更新、添加外， 同时还对页面采集模块提交的u r l 删除信息加以处理，以保证索引数据库和它 对应的网页之间的链接可靠。不少大型中文搜索引擎还采用了索引数据库缓存机 制来提高检索的性能，即以用户的高频查询项为索引来组织数据，并将这些数据 置于索引数据库的缓存中，可以大幅加快查询的响应速度且获得较高的匹配成功 率。 2 1 3 数据检索模块的工作原理 搜索的处理过程是对用户的搜索请求进行满足的过程，通过用户输入搜索关 键字，搜索服务器对应关键词字典，把搜索关键词转化为w o r d i d ，然后在标引 库中得到d o c i d 列表，对d o c i d 列表进行扫描和w o r d i d 的匹配，提取满足条件 的网页，然后计算网页和关键词的相关度，根据相关度的数值返回前k 篇结果 ( 不同的搜索引擎每页的搜索结果数不同) 返回给用户。如果用户查看的第二页 或者第多少页，重新进行搜索，把排序结果中在第k + l 到2 木k 的网页组织返回 给用户。其处理流如图2 3 ： 7 图2 3 数据检索模块的工作原理 数据检索模块首先将用户输入的查询项转化成计算机可执行的规范化检索 式，再按一定的检索策略先后在索引数据库的缓存、索引数据库中进行匹配，如 果仍然没有匹配成功，有的中文搜索引擎还会将用户查询项交给第三方搜索引擎 处理或者检索第三方索引数据库，最后将检索到的结果按定的排序策略进行组 织并返回给用户。中文搜索引擎的检索策略在很大程度上受搜索引擎的页面处理 方法影响。采用字表法标引页面的中文搜索引擎【9 1 ，检索时采用全文检索方式； 采用抽词法标引页面的中文搜索引擎，检索时采用主题检索方式，其关键词一般 能比较准确地反映文档的主题。不同的中文搜索引擎对检索结果的排序策略多不 荤 相同，这使得同一个查询项应用不同的中文搜索引擎返回的查询结果排序差异非 常明显。互联网虽然只有一个，但各搜索引擎的能力和偏好不同，所以抓取的网 页各不相同，排序算法也各不相同。大型搜索引擎的数据库储存了互联网上几亿 至几十亿的网页索引，数据量达到几千g 甚至几万g 【3 1 。但即使最大的搜索引擎 建立超过二十亿网页的索引数据库，也只能占到互联网上普通网页的不到3 0 ， 不同搜索引擎之间的网页数据重叠率一般在7 0 以下。我们使用不同搜索引擎的 重要原因，就是因为它们能分别搜索到不同的内容。而互联网上有更大量的内容， 是搜索引擎无法抓取索引的，也是我们无法用搜索引擎搜索到的。应该有这个概 念：搜索引擎只能搜到它网页索引数据库里储存的内容。 2 2 开源全文检索系统iu c e n e l u c e i l e 是a p a c h e 软件基金会j a k a r t a 项目组的一个子项目，是一个开放源代 码的全文检索引擎工具包，即它不是一个完整的全文检索引擎，而是一个全文检 索引擎的架构，提供了完整的查询引擎和索引引擎，部分文本分析引擎( 英文与 德文两种西方语言) 。l u c e l l e 的目的是为软件开发人员提供一个简单易用的工具 包，以方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起完整 的全文检索引擎。l u c e n e 的原作者是d o u gc u t t i n g ，他是一位资深全文索引检 索专家，曾经是v - t w i n 搜索引擎的主要开发者，后在e x c i t e 担任高级系统架构 设计师，目前从事于一些i n t e n l e t 底层架构的研究 全文检索是指计算机索引程序通过扫描文章中的每一个词，对每个词建立一 个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据 事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程类 似于通过字典中的检索字表查字的过程。 全文检索的方法主要分为按字检索和按词检索两种。按字检索是指对于文章 中的每一个字都建立索引，检索时将词分解为字的组合。对于各种不同的语言而 言，字有不同的含义，比如英文中字与词实际上是合一的，而中文中字与词有很 大分别。按词检索指对文章中的词，即语义单位建立索引，检索时按词检索，并 且可以处理同义项等。英文等西方文字由于按照空白切分词，因此实现上与按字 处理类似，添加同义处理也很容易。中文等东方文字则需要切分字词，以达到按 9 词索引的目的，关于这方面的问题，是当前全文检索技术尤其是中文全文检索技 术中的难点，在此不做详述。 全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软 件系统。一般来浼，全文检索需要具备建立索引和提供查询的基本功能，此外现 代的全文检索系统还需要具有方便的用户接口、面向w w w 的开发接口、二次 应用开发接口等等。功能上，全文检索系统核心具有建立索引、处理查询返回结 果集、增加索引、优化索引结构等等功能，外围则由各种不同应用具有的功能组 成。结构上，全文检索系统核心具有索引引擎、查询引擎、文本分析引擎、对外 接口等等，加上各种外围应用系统等等共同构成了全文检索系统。图2 4 展示了 上述全文检索系统的结构与功能。 图2 4 全文检索系统结构 l u c e n e 作为一个全文检索引擎，其具有如下突出的优点： ( 1 ) 索引文件格式独立于应用平台。l u c e n e 定义了一套以8 位字节为基础 的索引文件格式，使得兼容系统或者不同平台的应用能够共享建立的索引文件。 ( 2 ) 在传统全文检索引擎的倒排索引的基础上，实现了分块索引，能够针 对新的文件建立小文件索引，提升索引速度。然后通过与原有索引的合并，达到 优化的目的。 1 0 ( 3 ) 优秀的面向对象的系统架构，使得对于l u c 锄e 扩展的学习难度降低， 方便扩充新功能。 ( 4 ) 设计了独立于语言和文件格式的文本分析接口，索引器通过接受t o k e i l 流完成索引文件的创立，用户扩展新的语言和文件格式，只需要实现文本分析的 接口。 ( 5 ) 已经默认实现了一套强大的查询引擎，用户无需自己编写代码即使系 统可获得强大的查询能力，l u c e i l e 的查询实现中默认实现了布尔操作、模糊查 询、分组查询等等。 面对已经存在的商业全文检索引擎，l u c e n e 也具有相当的优势。首先，它 的开发源代码发行方式( 遵守a - p a c h es o 胁a r el i c e i l s e ) ，在此基础上程序员不仅 仅可以充分的利用l u c e l l e 所提供的强大功能，而且可以深入细致的学习到全文 检索引擎制作技术和面相对象编程的实践，进而在此基础上根据应用的实际情况 编写出更好的更适合当前应用的全文检索引擎。在这一点上，商业软件的灵活性 远远不及l u c e l l e 。其次，l u c e n e 秉承了开放源代码一贯的架构优良的优势，设 计了一个合理而极具扩充能力的面向对象架构，程序员可以在l u c e i l e 的基础上 扩充各种功能，比如扩充中文处理能力，从文本扩充到h 1 m l 、p d f 等等文本 格式的处理，编写这些扩展的功能不仅仅不复杂，而且由于l u c e i l e 恰当合理的 对系统设备做了程序上的抽象，扩展的功能也能轻易的达到跨平台的能力1 9 】。 第3 章搜索引擎的相关算法研究 本章研究了通用搜索爬行算法的主题相关度算法，在分析总结基于关键词算 法与基于概念的算法之上，研究了使用链接分析改进主题爬虫策略的方法。并分 析了分词算法的最大匹配算法，设计了正向最细粒度最长算法。 3 1 网络蜘蛛爬行算法 通用搜索引擎的网络爬虫从一个或若干初始网页的u r l 开始，获得初始网 页上的u r l 在抓取网页的过程中，不断从当前页面上抓取新的u r l 放人队列， 直到满足系统的一定停止条件。搜索引擎保留有用的链接并将其放人等待抓取的 u r l 队列。然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页 u u ，并重复上述过程，直到达到系统的某一条件时停止。如图3 1 所示。 图3 一l 网络爬虫流程图 主题爬虫最初的设计思想是考虑对所爬取内容的过滤，区别于普通爬虫对所 有页面的链接进行采集处理，而是先对所爬去内容与主题领域的匹配相关度进行 处理，只有当其主题相关度符合一定标准时才处理该页面中的链接，因为如果该 页面和本领域比较相关，它所包含的链接和领域相关的几率也较大，这样提高了 1 2 爬行精度，虽然会出现一定错误率，但综合比较爬行速度与数据冗余的效果是令 人满意的。因此，主题相关度的分析是主题爬虫设计的关键，最简单的可以基于 关键词进行分析，更复杂的可以上升到语义和概念的相关算法处理。第一阶段基 于关键词的主题相关度分析的主题爬虫设计取得了较好的效果，其主要思路是： 首先在领域专家的参与下，确定一组带有权重的能够代表受限领域的关键词，用 它表示确定的主题；然后对页面进行特征词提取，采用向量空间模型算法计算网 页的主题相关度，然后根据事先确定的阈值决定是否采集数据【1 6 】。 3 1 1 基于特征词的算法 在基于特征词的方案中，把特征词的个数n 作为向量空间的维数，每个特征 词的权重w i 作为每一维分量的大小，则主题用向量表示为： q = ( a i ，a 2 。，a n ) ，i = l ，2 ，n ，a i = w i 对页面进行分析，统计特征词出现频率，求出频率之比，以出现频率最高的特 征词为基准，其频率用x 产1 表示通过频率比，求出其他特征词的频率妇，则该 页面对应向量的每一维分量为x i w i ，页面主题用向量表示为： b = ( x l w l ，x 2 w 2 ，x n 、) ，i = 1 ，2 ，n 用两个向量夹角的余弦表示页面的主题相关度： c o s = ( q ，b ) l qi lbl = 石1w f + z 2w ；+ + 吒w 二 i 两厣石石了丽 指定一个阂值r ，当c o “a ，b 大于r 时就可以认为该页面和主题是比较相关 的r 的取值根据经验和实际要求确定。如果想获得较多的页面，可以把r 设小一点， 要获得较少的页面，可以把r 设得大点。 3 1 2 基于概念的算法 在基于概念的方案中，由于“知网 ( 英文名称为h o w n e t ) 能够为汉语语义处 理提供个比较全面的语义知识库，可以此作为基于概念的主题相关度分析的概 念网络。所有的特征词t 形成特征词集合t = ( t l ，t 2 ，t n ) ，设特征词t i 有a i ( a i 1 3 1 ) 个概念义，记c ( f ，) = ( f ? ，f ；，c ) ，从特征词集合t 转化扩充得到特征 词概念集合c t ，其元素为每个特征词的每个概念义，令纪( ，c ；) ，其中j = 1 ， 2 ，a i ，t c ：表示第i 个特征词的第j 个概念义，则有c t = ( ，c f ) ，( 乞，彳) ，( f l ， 午) ，( ，t ) ，( 乙，靠) ) = ( 叫，砭，硝，碟， 砰) 。考虑一词多义，删除其他完全相同的概念，将集合c t 变为概念集合c ， 设由m 个概念组成，记为c = ( c i ，c 2 ，c i l l ) 。把概念的个数m 为向量的 维数， 每个概念的权重w i ( 该概念对于主题的贡献度) 作为每一维分量的大小， 得到主题的新的向量表示q 。然后，与基于特征词的方案对应，对页面进行概 念提取，在概念集合c 上页面d 的特征向量为v c ( d ) = ( c i ，屹；c m ， w 硎( d ) ) ，其中心( d ) 为概念c i 在页面d 中的权重，最终得到新的页面主题向量表 示b 。最后，计算c o s ，并将它和指定的阈值进行比较，来判断页面 的主题相关度，决定页面的取舍【r n 。 3 2 使用预取链接改进爬行策略 以上两个基于特征词和基于概念的方案均能获得很好的爬行效果，两者都是 基于向量空间模型的算法，现有的程序验证了用向量空问模型算法进行主题相关 度计算的可行性和有效性。但是如果想进一步提高爬行效率与爬行精度，单纯使 用一种算法算法可能不会取得很好的效果。可以采用辅助的方法。上述基于概念 的算法和基于特征词的算法主要考虑的是过滤网页，而面向主题领域的网络爬虫 不需要爬行不相关的页面。但事实上存在这样一种情况，在一个页面中可能会有 很多不相关的超链接，如果能过滤出不相关的链接，理论上讲爬虫的爬行效率可 以继续提高。从网路爬虫的基本爬行原理可知，爬虫工作的爬行方向就是网页间 的链接，所以链接的关键词尤为重要，例如 招聘工程师 ，锚点内的内容与锚点的t i t l e 属性就是很重要的特征信息，如果能够充分分 析利用链接信息，应该能够改进爬虫的爬行效果。 w 曲上的信息有一定的结构，这既包括由u r l 目录层次反映出来的物理结 构，也包括页面和页面问链接构成的逻辑结构。可以通过分析w 曲站点信息结构， 1 4 初步判断信息的类别，作为预测采集的结构基础。 一个完整的u r l 包括协议和路径两个部分。在w 如站点中使用的大多数是 h r r p 协议，其u r l 语法形式如下： h t t p ： ： ? 其中 表示站点主 机名( 域名或i p 地址) ； 表示端口号； 表示页面的路径； 表示c g l 接口g e t 方法的参数表达式。对于一个站点来说，能够用来 表示站点结构的只有 部分。页面的路径和w 曲站点的文件系统是对应的， 也是一种分层的树型结构，每个层之间通过“”分开。一个设计比较规范的站 点，内容的组织都是按照一定的栏目结构排放的，每个栏目包括某个主题的内容。 一个站点设置若干个栏目，内容较多的栏目则设置子栏目，每个栏目或者子栏目 的文件分目录进行存放。这样，站点物理结构相同的页面就属于同一栏目，它们 有相同或相似的主题，可以利用站点的物理结构来进行信息的采集f 1 6 1 。 站点物理结构反映的是页面的是何种的文本结构，w e b 页面内容之间的主要 联系是通过页面间的链接来进行的。如图3 2 所示： 水平链揍 图3 2 链接类型 页面之间的链接主要包括以下5 种类型： d o w n w a r d 下行链接，目标页面是当前页面的下级页面。 u p w a r d 上行链接，目标页面是当前页面的上级页面。 h o r i z o n t a l 水平链接，目标页面和当前页面处于同一目录。 c r o s s w i s e - 一交叉链接，目标页面和当前页面不在同一路径上。 o 咖a r d 外向链接，目标页面和当前页面不在同一站点。 1 5 通常情况下，下行链的目标页面是对当前页面的详细描述，上行链的目标页 面是对当前页面的概括，水平链的目标页面和当前页面属于同一领域内容，交叉 链和外向链主要表示和锚点信息指向内容相关。： 首先，研究一下基于特征向量和基于概念的两个方案所存在的缺陷，无论是 基于特征词的方案还是基于概念的方案，在分析完页面的主题相关度分析后，将 其主题相关度符合要求的页面将处理其所有链接，这样会导致大量不相关的数据 被分析处理，即数据冗余度较高。因为即使页面本身和主题很相关， 但其中的 链接指向的页面也很有可能指向了不相关站点，如果不加控制取回所有页面并分 进行处理，可能会增加系统的工作量和数据库的数据，并能影响爬虫的总体工作 效率。 但是如果能够对主题相关的页面内的链接进行一次分析，去除那些主题不相 关的链接，在后续爬虫工作中就不必采集分析这些链接指向的页面，因而可以大 大节省时间，因为相比对链接的分析，主题相关度分析耗时更多。上述链接分析 理论可以用于链接过滤，通过链接分析可以把页面中的链接分成五种不同的类 型，对于不同类型链接采取不同的处理。水平链的两页面属于同一内容，下行链 的目标页面是对当前页面的详细描述，对于水平链和下行链的目标页面应该取 回；上行链的目标页面是对当前页面的概括，从统计的角度看，并非所有的目标 页面和主题相关，对于上行链的处理以一定的概率去取页面，取中间值o 5 较合 适。 对下行链接的处理方法：因为一般的下行链接都是对本页面的一个深层论 述。所以对下行链接我们采用全部爬行的策略。 对水平链接的处理方法：水平链接一般是平行的内容很可能有不相关的主 题。所以对水平链接的处理方法分为两步处理。第一步，先分析超链接的文本内 容，以及超链接内t i t l e 属性，超链接前后2 0 字的内容。如果确定有主题相关则进 行第二步，分析水平链接所指向的页面。 对交叉链接的处理方法：交叉链接的主题相关度一般较低。所以只分析链接 的内容。如果相关则进行下一步，不想关则放弃。 对外向链接的处理方法：对外向连接的处理方法如交叉链接的处理方法。 所以对不同链接的分析结果决定是否对目标页面采取进一步处理，提高了爬 1 6 虫的爬行效率。修改后的算法描述如下： ( 1 ) 主题的特征词或概念表示。对选定的主题，从特征词或者概念的层次 用向量将其形式化。 ( 2 ) 特征词或概念提取。从特征词或概念层次分析页面，得到它的向量表 示。 ( 3 ) 计算相关度。计算上述两个向量夹角的余弦。 ( 4 ) 相关度分析。根据预先设定的阈值进行分析，决定页面取舍。 ( 5 ) 对于相关度符合要求的页面进行链接分析，对页面中的链接进行过滤。 3 3 中文分词技术 分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。中文分 词是网页分析索引的基础。在网页分析的过程中，中文与英文的处理方式是不同 的，这是因为中文信息与英文信息有一个明显的差别：英文单词之间有空格，而 中文文本中词与词之间没有分割符。这就要求在对中文网页进行分析之前，先要 将网页中的句子切割成一个个的词的序列，这就是中文分词。中文分词涉及到许 多自然语言处理技术和评价标准，在搜索引擎中，我们主要关心中文自动分词的 速度和准确度。分词准确性对搜索引擎来沈十分重要，但如果分词速度太慢，即 使准确性再高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿 计的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因 此，搜索引擎对分词的准确性和速度都提出了很高的要求【l l 】。 3 3 1 中文分词算法 中文分词技术属于自然语言处理技术范畴，其处理过程就是分词算法。现有 的分词算法可分为三大类基于字符串匹配的分词方法、基于理解的分词方法和基 于统计的分词方法。 基于字符串匹配的分词方法： 这种方法又被称为机械分词方法，它是按照一定的策略将待切分的汉字串与 分词词典中的词条进行匹配查询，若在词典中找到某个字符串，则匹配成功，即 识别出一个词。按照扫描方向的不同，串匹配分词方法可以分为j 下向匹配和逆向 1 7 匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹 配：按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相 结合的一体化方法。常用的几种机械分词方法如：正向最大匹配法：方向由左到 右；逆向最大匹配法：方向由右到左；最少切分：使每一句中切出的词数最小还 可以将上述各种方法相互组合，例如邹海山等在现有分词技术的基础上，提出了 一种基于词典的正向最大匹配和逆向最大匹配相结合的中文分次方案【l2 1 ，可以 高效、准确地实现中文文档的主题词条的抽取和词频统计可以将正向最大匹配方 法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正 向最小匹配和逆向最小匹配一般很少使用。般浼来，逆向匹配的切分精度略高 于正向匹配，遇到的歧义现象也较少。还有一种方法是改进扫描方式，称为特征 扫描或标志切分，优先在待分析的字符串中识别和切分出一些带有明显特征的 词，以这些词作为断点，可将原字符串分为几个较短的子串再进行机械分词，从 而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词 类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、 调整，从而极大地提高切分的准确率。 3 3 2 基于统计的分词 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的 次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好 的反映为词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计， 计算它们的互现信息。定义两个字的互现信息，计算两个汉字x ，y 的相邻共现 概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个闭 值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进 行统计，不需要切分词典，因而又