15.搜索引擎-倒排文档ppt课件

搜索引擎数据库存储结构,(1)存储爬虫采集的网页的主要目的，是为了响应用户的检索。由于数据的存储结构直接影响着查询效率，所以研究网页的存储结构是一个不可忽视的问题。(2)文本检索的演化进程大致如下：全文扫描(Fulltextscanning)、文件签名(SignatureFile)和倒排文档(Invertedfile)。,搜索引擎数据库存储结构,全文扫描是一个顺序查找过程，在这种搜索模式下，人们已经研究出多种关于字符串匹配的算法，比如KMP算法、Boyer-Moore算法以及FSA算法等等。优点：便捷的文本插入和更新，而且不需要额外的存储空间，其最大的缺点是较差的检索响应时间,搜索引擎数据库存储结构,文件签名方法通过把原始文档转化为签名文档，很大程度上减小了文档的长度，来加快查找速度由于这种方式仍旧是顺序查找，所以并没有从根本上改变响应不够灵敏的缺点。,搜索引擎数据库存储结构,随着需要处理的文本逐渐增多，针对这种情况，人们开始把文档中的关键词建立索引，并在索引后面记录该关键词的信息(比如文档标识，关键词的位置及其权重等)，这种检索模式可以满足在大语料库中快速查询。,倒排文档,倒排文档起初的做法是把文档中的关键词(KeyWord)建立索引，后来为了满足对任意检索单位检索的需求，逐渐形成了全文检索模式(ruUtextretrieval)，即对文档中的所有单词建立索引，由于中文的词语切分、概念切分还没有很好地得到解决，所以大都采用了单汉字标引技术,倒排索引,这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(invertedindex)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(invertedfile)。在搜索引擎收集完数据的预处理阶段，搜索引擎往往需要一种高效的数据结构来对外提供检索服务。而现行最有效的数据结构就是“倒排索引”。,倒排索引,倒排索引的生成过程如图：,倒排文档的结构,倒排文档，一个倒排文档由两个部分组成：索引文件(IndexingFile)：索引文件中的每一个条目(Item)对应文献中的一个可检索单位。后缀文件(PostingsFile)：每一个后缀文件则记录包含该索引单位的文献信息以及其它相关信息(比如索引在文献中的权值）建立索引文件时，根据中文的内码特点，可以方便地把所有GB2312的汉字哈希到一个94X94的二维数组，使查询时快速访问到索引文件中的索引项,倒排文档结构的改进,倒排文档的存储结构，直接决定了搜索引擎系统的检索速度，并且在一定程度上也影响到检索结果的准确度。网络上的网页繁多，更新迅速，而且信息冗余量大。对数据存储方式的改进也正是根据这些特点,倒排文档结构的改进,中英文自动摘要对Spider搜索到的每个网页做200字的摘要。建立全文索引是对每一篇摘要建立索引，而非原始文本。因为摘要中的字词能够更有力地表达网页的主题，检索结果当然也就更准确。另外摘要的篇幅比原文短，可以大幅度减小后缀文件的大小，从而提高检索效率。统计结果表明，新浪、新华网、中国新闻网三个网站的新闻平均纯文本大小是435k字节(17，386个文件的大小是75，695，220字节)。因此200汉字的摘要是原文长度的110。,倒排文档结构的改进,对于索引文件和后缀文件结构的改进建立索引文件时，如果以单汉字作为标引项，可以简化标引难度，并且可以在处理检索时能够采用统一的规则，而且能够检索任意字符串。但是这种方式也有明显的缺点：(1)单汉字与文档间的相关度难以精确计算仅仅依赖汉字出现频率来计算汉字在文档中的权重并不恰当一篇标题为“各种马的区别”的网页中，“马”这个字出现次数非常多当用户检索“马大哈”这个条目时，如果根据单汉字方式处理，把这个网页当作一个比较符合要求的结果返回，显然不能让用户满意,倒排文档结构的改进,对于索引文件和后缀文件结构的改进(2)汉字间错误的组合导致不符合要求的检索结果完全基于汉字的处理方式，总是不能避免如下的错误查询“天真”返回了包含“今天真热”的文档在著名的搜索引擎Google中，返回的结果第5条就是以“事发十天真相难明”为标题的网页(2002年)查询“明天”返回了包含“小明天天迟到的文档，查询“如果”返回包含“薯片不如果冻好吃”的文档查询“和服”返回结果中包含许多“电脑的销售和服务之类的网页,倒排文档结构的改进,对于索引文件和后缀文件结构的改进为了解决上述两个问题，必须把网页提升到概念的层面来处理处理方法是：先把搜索到的网页解析出纯文本，进行概念提取，对于没有被词典中的词切分出的汉字组合，去掉停用词之后(根据停用词表)，按照单汉字建立索引。这样最终建立的索引文件既有基于词的索引，也保留了单汉字标引。考虑到汉语词的数目巨大，不可能对所有词都建立索引。250个常用词的覆盖率即可达到50以上，5000常用中文词的覆盖率即可达到91.67，8000常用词的覆盖率可达95.13。据此对8000常用词建立索引,例子,以英文为例，下面是要被索引的文本：T0=itiswhatitisT1=whatisitT2=itisabanana“,我们就能得到下面的反向文件索引：a:2banana:2is:0,1,2it:0,1,2what:0,1,检索的条件what,is和it将对应这个集合：,例子,以英文为例，下面是要被索引的文本：T0=itiswhatitisT1=whatisitT2=itisabanana,得到带起始位置的反向文件索引：a:(2,2)banana:(2,3)is:(0,1),(0,