互联网搜索技术交流.ppt

1、2020/7/24,1,互联网搜索技术交流,中国电信股份有限公司广州研究院 广东省电信有限公司研究院 年 月 日,2020/7/24,2,目录,互联网搜索发展历程 互联网搜索基础技术 互联网搜索新技术及应用,2020/7/24,3,搜索引擎发展历史,自动搜索 1990-加拿大麦吉尔大学FTP文件查找软件Archie 1993-Matthew Gray开发第一个网页爬虫World Wide Web Wanderer 1994-Michael Mauldin创建首个现代意义的搜索引擎Lycos 1998-Google 2000-百度 人工整理的目录搜索 1995-Yahoo 1996-搜狐,202

2、0/7/24,4,搜索引擎商业模式,广告商支付网站上放置的广告条 CPM: Cost Per Mille (thousand impressions). 每一次广告条显示都收费. CPC: Cost Per Click. 只有用户点击时才收费. CTR: Click Through Rate. 点击占总显示数目的比例. CTR = CPC / (CPM * 1000) CPA: Cost Per Action (Acquisition). 只有当用户在目标网站上实际购买时才收费. 广告商竞拍“关键词”，当用户查询中包含一个被购买的关键词，最高拍卖价格的广告显示. PPC: Pay Per Cl

3、ick. 竞拍词广告的CPC (e.g. Google AdWords).,2020/7/24,5,目录,互联网搜索发展历程 互联网搜索基础技术 互联网搜索新技术及应用,2020/7/24,6,最简单的Web搜索流程,www,采集,语言处理,索引,检索,Web搜索 应用服务,2020/7/24,7,Pages,最简单的Web搜索体系结构,www,爬虫,存储,页面解析,索引器,检索器,缓存,搜索应用,HTML锚,链接解析,链接库,反向索引,PageRank,采集,预处理,索引,检索,用户查询,2020/7/24,8,Web采集,页面解析,索引器,检索器,缓存,应用界面,URL解析,链接,反向索引

4、,PageRank,预处理,索引,检索,查询,Pages,www,爬虫,存储,HTML锚,采集,通过超链抓取Web网页，并定期更新。 问题与挑战： 如何高效准确地发现与剔除重复页面？ 如何检测高质量页面？如何反spam？ 如何预测各类网页的刷新率，以保证索引时新性 如何综合这些因素？ Invisible web如何获取？,2020/7/24,9,采集,页面分析和信息抽取,索引,检索,预处理,索引器,检索器,缓存,应用界面,URL解析,链接,反向索引,PageRank,查询,Pages,www,爬虫,存储,HTML锚,页面解析,分析页面，提取用于索引的信息：Title，URL，Body(锚文本，

5、纯文本，黑体，斜体，文字大小等) 建立Link map 发现新的超链供采集器使用 问题与挑战： 页面的哪些特征是有用的必须抽取？ BBS，社区，Blog，产品，新闻等等，页面是设计给人看的，结构特征各异，如何准确抽取有用信息？,2020/7/24,10,预处理,采集,索引,检索,索引,页面解析,检索器,缓存,应用界面,URL解析,链接,反向索引,PageRank,查询,Pages,www,爬虫,存储,HTML锚,建立索引以加速查询，目前使用最广最高效的是倒排索引 问题与挑战： 性能：如何在计算资源有限的情况下快速构建索引？ 文档更新：倒排索引天生不适合文档的更新，如何支持文档的实时更新？ 在线

6、索引：Blog，新闻，论坛，交易信息等更新非常快，如何做到实时索引的同时实时检索？ 分布式：document partition ，term partition或者其他模式？大量计算资源的管理，容错 (Google File System, MapReduce, BigFile),索引器,2020/7/24,11,页面解析,索引器,缓存,应用界面,URL解析,链接,反向索引,PageRank,查询,Pages,www,爬虫,存储,HTML锚,预处理,采集,搜索,索引,检索,利用建立的倒排索引，结合链接结构等信息处理查询，返回Top-k结果 问题与挑战： 效果：如何从巨大的文档集中在第一个页面上

7、返回用户真正想要的东西？更好的IR Model，PageRank算法？ 性能：在资源有限的情况下如何快速处理Top-k查询？New Index strategy, index compression，index pruning？ 处理link图非常耗时，更高效的算法？ Link-spam 是否有比链接分析更好的，spam免疫的方法？,检索器,2020/7/24,12,页面解析,索引器,检索器,应用界面,URL解析,链接,反向索引,PageRank,查询,Pages,www,爬虫,存储,HTML锚,预处理,采集,缓存,索引,检索,缓存常用的查询，Cache的使用可以大大提高搜索引擎的效率。 问题

