信息检索中效率问题的研究.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息检索中效率问题的研究,1,信息检索(,IR),的基本概念（一）,信息检索和数据库管理系统(,DBMS）,的区别：,DBMS,处理对象是结构化数据，,IR,处理大量的非结构化数据。,DBMS,只是管理数据，,IR,要管理数据的内容内容管理（,content management）。,DBMS,的每次事务的结果是确定的，,IR,系统的任务是找到用户需要的信息，其结果是不精确的。,2,信息检索(,IR),的基本概念（二,）,信息检索的两大问题：效率(,efficiency)、,效果（,effectiveness）。,效果指标：查准率(,precision),和查全率（,recall）。,效率指标：响应时间(,response time),和吞吐量（,throughput）。,文本信息检索效果的提高依赖于自然语言处理(,NLP)；,信息的指数增长使得检索效率也成为不可忽略的问题。,3,信息检索(,IR),的基本概念（三,）,信息检索系统的组成部分：,4,信息检索(,IR),的基本概念（四,）,基本用户查询(,query):,逻辑操作(,AND,OR,NOT)。,位置邻近查找(,Proximity Search),短语查找(,Phrase Search)。,对原始信息创建索引加快检索速度：,Inverted file,signature file,等。,倒排文件是最广泛使用的技术，它组织结构灵活，可以满足多种查询方式。,5,对文档的预处理,在英语等语言中做“,stem”,索引单词的“主干”。可以提高查全率，降低查准率。,汉字之间没有空格，可以对汉字字符索引，也可以索引做切词处理后的词组。,现代汉语中大部分是两个字的词组，单个的字符表示的意义很不确定，所以对词组建索引可以提高查询的效果。切词对查询效率也有重大影响。,6,倒排文件的组织,将文档分割成独立的单词项(,term),按单词项索引形成倒排文件。,单词,t,j,对应的,posting lists,是,(,d,i,f,i,a,*,)+(di+k,f,i+k,a,*,)+,，,f,i,表示,t,j,在,d,i,的出现次数，也是后面,a,的数量。这是倒排文件的全文本索引,(,full-text inverted file),形式,它记录了每次出现的位置等信息，要占用较多的存储空间。如果去掉位置信息，仅可以支持逻辑查询形式。,7,词典的组织（一）,索引单词项的集合构成词典，系统通过查找词典定位该单词对应的,posting lists，,这是从单词到指针的映射。有两种词典的组织方式：,直接用,B+,树等方式组织单词的字符串。,用哈希（,hash）,的方式速度更快，可以将所有单词装入内存中。,8,词典的组织（二,）,“天网”中用哈希的方法实现从单词字符串到单词标识(,TermID，,整数)的转换，单词的标志是在每次创建索引是赋予的（不是固定的），所有单词的标志是从零开始的连续整数。,如果维护一个全局稳定的词典（固定单词的标识，便于维护），系统的,TermID,可能成为稀疏的整数，可以组织成,B+,树实现从,TermID,到指针的映射。,9,数据组织（一）,倒排文件中单词对应的,posting lists,部分必须存储在磁盘中，不同单词的,posting lists,长度差别很大，可以区别对待。,存储管理的方法在,DBMS,已经有深入研究。在倒排文件中，每个单词的,posting lists,的访问模式是顺序扫描,（,sequential scanning,）,，作为一个对象看待最合适。关系数据库管理系统（,RDBMS）,用于倒排文件的缺点是不太灵活，而且,SQL,语句的开销比较大。,10,数据组织（二,）,面向对象的概念更能简洁地描述倒排文件的结构，采用面向对象数据库系统（,OODBS,）,是更好的选择。下面是两个被一些,IR,系统使用的例子：,用持久对象存储（,Persistent Object Store,）,Mneme,管理倒排文件，,Mneme,不但提供基于对象的数据缓存和良好的磁盘空间分配策略，还可以用它高度的可扩展性，根据数据的特性定制存储。,ObjectStore,是商业上最成功的面向对象数据库系统之一，它用内存映射技术实现持久对象存储，和程序语言（,C,C+,JAVA,）,完全集成，既有程序设计语言的灵活，又可以高效的存储数据，是另一个很好的索引管理工具。,11,数据组织（三,）,“天网”中用多个文件实现倒排文件的存储，优点是实现简单，可以利用文件的缓存机制，缺点是灵活性差，效率也有所损失。,嵌入式数据库系统,Berkeley Database,（,Berkeley DB,）,是一个开放源代码产品，它提供简单高效的功能（三种访问方法,B+tree,hash,recno,），,实现,key/value,的存取，这已完全能满足索引管理的需求，可以替代,OODBS,（在,WebBase,项目中使用）。,12,实现倒排表的随机访问,高频词（,Term,）,的,Posting lists,长度通常,1,Mbytes,以上（随着文档数据库规模增大，它会快速增长），称作,“,long Posting lists”,。,如果对它作顺序访问，从磁盘读入内存会耗费很长时间，同时占用系统大量的,I/O,带宽，从而降低整个系统的吞吐量。解决的方法是将对,long Posting lists,的顺序访问变成随机访问（,random access Posting lists,）,long Posting lists,被按照,“,文档号,”,分割成长度较小的数据块，在,“,AND”,和,“,Proximity search”,操作时可以有选择地访问部分数据，不可能相关的文档所在数据块被,“,跳过,”,（,skip,）。,它增加了按照,“,文档号,”,索引数据，以空间换取时间。,13,信息检索的缓冲区管理（一）,利用文件系统的缓存往往不能得到最佳的性能，根据,Posting lists,的顺序访问模式，可以采用基于对象的缓存，对象持久存储中的双向缓冲区将对象和分页缓存结合起来，是一种更佳的策略。对很高频的单词，由于它对查询准确度的提高很有限（有些系统将它们作为,stopword,忽略，不建索引），缓存整个它的,Posting lists,将占用大量内存，少量的高频词就可以耗尽所有的内存,，所以缓存高频词的,Posting lists,将得不偿失。采用,random access Posting lists,算法，可以将大对象分解成小对象，缓存对小对象的索引数据，提高内存使用效率。,14,信息检索的缓冲区管理（二）,J,nsson,Bj,rn T.,Franklin,Michael J.and Srivastava,Divesh.Interaction of query,evaluation and buffer management for information retrieval.,研究了信息检索中缓存管理和查询的相互作用关系，作者提出两种查询时优化利用缓存的策略：,buffer-aware query evaluation,和,ranking-aware buffer replacement,，,前者在查询时优先使用在缓存中的数据来减少读磁盘，后一种技术将数据的语义引入到缓存的替换中，例如关键词的,Posting lists,要被顺序扫描，每次都必须访问第一个数据页，最后一页则未必需要，所以就应该尽量保持它的第一页在内存中。,15,查询处理中的,Fast Ranking,技术,主要思想：不检索出全部结果集，只需找出现面,K,个结果,Retrieve partial document allowing error，,要和相关度评价算法（,ranking algorithm）,结合。,对数据存储的要求是在每个单词的,Posting lists,中要按照频率排序（认为单词在文档中出现频率越高，相关度越大）,Filtered Document Retrieval with Frequency-sorted Indexes。,由于只需读取部分数据，可以极大提高检索效率。,16,倒排文件压缩（一）,影响倒排文件查询效率的主要是关键词的,Posting lists,，,所以必须压缩它的长度。压缩以后减少了内存、磁盘空间的占用和,I/O,带宽的使用，同时要对数据编码和解码，增加了,CPU,时间耗用。考虑到,I/O,是系统的瓶颈，,CPU,和,I/O,之间不断扩大的性能差距，以时间换取空间是可行的。压缩不仅能提高查询时的效率，还能加快创建索引，从各方面提升系统性能。,17,倒排文件压缩（二）,关键词对应的,Posting lists,是整数的序列，包含文档号（,d,）、,关键词在文档中的频度（,f,）,和关键词在文档中的一系列出现（,a,）。,压缩的方法首先基于,“,游程编码,”,（,run length coding）,增量整数序列被变换为差分序列（原来相邻整数之间的增量序列）。由于,Posting lists,中文档号,d,和出现位置,a，,都是递增排列，故可以做,“,游程编码,”,变换。游程编码本身并不能实现压缩，只是较大的整数被变换成了较小的整数（频度,f,本来就是小整数）。,18,倒排文件压缩（三）,字节对齐索引压缩（,Byte Aligned Index Compression,）,字节对齐索引的优点是容易编码和解码，位操作少，占用,CPU,时间少，缺点是对很小的整数压缩率低，每个整数最少用一个字节的空间。,变长索引压缩（,Variable Length Index Compression,）,一元编码（,unary）、,编码和,编码,进一步优化的方法是根据整数序列的平均游程长度（,mean run length）,对位向量编码增加参数，称作,“,局部模式,”,。比较简单的一种方法是：一个整数序列的个数是,p,w,，,则它的平均游程长度是,N/p,w,，,设,b=0.69N/p,w,，,取,V,G,=(b,b,b,),作压缩向量，前缀用一元编码，后缀是二进制编码（占用个位）。,19,倒排文件压缩（四,）,在非全文索引中，,Posting lists,由文档号,d,和文档中的词频,f,组成，一个（,d,f,）,平均用,1,个字节即可表示；单词,t,的,Posting lists,平均长度可以根据,t,的,IDF,推算出来。,在全文索引中，单词出现的位置信息占据索引数据的主要部分，所以忽略文档号,d,和文档中的词频,f,。,用变长压缩算法，单词出现位置平均可以用少于,8,bit,的位表示。设全部文档分词后的单词总数是,T,N那么单词,t,总的出现次数是,T,N,*TF,，,它的,Posting lists,平均长度小于,T,N,*TF,字节。,20,结论（一）,用户的大部分查询中的单词数量比较少，查询一个主题时用2-3个单词就可以描述，查询文章的题目时可能有10个单词以上。不妨设,Lq,表示用户查询中的单词个数，估计平均,Lq,等于5。根据前面得出的现在一个磁盘的,IOPS=100，,可以计算出在不考虑数据缓存情况下，系统平均每秒钟处理查询的上限是,IOPS/Lq=20。,根据磁盘的可用带宽大约是20,MBytes/s，,得出每个查询的,I/O,应不大于1,Mbytes，,也就是满足如下条件：,T,N,*TF*Lq1MB。,代入以上得出的估计参数，有如下结论：,l,对汉语字符：,T,N,400MB（TF=0.05%，Lq=5）,l,对英语单词：,T,N,4GB（TF=0.005%，Lq=5）,21,结论（二,）,由于汉语的一个字符占两个字节，所以如果对汉语字符建索引，要维持每秒,20,个查询的系统吞吐量，只能索引,800,MB,的文本数据库。英语的一个单词平均占用字节,6-8,个（包括空格符），故同样情况下可以索引,24-32,GB,的英语文本。,汉语切词后,关键词的平均频率达到和英语相近的水平,。,在,“,天网,”,的检索系统中，使用北大计算语言学研究所开发的切词程序（共收录了7.3万词条），切词后对词组建索引。,日本的中日韩词典研究所,41,构建的汉语词典有,260,万的简体和繁体词条，包括,60,万的一般词汇（简繁各,240,000,）和科技术语，,200,万的人名、地名和公司名称等，它对,GB-2312,的词频统计显示在第,100,个词频率已经下降到,0.05%,。,22,结论（三,）,单机系统支持的检索系统规模在,Gbytes,级，更大规模的数据必须使用分布并行系统。,“天网”。,Google。,分布式解决了规模问题，但是系统的吞吐量和并发度仍受限于,I/O,这个瓶颈。,可能必须用内存数据库，将所有数据载入内存，去掉,I/O,限制。,23,