全文搜索引擎技术的研究和实现

全文搜索引擎技术的研究和实现内容摘要：

3。 45 1 全文搜索引擎技术的研究和实现 摘要： 随着互联网（ Inter）的出现和普及，人们的信息来源得到极大的丰富，获取信息的方式也随之改变。 换句话说，互联网成为人们获取信息的主要来源之一。 在 Web信息以几何级数增长的情况下，如何快速获取所需信息成为研究热点之一。 本文介绍了一个基于 Linux平台下 C++的 可索引百万级网页原文 的全文搜索引擎的设计及其实现， 并对该搜索引擎的基 本框架设计和主要功能模块的实现作了详细介绍， 其中包括 通过信号量和互斥锁达到同步的 多线程并行网页爬虫， 采用 正向窗口最大匹配分词 算法 ，网页原文采用天网格式的数据存储，核心数据结构包括 ISAM顺序索引文件， 正向索引文件， 倒排索引文件等， 最后给出了相应的测试 结果。 关键词 ： 多线程 网页 爬虫；线程同步；顺序、倒排索引； 全文搜索引擎 Full Text Search Engine Abstract： With the inventation and popularization of the Inter， it has been kinds of source of news and the way access to information also has been a great other words， Inter has bee one of the main means which people obtain the Web information grows in a geometric progression， how to obtain the required information fast bees one of hot spot of researches. This paper introduces a Linux platform based on C++ of one million web pages indexed the full text of the original search engine design and its implementation, and the search engine design and the basic framework for the realization of the main functional modules described in detail, including through the signal Mutex and achieve synchronization in parallel multithreaded page reptiles, the use of the window are the largest subword matching algorithms, the original web page format using Tianwang data storage, data structures, including the core sequence ISAM index file, index files, inverted index file。 Finally， it educes the corresponding test results. Keywords： Multithreaded page crawler； Thread Synchronization； Order、 inverted index； Full text search engine 2 第一章 绪论 早在工业时代以前 ， 许多专家 、 学者就开始致力于信息整序的研究，并积累了丰富的经验。 进入信息时代以后，人们加深了对信息资源的认识，把信息资源的重要性提升到前所未有的高度，将之与物质和能源相 提并论，称之为现代社会的三大支柱之一。 国际互联网的诞生和发展，给信息资源的建设提供了一个无限的空间。 网上信息资源的迅速增长，为信息的开发与利用提供了便利条件。 然而，网络信息微观上的有序性和宏观上的分散性、无序性、动态变化性给人们在搜集与利用信息时带来了种种障碍。 为了能从网络上找到用户所需要的特定信息，为了更加有效的开发利用互联网上的数字金矿，搜索引擎应运而生了。 论文的研究背景 伴随着万维网的普及和发展 ， 因特网上的信息资源正在呈几何级数增长 ， 据统计 09年 4月 服务器主机数 已经 超过 2亿 个 [1]， 如图 11所示。 图 11 世界 Web 服务器总量 [1] Total Sites Across All Domains August 1995 April 2020 [1] 根据 2020 年的一个研究， 在互联网上已 超过 5500 亿个 网页 文档 [2]。 2020 年 7月25日谷歌软件工程师 Jesse Alpert和 Nissan Hajaj宣布谷歌搜索引擎已经索引了万亿 3 级的不同 URL 地址 [2]。 中国网页规模如图 12所示。 图 12 20202020年中国网页 规模变化 [3] 20202020 Chinese web page size changes[3] 截至 2020 年底，中国网页总数超过 160 亿个，较 2020 年增长 90%[3]。 网页的增长速度与网站的增速基本一致。 如上所述 万维网 给人们带来极其丰富的信息 ， 同时也向人们提出了新的问题 ，即如何从浩如烟海的信息资源中迅速有效地检索出人们所需要的信息。 Web 搜索引擎就是为满足人们 的这种需要而诞生的。 搜索引擎是一种在互联网上采取一定的策略搜集 、 发现信息 ， 并对信息进行分析 、 提取 、 组织和处理 ， 为用户提供 检索服务的搜索工具。 本论文针对 Web全文搜索引擎 技术 进行研究和实现。 论文研究目的和意义 全球最大的网络调查公司 CyberAtlas 最近的一项调查表明 ， 网站 75%的访问量都来自于搜索引擎。 另一家美国权威顾问公司 IMT Strategies 调查发现，新网站的有效途径中：搜索引擎占 85%；自由冲浪占 6%；口碑宣传占 4%； BANNER 广告 2%； 偶然发现、报纸、电视各占 1%。 由此可见，搜索引擎 不仅仅作为用户快速检索互联网上的浩瀚资源的工具，同时 作为网站推广的首选媒介， 对 互联网 有着不可忽视 的 作用。 本论 文在 相关 商业 全文 搜索引擎 公开的 技术原理 和开源全文搜索引擎技术原理 的 4 基础上，对 全文搜索引擎 技术 研究并实现。 整个过程 会设计 并实现 一个 百万级网页规模的全文搜索引擎 ，来满足 普通 用户对 浩瀚 信息资源的检索需要。 研究现状 1990 年以前，没有任何人能搜索互联网。 1990 年诞生的 Archie 是一个可以用文件名自动索引互联网上匿名 FTP网站文件的程序，它实现了搜索，但还不是真正的搜索引擎。 现代意义上的搜索引擎出现于 1994 年 7 月 ， 当时 Michael Mauldin 将 JohnLeavitt的蜘蛛程序接入到其索引 程序中 ， 创建了大家现在熟知的 Lycosa。 1995 年末 ， Altavista 永远改变了搜索引擎的定义 ， AItavista 是第一个支持自然语言搜索的搜索引擎，也是第一个实现高级搜索语法的搜索引擎。 1998 年 ， Google 在 Pagerank、动态摘要、网页快照、 DailyRefresh、多文档格式支持、地图 、 股票 、 词典 、 寻人等集成搜索、多语言支持、用户界面等功能上的革新，象 Altavista 一样，再一次永远改变了搜索引擎的定义。 现阶段，出现 Ask Jeeves， ， ， MySimon， Dito 等内容类别不同的搜索引擎。 从出现第一个搜索引擎至今 ， 搜索引擎技术已获得了飞速的发展，现在的搜索引擎功能越来越强大，提供的服务也越来越全面，它们的目标不仅仅是提供单纯的查询功能，而是把自己发展成为用户首选的 Inter 入口站点。 目前的搜索引擎主要有以下几个主要特点 ： 多样化和个性化的服务。 现在绝大多数搜索引擎都提供多样化的服务，以吸引更多的用户，商业搜索引擎尤其注重这一点 ； 强大的查询功能与最早的搜索引擎相比，现在的搜索引擎在查询功能方面已有了很大的改进。 除了简单的 AND、 OR和 NOT 逻辑外，不少搜 索引擎还支持相似查询 ； 目录和基于 Robot 的搜索引擎相互结合目录和基于 Robot 的搜索引擎都具有自己的特点，在当前的技术条件下，最好的选择是将两种技术进行结合，同时为用户提供这两种类型的服务。 这些 搜索引擎基本工作原理是 ： 数据采集机制按照一定规律和方式对网络上的各种信息资源进行搜索，并将搜索到的页面信息存入到一个临时数据库中；数据分类索引机制对临时数据库中的页面信息进行索引 ， 经过整理形成各种倒排文档 ， 相应地建立起索引数据库；用户查询接口则提供友好的查询界面，接受用户提交的查询任务 ， 并根据要求访问相应的索引数 据库，将符合要求的结果按一定规则排序输出。 5 论文的研究内容 本文的研究内容主要包括以下 三 点： 互联网上 全文搜索引擎技术 面临的 挑战 ， 整体结构 的分析 以及相关技术的 研究 ，其中分为分布式处理，中文分词，网页排序，海量存储，压缩 等技术 的 介绍 ； 本论文 设计出 的 全文搜索引擎整体系统架构， 各 模块 的 交互 和 设计 ； 实现，最终完成一个可以对校内网站进行全文检索的搜索引擎，该全文搜索引擎主要分为以下三部分： 网页爬虫。 存储与索引 表 ，天网格式的网页数据原文存储格式，顺序索引表，倒排索引表 ， 相关性分析 ， 查询服务系统。 论文的组织结构 本论文共分 五 章，具体结构如下： 第一章 概述本文的研究背景和 研究意义以及国内外的研究现状，在此基础上提出本文研究的主要内容。 第二章 对 互联网上 的 全文搜索引擎 技术的 分析 和研究。 第三章 对本论文设计出的全文 搜索引擎 系统 的架构分析 ，结构分析 和 交互 设计 等。 第四章 对 整个 系统 各个部分模块的具体编码 实现与 关键技术 研究。 第五章 全文总结， 以及 对 本论文设计出的 全文搜索引擎的 创新 点 与展望 的说明。 6 图 13 论文结构 Thesis structure 小结 通过对互联网上网页数的调查，以及出现全文搜索引擎的背景和其研究的现状，最终提出了本论文研究的内容和论文的布局结构。 第一章 绪论 第二章 全文搜索引擎技术分析 第三章 本论文所设计的全文搜索引擎技术分析 第四章 本论文所设计的全文搜索引擎编码实现与关键技术研究 第五章 总结与展望 7 第二章 搜索引擎 相关 技术 分析 著名的搜索引擎 搜索引擎自 1993 年出现发展至今 ， 已取得了长足的进步 ， 信息检索工具搜索引擎也是层出不穷 ， 以下是与搜索引擎发展历史息息相关的几个搜索引擎 ： (1)Fast(All the web)公司创立于 1997 年 ， 是挪威科技大学 (NTNU)学术研究的副产品。 1999 年 5 月 ， 它发布了自己的搜索引擎 All The Web。 Fast 创立的目标是做世界上最大和最快的搜索引擎 ， 几年来庶几近之。 Fast(All the web)的网页搜索可利用 ODP 自动分类 ， 支持 Flash 和 Pdf 搜索 ， 支持多语言搜索 ，还提供新闻搜索、 图像搜索、视频、 MP3和 FTP 搜索 ， 拥有极其强大的高级搜索功能。 (2)Teoma 起源于 1998 年 Rutgers 大学的一个项目。 Apostolos Gerasoulis教授带领华裔 Tao Yang 教授等人创立 Teoma 于新泽西 Piscataway， 2020 年春初次登场 ， 2020 年 9 月被提问式搜索引擎 Ask Jeeves 收购 ， 2020 年 4月再次发布。 Teoma 的数据库目前仍偏小 ， 但有两个出彩的功能 ： 支持类似自动分类的 Refine； 同时提供专业链接目录的 Resources。 (3)Wisenut 由韩裔 Yeogirl Yun 创立。 2020 年春季发布 Beta 版 ， 2020 年 9月 5 日发布正式版 ， 2020 年 4月被分类目录提供商 looksmart 收购。 Wisenut 也有两个出彩的功能 ： 包含类似自动分类和相关检索词的 WiseGuide； 预览搜索结果的 SneakaPeek。 (4)Gigablast 由前 Infoseek 工程师 Matt Wells 创立 ， 2020 年 3 月展示 prebeta 版 ， 2020 年 7月 21 日发布 Beta 版。 Gigablast 的数据库目前仍偏小 ，但也提供网页快照 ， 一个特色功能是即时索引网页 ， 你的网页刚提交它就能搜索(注 ： 这个 spammers 的肉包子功能暂已关闭 )。 (5)Openfind 创立于 1998 年 1月 ， 其技术源自台湾中正大学吴升教授所领导的 GAIS 实验室。 Openfind 起先只做中文搜索引擎 ， 曾经是最好的中文搜索引擎 ， 鼎盛时期同时为三大著名门户新浪 、 奇摩 、 雅虎提供中文搜索引擎 ， 但 2000 年后市场逐 渐被 Baidu 和 Google 瓜分。 2020 年 6月 ， Openfind 重新发布基 8 于 GAIS30 Project的 Open2find搜索引擎 Beta版 ， 推出多元排序 (PolyRankTM)，宣布累计抓取网页 35亿 ， 开始进入英文搜索领域 ， 此后技术升级明显加快。 (6)北大天网是国家“九五”重点科技攻关项目“中文编码和分布式中英文信息发现”的研究成果 ， 由北大计算机系网络与分布式系统研究室开发 ， 于 1997年 10 月 29 日正式在 CERNET 上提供服务。 2020 年初成立天网搜索引擎新课题组 ， 由国家 973 重点基础研究发展规划项 目基金资助开发 ， 收录网页约 6000 万 ，利用教育网优势 ， 有强大的 FTP 搜索功能。 (7)2020 年 1 月 ， 两位北大校友 、 超链分析专利发明人 、 前 Infoseek 资深工程师李彦宏与好友徐勇 (加州伯克利分校博士 )在北京中关村创立了百度 (Baidu)公司。 2020 年 8 月发布 搜索引擎 Beta 版 (此前 Baidu 只为其它门户网站搜狐新浪 Tom 等提供搜索引擎 )， 2020 年 10 月 22 日正式发布 Baidu 搜索引擎 ， 专注于中文搜索。 Baidu 搜索引擎的其它特色包括 ： 网页快照 、 网页预览/预览全部网页 、 相关搜索词 、 错别 字纠正提示 、 新闻搜索 、 Flash 搜索 、 信息快递搜索。 2020 年 3月闪电计划 (BlitzenProject)开始后 ， 技术升级明显加快。 (8)Northernlight 公司于 1995 年 9 月成立于马萨诸塞州剑桥 ， 1997 年 8月Northernlight 搜索引擎正式现身。 它曾是拥有最大数据库的搜索引擎之一 ， 它没有 StopWords， 它有出色的 CurrentNews、 7100 多出版物组成的 Special Collection、 良好的高级搜索语法 ， 第一个支持对搜索结果进行简单的自动分类 (注 ：2020 年 1 月 16 日 ， Northernlight 公共搜索引擎关闭 ， 随后被 divine 收购 ， 但在 Nlresearch， 选中“ World Wide Web only” ， 仍可使用 Northernlight 搜索引擎 )。 (9)1995 年 9 月 26 日 ， 加州伯克利分校 CS 助教 EricBrewer、 博士生 PaulGauthier 创立了 Inktomi(UCBerkeleyAnnouncesInktomi)， 1996 年 5月 20 日 ， Inktomi 公司成立 ， 强大的 HotBot 出现在世人面前。 声称每天能抓取索引 1千万页以上 ， 所以有远超过其它搜索引擎的新内容。 HotBot 也大量运用 cookie 储存用户的个人搜索喜好设置 (注 ： Hotbot 曾是随后几年最受欢迎的搜索引擎之一 ，后被 Lycos 收购 )。 (10)Google 在 1998 年 10月之前 ， 只是 Stanford 大学的一个小项目 BackRub。 1995 年博士生 Larry Page 开始学习搜索引擎设计 ， 于 1997 年 9 月 15 日注 9 册了 的域名 ， 1997 年底 ， 在 Sergey Brin 和 Scott Hassan， Alan Steremberg 的共同参与下 ， BachRub 开始提供 Demo。 1999 年 2月 ， Google 完成了从 Alpha 版到 Beta 版的蜕变。 Google 公司则把 1998 年 9 月 27 日认作自己的生日。 Google 在 Pagerank、 动态摘要 、 网页快照 、 DailyRe2fresh、 多文档格式支持 、 地图股票词典寻人等集成搜索 、 多语言支持 、 用户界面等功能上的革新 ，象 Altavista 一样 ， 再一次永远改变了搜索引擎的定义。 在 2020 年中以前 ， Google 虽然以搜索准确性备受赞誉 ， 但因为数据库不如其它搜索引擎大 ， 缺乏高级搜索语法 ， 所以推广并不快。 直到 2020 年中数据库升级后 ， 又借被 Yahoo 选作搜索引擎的东风 ， 才一飞冲天。 搜索引擎存在的问题以及挑战 搜索引擎在飞速发展的同时也存在着很多缺陷 ， 需要进一步改进和完善 ， 笔者对这些问题进行了归纳 ， 如下 ： (1)网络信息质量控制欠缺。 任何人只要具备相应的条件就可以把任何信息送到网上 ， 800C 这些信息不经任何质量控制就被搜索引擎标引 ， 未经质量控制的信息必然会影响搜索结果的质量。 (2)大量占用昂贵的网络带宽和 CPU资源。 由于搜索引擎必须将大量资源站点的内容传送至搜索站点本地 ， 然后进行分析索引 ， 这样大规模的资源文件的传送和出路无疑会。