8、与挑战： Cache什么东西？ 高效的Cache调度算法？ 多级Cache： Result 缓存 Intersection 缓存 Posting List 缓存,缓存,2020/7/24,13,预处理,采集,Web搜索应用服务,索引,检索,页面解析,索引器,检索器,缓存,URL解析,链接,反向索引,PageRank,查询,Pages,www,爬虫,存储,HTML锚,基于Web搜索的应用：P2P搜索、Blog专家搜索；话题检测与跟踪；商情挖掘与推送等。 问题与挑战： 文本分类、文本聚类技术、特定信息追踪、社会网络挖掘等 高复杂度深层计算与大规模网络环境的本质矛盾 非确定性文本计算与特定需求的矛盾

9、 挑战 速度、精度与规模的统一 非确定性技术与特定需求的统一 搜索结果的挖掘与信息整合,应用界面,2020/7/24,14,分词,中文分词 将句子切成基本词汇单元 基本算法 基于字符串匹配的分词方法/机械分词法 基于统计的分词方法,企业/综合/信息/和服/务/提供商,企业/综合/信息/和/服务/提供商,错误：,正确：,难点一、歧义识别： 这个/门/把手/坏了 请/把/手/拿开,难点二、新词发现： 互联/星空/搜索 互联星空/搜索,分词质量,2020/7/24,15,索引,索引是什么？ 提供从记录的特征快速查询到记录的数据结构 倒排索引 从index term快速查询到doc的索引结构 Doc正

10、常表示为index term的集合，建立索引是把每个index term表示为其出现的doc的集合，这个过程称为inversion，即倒排。,原始文档,倒排索引,倒排,2020/7/24,16,索引创建,基本思想：排序,文档分析,文本数据,排序,词典,倒排文件,term,ptr,term,ptr,Doc1,doc2,Doc1,doc2,先term,再docid,Term编码（词典组织） 每个term用整数编码，减小存储空间 英文前缀编码(liber,liberal,liberalist) 散列表(MPH,无冲突散列） 减少磁盘的随机访问次数（大内存环境） 在内存中排序，排序结果分批写入磁盘，最

11、后合并。 两趟算法，在内存中直接倒排，小倒排文件分批写入磁盘，最后多路合并。 数据压缩,算法优化,2020/7/24,17,相关度与排序,给定一组查询词，如何选取出相匹配的查询结果？,向量空间模型,文档在词汇的多维空间中表现为向量 每一个词汇通常是一个坐标轴 文档以词汇的二进制向量形式表现 将查询与文档同样看待 查询与文档的权重基于其词汇向量的方向和长度 查询和文档两者之间的词汇向量距离，决定了与查询相关的文档的排序（距离短的相关性高）,向量空间内的文档,其中：t1, t2, t3均为一个词汇，D1D11是11个文档在该词汇空间中的对应向量,2020/7/24,18,相关度与排序,排序算法,为

12、文档词指定权重,为查询词指定权重,为指定权重的词进行比较,结果排序,权重表示形式,如果w = 0，则说明该词汇在文档和查询中不存在,权重指定方式,相关性的表示,2020/7/24,19,网页相关性的重要性分析Google PageRank核心思想,PageRank 是基于“从许多优质的网页链接过来的网页，必定还是优质网页”的回归关系，来判定所有网页的重要性。,反向链接数 (单纯的意义上的受欢迎度指标) 反向链接是否来自推荐度高的页面 (有根据的受欢迎指标) 反向链接源页面的链接数 (被选中的几率指标),因此，如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话，仅此网页

13、的 PageRank 也会一下子上升；相反地，无论有多少反向链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank 也不会轻易上升。,2020/7/24,20,搜索质量评估指标-查全率和查准率,对某个测试参考集,信息查询实例为I，I对应的相关文档集合为R。假设用某个检索策略对I进行处理后，得到一个结果集合A。令Ra表示R与A的交集。 查全率(Recall)：检出的相关文档个数与相关文档集合总数的比值，即R=|Ra| / |R| 查准率(Precision)：检出的相关文档个数与检出文档总数的比值，即P=|Ra| / |A|,R,A,2020/7/24,21,目录,互联网搜索发

14、展历程 互联网搜索基础技术 互联网搜索新技术及应用,2020/7/24,22,互联网搜索新应用,更有组织性的结果 G 利用用户信息 Google、 Yahoo的个性化搜索 Amazon A9 Search , 自动推荐系统 （协同过滤） 利用web文档结构信息 酷讯， ，车票、求职、租房等生活信息搜索(信息提取) 更自然的搜索界面 (浅层自然语言处理) 社会化搜索 ,2020/7/24,23,聚类搜索结果：vivisimo,2020/7/24,24,整合搜索：yahoo,2020/7/24,25,个性化搜索,利用用户历史搜索信息，返回更符合需求的搜索结果,2020/7/24,26,web文档结构信息抽取：购物搜索,购龙网 ,2020/7/24,27,自然语言搜索：hakia,有效性仍待提高,2020/7