搜索引擎原理——使用Perl.ppt

搜索引擎原理——使用Perl 周 恒 LinuxMEhiko@ 搜索引擎原理（使用Perl）－主要目的 介绍典型的Web搜索引擎原理 使用Perl，来和大家一起完成一个简单Web搜索引擎的主要部分（perlBEE） 和大家一起交流，共同探讨Perl、推广Perl 搜索引擎原理（使用Perl）－主流搜索引擎 搜索引擎原理（使用Perl）－PerlBEE搜索引擎 假设在学校内部，不同组织维护着多个Http及Ftp服务器，向校内提供服务。 使用perl,编写一个简单的搜索引擎，检索这些服务器内的资源。 Linux＋Apache ＋ MySQL ＋ Perl (old version) 搜索引擎原理（使用Perl）－基本要求 接受用户提交的关键字（q） 在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表（L） 可以接受的时间： 匹配： 列表： 搜索引擎原理（使用Perl）－三段式工作流程 网页搜集： 预处理： 提供服务： 搜索引擎原理（使用Perl）－网页搜集 网页数据库的基本策略： 1）定期搜集： 2）增量搜集： 网页的抓取策略： 1）“爬取”策略： 2）维护URL： 搜索引擎原理（使用Perl）－定期搜索 定期搜索，隔一段时间后对整个网页重新搜集一遍，替换以前的内容。 优点：实现起来较简单 缺点：开销较大，两次搜集的时间间隔不会很短，“时新性（freshness）”不高 搜索引擎原理（使用Perl）－增量搜索 开始时搜集一遍，然后： 1.搜集新出现的网页 2.搜集更新了的网页 3.发现有网页已经不存在，则从库中删除 搜索引擎原理（使用Perl）－ “爬取”策略 将Web看作是一个有向图，搜集过程从给定的起始url集合S开始，沿着网页中的链接，按照一定的策略（先深/先宽/others）遍历。 这个过程象蜘蛛（spider）在蜘蛛网（Web）上爬行（crawl） 搜索引擎原理（使用Perl）－维护URL 系统进行第一次全面的网页搜集之后，维护相应的URL集合，以后的搜索基于此集合。 搜索引擎原理（使用Perl）－存储网页 搜集到的网页将存储到知识库（repository）中。 知识库包含每个网页的docID，长度，URL以及网页的全部HTML。 由于网页数量会很多，所以，网页在存入知识库时要进行压缩处理。 搜索引擎原理（使用Perl）－PerlBEE的网页搜集部分 手动执行脚本，进行资源搜集 从维护的url列表当中获得url 支持http和ftp协议 获得的网页按照文件的形式存入知识库中。 搜索引擎原理（使用Perl）－PerlBEE的网页搜集部分 对知识库进行索引，以便快速定位网页原文 搜索引擎原理（使用Perl）－预处理 链接分析 网页重要程度计算 关键词提取 搜索引擎原理（使用Perl）－链接分析 链接是分析网页重要的信息 1.链接描述文字准确的反映了网页的内容 2.网页之间的链接关系，反映了网页的重要程度（PageRank Google） 搜索引擎原理（使用Perl）－网页重要程度计算 PageRank（Google） 指向一个网页的链接越多，说明这个网页越重要。 把整个web结构看作一个矩阵。N个网页就形成一个n×n的矩阵。 搜索引擎原理（使用Perl）－关键词提取 建立倒排索引 英文的分词 中文的分词 搜索引擎原理（使用Perl）－中文分词技术 中文分词是中文搜索引擎的核心 中文分词技术 基于字符串匹配的分词方法 基于统计的分词方法 搜索引擎原理（使用Perl）－基于字符串匹配的分词算法 正向减字最大匹配法（MM） 逆向减字最大匹配法（RMM） 将上述两种方法结合起来 搜索引擎原理（使用Perl）－PerlBEE的预处理部分 读取网页 英文按照空格切开 中文按照正/逆向最大匹配的方法切词 将词编入索引文件 搜索引擎原理（使用Perl）－查询服务 查询方式和匹配 结果排序 文档摘要 搜索引擎原理（使用Perl）－查询方式和匹配 布尔模型 向量模型 概率模型 搜索引擎原理（使用Perl）－文档摘要 搜索引擎原理（使用Perl）－PerlBEE的查询服务.CGI 对用户输入进行切分 查找结果 对结果进行合并 搜索引擎原理（使用Perl）－使用Perl * * docID Web原文 获取的时间 url docID Web原文 获取的时间 url 69 12387 2 12387 0 1 length Position docID Word DocID DocID * * * 解释： 可以接受的时间 、 匹配 、 列表 解释： 网页搜集、预处理、服务 Google，更新一次大概需要一个月