搜索引擎的设计与实现

webweb 搜索引擎的设计与实现搜索引擎的设计与实现 摘 要 随着网络的迅猛发展 网络成为信息的极其重要的来源地 越来越多的人 从网络上获取自己所需要的信息 这就使得像 Google 40 百度 39 这样的通用 搜索引擎变成了人们寻找信息必不可少的工具 本文在深入研究了通用搜索引擎基本原理 架构设计和核心技术的基础上 结合小型搜索引擎的需求 参照了天网 lucene 等搜索引擎的原理 构建了一 个运行稳定 性能良好而且可扩充的小型搜索引擎系统 本文不仅仅完成了对 整个系统的设计 并且完成了所有的编码工作 本文论述了搜索引擎的开发背景以及搜索引擎的历史和发展趋势 分析了 小型搜索引擎的需求 对系统开发中的一些问题 都给出了解决方案 并对方 案进行详细设计 编码实现 论文的主要工作及创新如下 1 在深刻理解网络爬虫的工作原理的基础上 使用数据库的来实现爬虫部 分 2 在深刻理解了中文切词原理的基础之上 对 lucene 的切词算法上做出了 改进的基础上设计了自己的算法 对改进后的算法实现 并进行了准确率和效 率的测试 证明在效率上确实提高 3 在理解了排序索引部分的原理之后 设计了实现索引排序部分结构 完 成了详细流程图和编码实现 对完成的代码进行测试 4 在完成搜索部分设计后 觉得效率上还不能够达到系统的要求 于是为 了提高系统的搜索效率 采用了缓存搜索页面和对搜索频率较高词语结果缓存 的两级缓存原则来提高系统搜索效率 关键词 关键词 搜索引擎 网络爬虫 中文切词 排序索引 ABSTRACT With the rapidly developing of the network Network became a vital information source more and more people are obtaining the information that they need from the network this making web search engine has become essential tool to people when they want to find some information from internet In this paper with in depth study of the basic principles of general search engines the design and core technology architecture combining with the needs of small search engine and in the light of the tianwang lucene search engine I build a stable good performance and can be expanded small scale search engine system this article not only completed the design of the entire system but also basically completed all the coding work This article describle not only the background of search engines but also the history of search engine developing and developing trends and analyse the needs of small search engines and giving solutionsthe to the problems which was found in the development of the system and making a detailed program design coding to achieve The main thesis of the article and innovation are as follows 1 with the deep understanding of the working principle of the network spider I acheived network spider with using database system 2 with the deep understanding of Chinese segmentation and segmentation algorithm of lucene system I made my own segmentation algorithm and give a lot of tests to my segmentation algorithm to provide that my segmentation algorithm is better 3 with the deep understanding of sorted and index algorithm I designed my own sorted and index algorithm with the data struct I designed and coding it it was provided available after lots of tests 4 after design of search part I foud the efficiency of the part is not very poor so I designed two stage cache device to impove the efficiency of the system Key words search engine net spider Chinese segmentation sorted and index 目录目录 第一章 绪论 1 1 1 搜索引擎出现的背景及意义 1 1 2 搜索引擎的发展历史及趋势 1 1 3 本文主要工作 3 1 4 论文结构 4 第二章 系统结构 5 2 1 概述 5 2 2 系统结构 5 2 2 1 爬虫 6 2 2 2 信息处理 6 2 2 3 排序和索引 6 2 2 4 搜索 6 2 3 搜索引擎主要指标及分析 6 2 4 开发语言 7 2 5 小结 8 第三章 爬虫 9 3 1 概述 9 3 2 爬虫结构分析 9 3 2 1 爬虫初始化 10 3 2 2 从网页中提取 url 11 3 2 3 URL 存储 12 3 2 4 从数据库中提取 url 12 3 3 小结 13 第四章 信息处理 14 4 1 概述 14 4 2 转换 15 4 3 切词 18 4 3 1 中文切词 19 4 3 2 中文切词测试 25 4 3 3 英文切词 27 4 3 4 数字切词 28 4 3 5 符号处理 29 4 3 6 词语存储 30 4 4 小结 31 第五章 排序索引 33 5 1 概述 33 5 2 统计相关 url 33 5 3 排序 34 5 4 索引 36 5 5 小结 37 第六章 搜索 38 6 1 概述 38 6 2 实现搜索 38 6 3 性能优化 41 6 4 小结 42 第七章 总结与展望 43 7 1 总结 43 7 3 展望 44 参考文献 47 致 谢 49 Web 搜索引擎的设计与实现绪论 1 第一章第一章 绪论绪论 1 11 1 搜索引擎出现的背景及意义搜索引擎出现的背景及意义 网络的出现以及发展对于世界发展的意义是极其重要的 它让地球村的理念 变成的现实 信息的传输不再受到时间和空间的限制 随着网络技术和应用的不断发展 互联网已经成为了信息的重要来源地 人们越来越依靠网络来查找他们所需要的信息 我们所处的是一个信息爆炸的 时代 Google 的索引在 1998 年开始工作 当时他们收集了 2600 万个页面 2000 年就突破了 10 亿 到 10 年后的 2008 年达到了 1 000 000 000 000 Google 的数 据库变成了全球最庞大的索引之一 8 数量之庞大让我们震惊 这么巨大的数 字导致了一个问题 Rich Data Poor Information 我们就好像处在一个信 息的迷宫 因此 如何有效快速的找到自己需要的信息成为了一个极其重要的 问题 在没有搜索引擎的时代 用户希望寻找某方面的信息 就必须通过各种途 径或者是网站之间的连接寻找 可以这样说 脱离的搜索引擎的网站 就像是 信息海洋中的一个一个的孤岛 用户必将面临巨大的搜索成本 同时必须付出 大量的时间和精力 搜索引擎的出现改变了上述的现象 4 它通过程序的自动搜寻并建立索引 将这些信息孤岛联系起来 形成了一张巨大的信息网 并且运用分布式计算的 巨大力量 能够让用户从海量数据中摒除垃圾信息 获取想要的知识 搜索引 擎不仅仅是节省了用户的时间 通过挖掉搜寻成本这座墙 它让许许多多的不 可能成为可能 1 21 2 搜索引擎的发展历史及趋势搜索引擎的发展历史及趋势 搜索经历了三代的更新和发展 8 第一代搜索引擎出现于 1994 年 这类搜索引擎一般都索引少于 1 000 000 个网页 极少重新搜集网页并去刷新索引 而且其检索速度非常 Web 搜索引擎的设计与实现绪论 1 慢 一般都要等待 10 秒甚至更长的时间 第二代搜索出现在 1996 年 第二代搜索引擎系统大多采用分布式方案 多个微型计算机协同工作 来 提高数据规模 响应速度和用户数量 它们一般都保持一个大约 50 000 000 网 页的索引数据库 每天能够响应 10 000 000 次用户检索请求 第三代搜索引擎年代的划分和主要特性至今没有统一的认识 不过至少可以 肯定的是 第三代搜索引擎是对第二代搜索引擎在搜索技术上的改进 主要增 加了互动性和个性化等高级的技术 为用户使用搜索引擎获取信息获得更好的 体验 至于互动性的评价标准是什么 以及第三代搜索引擎到底比第二代搜索 引擎增加了多少价值 尤其是为企业利用搜索引擎开展网络营销增加了哪些 价值 目前并没有非常令人信服的研究结论 这也就是目前所谓的第三代搜索 引擎并没有表现出太多优势的原因之一 现在 网络上有很多著名的搜索引擎 百度 google yahoo 等等 百度 从 2005 年诞生到现在成为全球最大的中文搜索引擎 可想而知 发展的速度的 多么的快 人们对搜索引擎的的需求的多大 百度的日点击率我无法在找到确 切的数字 但是我们可以计算一下 截至 2008 年底 中国网民规模达到 2 98 亿人 9 每个网民上网点击百度的次数应该不少于十次吧 像我们要在百度上 找资料的网名点击率百次不止 所以百度的日点击率是多么惊人 搜索引擎经过几年的发展和摸索 越来越贴近人们的需求 搜索引擎的技 术也得到了很大的发展 搜索引擎在将来的的发展趋势大概有以下几个方面 10 1 提高对用户输入的理解 为了提高搜索引擎对用户检索提问的理解 就必须有一个好的检索提问语 言 为了克服关键词检索和目录查询的缺点 现在已经出现了自然语言智能答 询 用户可以输入简单的疑问句 比如 how can kill virus of computer 搜索引擎在对提问进行结构和内容的分析之后 或直接给出提问的答案 或引 导用户从几个可选择的问题中进行再选择 自然语言的优势在于 一是使网络 交流更加人性化 二是使查询变得更加方便 直接 有效 就以上面的例子来 讲 如果用关键词查询 多半人会用 virus 这个词来检索 结果中必然会包 括各类病毒的介绍 病毒是怎样产生的等等许多无效信息 而用 how can kill virus of computer 搜索引擎会将怎样杀病毒的信息提供给用户 提 Web 搜索引擎的设计与实现绪论 2 高了检索效率 2 对检索的结果进行处理 对检索的结果处理 有以下几个方向 其一 使用链接评价 就是将网页 的链接数量算作网页评分因素之一 这样搜索的结果就更加的能够满足用户的 要求 在这个方面 google 的 链接评价体系 已经做出了 相当出色的成绩 其二 使用大众访问性 就是将访问数量 也可以叫做点击 数量 算作网页评分的因素之一 这样想 这样的网站的分数 会很高 而这样的网站很多时候都是用户想找的 这样能够提高搜索引擎的准 确率 其三 去掉结果中的附加信息 有调查指出 过多的附加信息加重了用 户的信息负担 为了去掉这些过多的附加信息 可以采用用户定制 内容过滤 等检索技术 3 确定搜集返回 提高针对性 在这个方面现在的发展的方向是 其一 垂直主题搜索 垂直主题的搜索 引擎以其高度的目标化和专业化在各类搜索引擎中占据了一系席之地 比如象 股票 天气 新闻等类的搜索引擎 具有很高的针对性 用户对查询结果的满 意度较高 我认为 垂直主题有着极大的发展空间 其二 非 www 信息的搜索 搜索引擎提供了例如 ftp 等非 www 信息的搜索 其三 多媒体搜索 搜索引擎 还提供了例如包括声音 图像等等多媒体信息的检索 4 提供更优化的检索结果 在这个方面有两个主要的发展方向 其一 纯净搜索引擎 这类搜索引擎 没有自己的信息采集系统 利用别人现有的索引数据库 主要关注检索的理念 技术和机制等 其二 元搜索引擎 元搜索引擎 metasearch enging 是将用户 提交的检索请求到多个独立的搜索引擎上去搜索 并将检索结果集中统一处理 以统一的格式提供给用户 因此有搜索引擎之上的搜索引擎之称 它的主要精 力放在提高搜索速度 智能化处理搜索结果 个性搜索功能的设置和用户检索 界面的友好性上 查全率和查准率都比较高 1 31 3 本文主要工作本文主要工作 本文在深入分析通用搜索引擎基本原理 架构设计和核心技术的基础上 Web 搜索引擎的设计与实现绪论 3 结合开源搜索引擎 lucene 和天网搜索引擎的实现原理 设计并实现了一个可扩 展 可复用的小型搜索引擎系统 本文的具体工作有以下几个方面 1 详细论述了系统结构 系统的设计原则以及目标 明确系统的功能 设 计出详细的系统流程图 2 分析了网络爬虫的工作原理 利用数据库设计出爬虫部分的详细流程图 并实现了系统的爬虫部分 3 详细设计了系统的信息处理部分 并且给出了设计的流程图 在中文切 成部分参照 lucene 的原理 做出了算法上的改进 对改进后的算法实现 并进 行了准确率和效率的测试 证明在效率上确实提高 4 根据排序和索引的原理 自己详细设计了这个部分 完成了详细流程图 并实现 5 为了提高系统的搜索效率 采用了缓存搜索页面和对搜索频率较高词语 结果缓存的两级缓存原则 1 41 4 论文结构论文结构 本文共分为七章 第一章 绪论 主要阐述了论文的研究背景与意义 搜索引擎的发展现状 发展趋势 论文的主要工作和组织结构 第二章 系统结构 主要对整个系统进行的概念和功能进行了描述 并且 对系统的各个部分进行了一个大概的介绍 并给出系统流程图 第三章 爬虫 对系统中的爬虫部分的原理进行了详细的说明 对爬虫部 分详细设计了流程图 并给出对爬虫部分的代码实现和对代码进行一定程度的 讲解 第四章 信息处理 对信息处理部分的原理进行详细的描述 详细设计了 流程图 给出了信息处理部分各种切词部分代码实现 并且对代码进行了一定 程度了解说 第五者 排序索引 对系统的排序和索引两个部分的原理进行详细的描述 并对用来实现排序和索引的数据结构进行详细的说明 给出流程图 第六章 搜索 对系统的最后一个环节 搜索进行了描述 给出实现搜 Web 搜索引擎的设计与实现绪论 4 索的消息步骤 并且对提高效率的两级缓存策略给出了详细的讲解 给出流程 图 第七章 总结 对整个毕业设计的过程和项目进行了总结 并且分析了系 统现有的不足 对不足之处给出了将进行改进的建议 Web 搜索引擎的设计与实现系统结构 0 第二章第二章 系统结构系统结构 2 12 1 概述概述 搜索引擎 41 Search Engines 就是指在 WWW World Wide Web 环境中 能够响应用户提交的搜索请求 返回相应的查询结果信息的技术和系统 是互 联网上的可以查询网站或网页信息的工具 2 它包括信息搜集 信息整理和用 户查询三部分 搜索引擎的服务方式分为两种 目录服务和关键字检索服务 目录服务是由分类专家将网络信息按照主题分成若干个大类 用户可以根据分 类清晰地找到自己所需要的内容 关键字检索服务可以查找包含一个或多个特 定关键字或词组的 WWW 站点 搜索引擎是互联网的第二大核心技术 涉及到信 息检索 人工智能 计算机网络 分布式处理 数据库 数据挖掘 数字图书 馆 自然语言处理等多领域的理论和技术 所以具有综合性和挑战性 2 22 2 系统结构系统结构 搜索引擎系统结构 1 分为爬虫 信息处理 排序索引 搜索四个部分 系 统结构图如图 2 1 所示 图 2 1 系统流程图 Web 搜索引擎的设计与实现系统结构 1 2 2 12 2 1 爬虫爬虫 爬虫也可以称作 网络爬虫程序 web 爬虫 网络蜘蛛 网络机器 人 网络爬虫是一个自动提取网页的程序 它为搜索引擎从万维网上下载网 页 是搜索引擎的重要组成 传统爬虫从一个或若干初始网页的URL 开始 获得初始网页上的 URL 在抓取网页的过程中 不断从当前页面上抽取新的 URL 放入队列 直到满足系统的一定停止条件 2 2 22 2 2 信息处理信息处理 信息处理指的是当爬虫从万维网上下载了网页 对网页中包含的信息进 行处理 其中包括提取网页中包含的url 为爬虫的继续提供所需要的 url 这个事很重要的 因为没有新的url 出现的话 爬虫程序就会停止 这样就无法获得全面的信息 信息处理还必须得网页显示的内容进行分析处 理 把网页的内容切成词语 为下面的排序和索引部分提供相应的信息 2 2 32 2 3 排排序序和和索索引引 在信息处理完成之后 每个网页都会被切成很多个关键词 同时每个词语 都会有很过个相关的网页 排序所要做的事就是把每个词语的相关的网页按词 语的出现次数进行排序 这样在进行搜索时结果的出现顺序提供依据 接下来 的索引程序就是以词库为索引关键字建立索引 这样在搜索的时候就能够在最 短的时间找出我们想要的结果 2 2 42 2 4 搜索搜索 在上述的工作完成之后 便可以为用户提供搜索服务了 按照用户的关键 字或词的输入 按照所建立的索引在最短的时间内找到相应的结果 返回相应 的数据 然后在网页上显示返回的结果 是用户能够选择自己想要的信息 2 32 3 搜索引擎主要指标及分析搜索引擎主要指标及分析 搜索引擎的主要指标有响应时间 召回率 准确率 相关度等 这些指标 Web 搜索引擎的设计与实现系统结构 2 决定了搜索引擎的技术指标 搜索引擎的技术指标决定了搜索引擎的评价指标 好的搜索引擎应该是具有较快的反应速度和高召回率 准确率的 当然这些都 需要搜索引擎技术指标来保障 毕业设计论文代做平台 580 毕业设计网 是专业 代做团队 也有大量毕业设计成品提供参考 QQ3449649974 召回率 一次搜索结果中符合用户要求的数目与用户查询相关信息的总数之比 准确率 一次搜索结果中符合用户要求的数目与该次搜索结果总数之比 相关度 用户查询与搜索结果之间相似度的一种度量 精确度 对搜索结果的排序分级能力和对垃圾网页的抗干扰能力 2 42 4 开发语言开发语言 本文在开发语言上选择的是 c 语言 5 因为 C 在带来对应用程序的快速开 发能力的同时 并没有牺牲 C 与 C 程序员所关心的各种特性 它忠实地继承 了 C 和 C 的优点 C 语言还有以下的优点 15 1 简洁的语法 语法中的冗余是 C 中的常见的问题 比如 const 和 define 各种各 样的字符类型等等 C 对此进行了简化 只保留了常见的形式 而别的冗余形 式从它的语法结构中被清除了出去 2 精心设计面向对象 在 C 的类型系统中 每种类型都可以看作一个对象 C 提供了一个叫做装 箱 boxing 与拆箱 unboxing 的机制来完成这种操作 而不给使用者带来麻烦 这在以后的章节中将进行更为详细的介绍 C 只允许单继承 即一个类不会有多个基类 从而避免了类型定义的混乱 在后面的学习中你很快会发现 C 中没有了全局函数 没有了全局变量 也没 有了全局常数 一切的一切 都必须封装在一个类之中 你的代码将具有更好 的可读性 并且减少了发生命名冲突的可能 3 完整的安全性与错误处理 语言的安全性与错误处理能力 是衡量一种语言是否优秀的重要依据 C 的先进设计思想可以消除软件开发中的许多常见错误 并提供了包括类型安全 在内的完整的安全性能 NET 运行库提供了代码访问安全特性 它允许管理员 Web 搜索引擎的设计与实现系统结构 3 和用户根据代码的 ID 来配置安全等级 变量是类型安全的 4 灵活性与兼容性 在简化语法的同时 C 并没有失去灵活性 正是由于其灵活性 C 允许与 C 风格的需要传递指针型参数的 API 进行交互操作 DLL 的任何入口点都可以在 程序中进行访问 C 遵守 NET 公用语言规范 Common Language Specification CLS 从而保证了 C 组件与其它语言组件间的互操作性 元数 据 Metadata 概念的引入既保证了兼容性 又实现了类型安全 2 52 5 小结小结 本章对基于因特网的搜索引擎结构和性能指标进行了分析 在这些原来的 理解基础之上利用 c 技术完成了一个小的 web 搜索引擎 在接下来的章节将对 搜索引擎结构中的网络爬虫设计进行说明 并给出关键部分的实现代码 Web 搜索引擎的设计与实现爬虫 0 第三章第三章 爬虫爬虫 3 13 1 概述概述 网络蜘蛛即 Web Spider 是一个很形象的名字 3 把互联网比喻成一个蜘 蛛网 那么 Spider 就是在网上爬来爬去的蜘蛛 网络蜘蛛是通过网页的链接地 址来寻找网页 从网站某一个页面 通常是首页 开始 读取网页的 找到在 网页中的其它链接地址 然后通过这些链接地址寻找下一个网页 这样一直循 环下去 直到把这个网站所有的网页都抓取完为止 如果把整个互联网当成一 个网站 那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来 对于搜索引擎来说 要抓取互联网上所有的网页几乎是不可能的 6 从公 布的数据来看 容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四 十左右 这其中的原因一方面是抓取技术的瓶颈 无法遍历所有的网页 有许 多网页无法从其它网页的链接中找到 另一个原因是存储技术和处理技术的 如果按照每个页面的平均大小为 20K 包含图片 100 亿网页的容量是 100 2000G 字节 即使能够存储 下载也存在问题 按照一台机器每秒下载 20K 计算 需要 340 台机器不停的下载一年时间 才能把所有网页下载完毕 同时 由于数据量太大 在提供搜索时也会有效率方面的 因此 许多搜索引 擎的网络蜘蛛只是抓取那些重要的网页 而在抓取的时候评价重要性主要的依 据是某个网页的链接深度 3 23 2 爬虫结构分析爬虫结构分析 爬虫部分分为爬虫初始化 从网页中提取 url 对 url 进行存储 从数据 中提取 url 四个部分 爬虫部分的流程图如图 3 1 所示 在本节将对爬虫的工 作原理进行详细的描述 Web 搜索引擎的设计与实现爬虫 1 图 3 1 爬虫流程图 3 2 13 2 1 爬虫初始化爬虫初始化 爬虫程序的开始是需要一个最初始的 url 爬虫将先下载这个 url 的内容 然后提取里面所包含的 url 所以这个最初始的 url 是很重要的 如果没有一 个好的初始的 url 这个 url 所包含的 url 会很少 那么爬虫所能爬下的网页 的数量也将大受影响 得到了初始的 url 以后 就可以下载网页的内容了 以 下就是下载网页的代码 HttpWebRequest loHttp HttpWebRequest WebRequest Create url 创建连接 loHttp Timeout 500 设置超时 HttpWebResponse loWebResponse HttpWebResponse loHttp GetResponse 获取响应 StreamReader loResponseStream new StreamReader loWebResponse GetResponseStream System Text Encoding Default 获取返回的流 html loResponseStream ReadToEnd 读取流 loWebResponse Close 关闭连接 有关于 httpwebrequest 类说明如下 12 NET Framework 使用 HttpWebRequest 和 HttpWebResponse 类来提供对 HTTP 协议的全面支持 而 HTTP 协议构成了所有 Internet 通信量中的绝大部分 每当静态方法 WebRequest Create 遇到以 http 或 https 开头的 URI 时 Web 搜索引擎的设计与实现爬虫 2 在默认情况下将返回这些从 WebRequest 和 WebResponse 派生的类 在大多数 情况下 WebRequest 和 WebResponse 类提供生成请求所需的一切 但如果需 要访问作为属性公开的 HTTP 特定功能 则可以将这些类的类型转换为 HttpWebRequest 或 HttpWebResponse HttpWebRequest 和 HttpWebResponse 封装 标准 HTTP 请求和响应 事务 并提供对通用 HTTP 头的访问 这些类还支持大部分的 HTTP 1 1 功能 其中 包括管线 块区 身份验证 预身份验证 加密 代理支持 服务器证书验证 以及连接管理 自定义头和不是通过属性提供的头可存储在 Headers 属性中并 可通过此属性访问 HttpWebRequest 是 WebRequest 使用的默认类 不需要注册它就可以将 URI 传递给 WebRequest Create 方法 可以通过将 AllowAutoRedirect 属性设置为 true 默认值 使应用程序自 动遵循 HTTP 重定向 应用程序将重定向请求 而 HttpWebResponse 的 ResponseURI 属性则将包含响应请求的实际 Web 资源 如果将 AllowAutoRedirect 设置为 false 则应用程序必须能够将重定向作为 HTTP 协议错误处理 应用程序通过捕捉 Status 设置为 WebExceptionStatus ProtocolError 的 WebException 来接收 HTTP 协议错误 Response 属性包含由服务器发送的 WebResponse 并指示遇到的实际 HTTP 错误 3 2 23 2 2 从网页中提取从网页中提取 urlurl 当把网页的代码下载完毕后 就需要对代码进行一次遍历 找出并提取其 中的 url 为爬虫的继续提供 url 对代码中的 url 的提取采用的是正则表达式 的方法 比较代码中所以匹配 url 正则表达式的部分 然后遍历这个集合 逐 条的读取其中的 url 以下为代码 string strRegex http w w w url 的正则表达式 Regex r new Regex strRegex RegexOptions IgnoreCase 初始化一 个 regex 对象 为比较作准备 Web 搜索引擎的设计与实现爬虫 3 MatchCollection m r Matches htmlCode 比较并得出代码中匹配 的集合 for int i 0 i m Count 1 i 遍历集合 得出其中的 url bool rep false string strNew m i ToString 3 2 33 2 3 URLURL 存储存储 在上面的部分得到了代码中的 url 接着用数据库对得到 url 进行存取 在 数据库中创建两个表 一个存储已经下载过的 url 一个存储还没有下载过的 url 在网页中得到的 url 进行如下几步处理 1 首先在已经下载过的 url 表中进行搜索 如果找到了 说明这个 url 的内 容已经被下载过了 再次下载不仅浪费了网络资源 更加浪费服务器的资源 所以对这样的 url 丢弃 2 如果在下载过的 url 表中没找到相同的 url 说明程序没有下载过这个 url 中内容 需要对其进行下载 于是在没有下载过的 url 表中搜索 如果搜 索到相同的 url 说明这个 url 已经存在了 再次添加只会让服务器对其进行 重复的下载 浪费了资源 不需要在添加 丢弃 3 如果在没有下载过的 url 表中找不到相同的 url 说明这个 url 还没有被 添加过 则将这个 url 添加到没有下载过的 url 表中 3 2 43 2 4 从数据库中提取从数据库中提取 urlurl 这个时候数据库中已经存在了很多的没有下载的 url 而其数量在增加中 我们就可以开启多线程程序 每个程序独自的从没有下载过的 url 表中提取一 个 url 进行下载 解析 存储 在下载完毕后将这个 url 从没下载过的 url 表 中删除 并且在下载过的 url 表中添加 这个时候需要注意的几个问题 1 那就是不能让多个线程同时从一个服务器上进行下载 比如多个线程同 时从 这样的大型服务器上进行下载 这样服务器有可能认为 Web 搜索引擎的设计与实现爬虫 4 受到了攻击 会将服务器的 ip 列入黑名单中 这样的话服务器以后都无法 下载 里的内容 2 超时问题 应该为每个下载设置一个等待的上限 在等待的时间超过了 这个上限后 仍然无法完成下载的话 程序就有理由认为对这个 url 的下 载时失败的 失败的原因很多 暂且不追寻它的原因是什么 程序就应该 及时的停止下载 以免造成线程的浪费 3 33 3 小结小结 在本章中 首先介绍了爬虫的基本概念 然后给出了爬虫的结构图 并逐 一的对爬虫中的每个程序模块进行了详细的讲解 并且给出了关键部分的代码 实现 爬虫是搜索引擎系统的开始部分 尽管实现起来没有太大的难度 但是 它是整个程序的开始 是整个程序的基石 以后的部分都是在它的基础上形成 的 所以要考虑完全 下面一章便开始对信息处理部分的设计进行详细的描述 并且给出关键部分的代码实现 Web 搜索引擎的设计与实现信息处理 0 第四章第四章 信息处理信息处理 4 14 1 概述概述 图 4 1 信息处理流程图 经过上面的处理程序已经成功的获得了网页代码 但是程序需要的只是网 页中包含的信息的词语 只有得到这些词语 才能够对词语相关的网页进行排 序和完成索引 在这本章就将对网页进行一系列的处理 以尽可能快的速度得 到这些词语 这些处理过程包含 转换 切词 信息处理的流程图如图 4 1 所 示 Web 搜索引擎的设计与实现信息处理 1 4 24 2 转换转换 图 4 2 内容转换流程图 根据上述所知程序要得到是组成一个网页的词语 程序现在拥有的是网页 的代码 当然代码中肯定包含了网页中所有的文字信息 25 但是不要忘记 代 码同时也包含了许多的 html 标签 这些标签不仅仅只是 html 的标准标签 同 时还有用户自定义的标签 对这些标签的处理我试过了如下的几种方法 1 去掉标签本身 但是对标签中间包含的内容还是进行正常的处理 例如 this is my first web page 程序在处理的时候会自 动的去掉和两个部分 然后对 this is my first web page 这个部分进行正常的处理 这中处理的方式会很好的切到网页中 所包含的文字信息 但是它有这样几个问题 a 首先 这样的方式程序会对 html 中的每个标签都进行如上的处理 一个 html 有时候标签所占得字符是远远的多于它所包含的文字 信息 这样的话程序的效率会因为处理很多无用的标签而浪费支 援 减低了效率 b 面对像 这样标签 它中间的内容是无用的 它只是对网页的显示效果有用 但是上面的程序还是会对它中间 的内容进行我们的切词程序 这样不仅大大的减低了程序的效率 还切刀了许多根本于网页的内容无关的词语 这样就会降低搜索 引擎的准确性 Web 搜索引擎的设计与实现信息处理 2 c 面对像 这样的标签 必须对它进行解析 才知道它运行后会得到什么结果 暂且不管能不能实现对它的解 析 即使能够写出这样的程序 但是不得不花大量的时间去想这 个程序 而其最后这个程序也得花大量的资源堆网页的 进行解析 所以这个问题否定了上面的 方法的可行性 2 面对和这两个标签 采用的方法是过滤掉标签中间包 含的内容 对其他标签 处理的方式与方法 1 是一样的 这个方法似乎 解决了方法 1 中的 b c 两个问题 但是真的是这样吗 我来分析一下 这个方面的缺点 a 首先 跟方法 1 一样 这样的方式程序会对 html 中的每个标签 都进行如上的处理 我们知道 一个 html 有时候标签所占得 字符是远远的多于它所包含的文字信息 这样的话程序的效率 会因为处理很多无用的标签而浪费支援 减低了效率 b 过滤了标签中间包含的内容 会丢失一定得信息 因 为网页的有些内容必须是在运行了脚本之后得到的 这样的话搜索引擎的准确率会因此降低 上面的两个方法都有效率的问题 而且各自也有着其他的问题 经过了几天 的思考 找到了一个相对来说比较好的方法 这个方法如下 首先程序会使用到一个控件 它叫 webbrowser 这个控件的功能是根据所 给的 html 的代码 它可以将网页显示出来 跟使用的 IE 的效果是一样的 这 样的话 似乎程序将爬虫下载好的代码放到 webbrowser 中 在获得控件 document body innertext 属性就可以了 但是这其中还有一个问题 那就是控件的加载的时间问题 经过测试 我发现控件的加载时间是整个程 序执行完了之后 也就是说即使在程序的开始处你把 html 代码赋值到控件 然 后在下面的程序中想使用 document body innertext 来获得网页内容 这个时 候程序会报 nullReferenceException 错误 因为在这个时候控件还没有加载 所以控件的内容还是空的 怎么解决个问题呢 本文使用了多进程使用另外一个程序来执行 Web 搜索引擎的设计与实现信息处理 3 webbrowser 控件的加载 这样当这个程序执行完成之后加载了控件 可以在 documentCompleted 方法中得到 document body innertext 然后程序进程间通 信将转换了的内容传回原来的程序 进程间通信程序采用的消息队列 13 关键 代码如下所示 转换代码 webBrowser1 DocumentText htmlCode 把html代码赋值给控 件 webBrowser1 Select 选中控件 webBrowser1 DocumentCompleted new WebBrowserDocumentCompletedEventHandler webBrowser1 DocumentCompleted 将方法webBrowser1 DocumentCompleted加到控件的事件中 当控件加载完成时调用的方法 public void webBrowser1 DocumentCompleted object sender WebBrowserDocumentCompletedEventArgs e htmlTex webBrowser1 Document Body InnerText 进程间通信的代码 internal class Transmit MessageQueue codeQueue null 申明一个消息队列 string codeQueueName Private webSearchCode 消息队 列的名字 public Transmit 初始化 对消息队列进行初始化 if MessageQueue Exists codeQueueName 如果消息队列存在 获得它 codeQueue new MessageQueue codeQueueName Web 搜索引擎的设计与实现信息处理 4 Else 如果消息队列不存在 创建一个消息队列 codeQueue MessageQueue Create codeQueueName public void send ref string htmlText string url codeQueue Send htmlText url 向消息队列中发送一个消息 4 34 3 切词切词 经过了上述的程序的转换过后 现在程序已经得到了网页显示的内容 就 像我们在 IE 中对网页进行全选 然后在复制 在记事本中粘贴出来的结果是一 样的 接下来就需要对这些内容进行切词 网页的词语我们可以划分为以下几 个部分 中文 英文 数字 其他的符号 对于不同的词语程序应该采用不同 的处理方式 所以需要对当前词语做一个判断 然后分类进行处理 对词语类 型的判断可以采用正则表达式来进行 代码如下 private int judge string str Regex rehanzi new Regex u4e00 u9fa5 0 初始 化中文的正则表达式 Regex reshuzi new Regex 0 9 初始化数字的正则 表达式 Regex reenglish new Regex A Za z 初始化英文的 正则表达式 if str n str t str r return 3 if rehanzi Match str Success return 0 说明是汉字 Web 搜索引擎的设计与实现信息处理 5 else if reenglish Match str Success return 1 说明是字母 else if reshuzi Match str Success return 2 说明是数字 else return 3 说明是其他的一些符号 return 1 经过上述的判断 我们就可以对不同的词语采取不同的处理方式 4 3 14 3 1 中文切词中文切词 图 4 3 中文切词流程图 Web 搜索引擎的设计与实现信息处理 6 中文切词 19 就是要程序把中文的语句切成一个一个的词语 这个工作是 相当复杂的 本文把它分成了初始化词库 词语定位 切词比较三个部分 下 面我将对每个部分进行详细的讲解和给出关键的代码 a 初始化词库 要进行中文切词 就需要一个中文的词库 没有这个词库 程序是无法完成的 本文用的词库是从网上下载的一个词库 不是很大 2M 左 右 词库下载完了 那么怎么用这个词库变成了一个很大的问题 查看了 lucence 一个使用 java 语言完成的搜索引擎 的代码 发现它是将整个词库 导入到一个哈希表里面 然后把切下的词到这个哈希表中查找 找到了就说明 当前词语是一个中文的词 但是这样的效率是很低下的 因为一个词库大概要 有二十万到三十万个词语 把它导入一个哈希表 这个哈希表太大了 它的查 找效率应该是很低的 还有在切词过程中 查找的次数是巨大了 如果每次查 找哪怕多用很少的时间 对于整片文章来说 完成整个的切词工作耗费的时间 也是很多的 因此 本文对词库进行了如下的改进 因为每个词语无论它的长度怎么变 它的首字是不会变的 这样针对一个词语 应该可以把查找的范围缩小 只要 查找的范围缩小了 查找的效率也就能够提高了 于是 本文把词库按照词语 的首字的拼音的前两个字母进行了一个划分 把原来的一个词库分成了 93 个 然后把词库导入到一个哈希表数组中 这样每个词库的平均大小只有 20k 左右 大大的减小了 每个哈希表中所包含的词语的数量也大大的减小了 针对一个 词语 它的查找始终是定位在一个哈希表的 是不会改变的 所以没个词语 经过一次定位以后 就可以在一个很小的范围内进行查找 词库初始化的工作还没有结束 还有一个很重要的事 那就是最大长度匹 配 我们对一条语句进行切词 应该要保证切下来的词语是最少的 也就是没 个词语都要尽量的长 例如 中华人民共和国 可以切成如下几个词语 中华 中华人民 中华人民共和国 但是最终选择的结果应该是最长的 那个结果 这个就相当的困难了 因为切词 词语是一个字一个字加上去的 在以上面的例子为例 程序首先切下了 中华 两个字 组成一个词 然后在 哈希表中进行查找 找到了 说明它是一个词语 我们在切下 人 字加到词 语中 得到了 中华人 这个词语在词库中是没有的 但是当在切下 民 加 到词语中时 组成了 中华人民 怎么样才能让程序切到 人 字的时候不停 Web 搜索引擎的设计与实现信息处理 7 止 而是继续往下切词呢 解决得办法就是程序在构造一个词库 原来的词库是一行存一个词 现在 改变一下 把词语全部连起来 每个词语中间加上一个 这样就可以区分 词语了 然后把新构造的词库读到一个 string 数组中 这样就可以使用 string 类型特有的 contains 方法来判断词库当中是不是包含了这个词 还是 上面的例子 在 string 中会有这样一段 中华人民共和国 当切词切到 中华人 的时候 调用 string 的 contains 方法 返回的 true 切词程序就 会继续往下走了 通过这样就能够实现最大长度匹配了 关键代码如下 public static Hashtable menuList new Hashtable 存放用于查找词语属于的列表 public static string dicText new string 93 存放不以行分的词库的字符串 public static void setWordHT string path string copyPath string wordText FileStream fCreate FileStream wordFS StreamReader wordSR FileStream fileOpen StreamWriter fileWriter bool needWrite false for int i 0 i 93 i 初始化哈希表词库 wordHT i new List wordText path word menuList i ToString txt copyPath word menuList i ToString Copy txt if File Exists copyPath fCreate File Create copyPath fCreate Close needWrite true wordFS new FileStream path FileMode Open FileAccess Read wordSR new StreamReader wor