走进搜索引擎

走进搜索引擎 章节 1 搜索引擎基本背景 发展历程2 宏观介绍搜索引擎 以及搜索引擎主要系统划分3 搜索引擎之下载系统背景知识 设计原理 技巧以及网页库设计 一 搜索引擎基本背景 发展历程 背景 万维网以非线性组织是人们在信息海洋中彷徨 因此催生出搜索引擎定义 在万维网上检索各种文件的计算机程序 与其说searchengine为一个查询系统 不如说是一个用于自定义的信息聚合系统分类 目录是搜索引擎 全文搜索引擎 元搜索引擎发展史 Archine Wanderer RBSE FTP文件名查找文件 获取URL 索引HTML文件正文 引入关键字匹配的搜索引擎 二 介绍搜索引擎 主要系统划分 1 宏观介绍 搜索引擎4大基本需求 快速 全面 准确 稳定可靠1 快速 信息爆炸增长 跟的上信息的脚步影响因素 索引库效率 分布查询能力 查询缓存命中率2 全面 应用查询率recall影响因素 网页索引库的大小 库的数目与recall成正比3 准确 precision 得到的结果为正确的内容4 查的稳 系统稳定运行 在任何情况下可惜牺牲检索质量和检索速度来换取检索服务 Recall 检索出相关的网页数 所有相关网页数例子 XML 如果世界包含 XML 的网页数为M 而实际检索出的M条中的N 则recall N MPrecision 检索出相关文档树 检索出文档总数例子 XML 如果实际检索出网页数N中 只有P个网页是与 XML 有关 则precision P N A 与XML有关网页 B 检索出的与XML有关网页 AnB Recall AnB A Precision AnB B 系统划分 前3类属于离线部分 需要长达几周时间才能计算完毕最后1类属于在线部分 需要毫秒级的访问速度 三 下载系统 背景 搜索引擎的基础 搜索数据均来自下载系统的工作爬虫 Wanderers 爬虫 劳动者网络资源 劳动资料万维网 劳动对象因此 理解劳动对象才能理解劳动者先介绍万维网 万维网具有蝴蝶结构 SCC56百万nodes IN OUT 须脚44百万nodes 不相关的部分 1 蝴蝶中部ssc stronglyconnectedcomponent 这种类型网页彼此相连 任意去掉有限个网页不影响连通度 BFS无论采取正向遍历 反向遍历都可以得到全部网站3 4的网页数2 蝴蝶左部 IN 这种类型网页指向SSC 称为 目录型网页 通常称为 导航网站 BFS正向遍历得到全部3 4网页数 反向遍历忽略不计3 蝴蝶右部 OUT 这种类型网页被中心SSC所指向 称为 权威网页 如果该网页被引用次数越多 说明 可靠度 越高 BFS正向遍历忽略不计 反向遍历为全部3 4网页数 4 蝴蝶须脚这种类型网页 左部链出到其他网页 其他网页链入右部 左部之间链入右部BFS无论正向或者反向都只能遍历有限的网页数因此 1 爬虫尽可能选择蝴蝶左部 或者中部进行遍历 须脚或右部只有少许网页被抓取2 网页分为目录型网页和权威性网页 目录型 门户网 导航网站 权威性网页 官网 较少斜杠 com home 爬虫 万维网网页结构没有想象那么深 却非常宽 选择BFS 为了防止爬虫一路走到黑 考虑万维网直径 采用DFS控制深度 要求 抓的全 抓的快 低代价 原理 通过下载一个网页 分析其中的链接 继而漫游 Wander 到其他链接所指向的网页 工作 抓取 策略 存储 抓取 选择蝴蝶左部目录型网页下载 抓取 一个网页策略 从门户网页中得到的链接进行遍 BFS DFS BFS利于抓取 先站内 后站外 封闭性强 1 Windows命令窗口 3 GET index html 1 2 3 4 5 6 死循环 解决方法 不重复抓取策略 DFS策略 不重复抓取策略原理 记录存储状态实现 hash表 抓取过 槽位置1 否则置0例子 MD5签名为hash函数Intx stringy x MD5 y 把字符串经过MD5函数得到一个整数U 整数聚合 S 字符串集合任意的URL i 属于S URL j 属于ST i MD5 URL i T j MD5 URL j 其中T i 属于集合U T j 也属于集合U且URL i URL j 有P T i T j 对两个不同的URL 产生出的签名值 冲突 概率小于一个足够小的小整数 冲突只能是减少 不可能避免 S S S MD5签名 0 1 0 0 1 0 0 0 第一次抓取 放槽1 之后再抓取 发现槽1为1 所以不抓取 MD5签名 34 IntHash 8 总共有8个槽位 0 Hash 1 每个槽位有32位比特位 4 0 0 0 0 0 0 0 0 0 1 0 0 0 34 32 8 1 在槽位1中 即Hash 1 34 32 2 在Hash 1 中 右起第3位 Bitmap结构hash结构图 十进制为4 即槽1的数值为4 该表以整形为单位 一个整形32位 IntMD5 34Intindex int MD5 31 34 32Intindex hash MD5 5 7 34 32 8If Hash index hash 1 index int 判断槽位是否置位 查询某个比特位为1if Hash index hash 1 index int 槽位没有被置位 通过Hash标志之后 如果抓取的网页之前出现过 则跳出循环条件利用好DFS遍历 种子站点A 种子站点B 种子站点C P 路径3 路径53 路径133 因此 限定搜索路径在一个范围之内 比如定义该范围为万维网的直径长度 深度超过这个度的话 遍历终止 很明显的看的出来 B与C浪费时间 2 抓取网页重要性 重要性 链接欢迎度 IB 链接重要度 IL 平均链接深度 ID 1 链接欢迎度 IB 由反向链接数目和质量决定1 反向链接越多 说明对该网页认可度越高 推断出其重要性越高2 其次是质量 越多被重