当前位置: 首页 > >

信息检索??索引构建

发布时间:

索引构建

?


本章内容:


    硬件基础语料库大规模倒排索引构建

? ? ? ? ? ? ? ? ? 基于块的索引构建BSBI


? ? ? ? ? ? ? ? ? 内存式单遍扫描索引构建SPIMI


    分布式索引MapReduce动态索引

?


目录


索引构建


硬件基础


语料库


大规模倒排索引构建


基于块的排序索引BSBI


内存式单遍扫描索引SPIMI


分布式索引MapReduce


动态索引






?


索引构建:建立倒排索引的过程index construction


索引器:构建索引的程序或计算机indexer


?


硬件基础
    访问内存数据比访问磁盘数据快得多。

我们尽可能的把数据放在磁盘中,特别是访问频繁的数据


高速缓存caching:将频繁访问的磁盘数据放入内存的技术


    寻道时间:进行磁盘读写时,磁头移到数据所在的磁道需要的一段时间,寻道时间并不进行数据传输硬盘为什么读取时那么慢??移动磁头。

硬盘:定位数在哪,移磁头(多出了寻道时间,慢),读数据


内存:没有磁头(没有寻道时间,快),直接读。


    提升硬盘的读取速度:传输连续的数据块。

想读100M数据,硬盘这100M数据分成了10个10M的放在不连续的空间。


举例:


读:移动了10次磁头??慢


磁头移动到第1个块,读10M


磁头移动到第2个块,读10M


..


磁头移动到第10个块,读10M


假设这100M数据是连续的(放在一起)??硬盘读连续数据会快很多。


移动1次磁头,读100M数据。


    操作系统往往以数据块为单位进行读写。因为,从磁盘中读取一个字节和读取一个数据块所耗费的时间可能一样多。数据块的大小一般是8KB-256KB

缓冲区buffer:内存中保存读写块的区域


7. IR系统的服务器往往有数G字节甚至数十G字节的内存.


8.可用的磁盘空间大小一般比内存大小要高几个数量级.


9.系统容错非常昂贵: 使用许多普通服务器比使用一台容错服务器要便宜得多.


?


?


语料库

自然语言处理,需要语料库。



词条:从原文切出来


词项:归一化处理,进入词典


词典:储存词项的数据结构


?


?


大规模倒排索引构建

关键点??排序??需要空间来排序。


1.数据量小,内存中足够放下所有的数据进行排序,第一章索引构建算法可用。


2.数据量大,内存放不下?怎么排序?普通排序算不能用,第一章的算法不能用,需要新的算法来解决内存放不下所有数据的问题。


大型文档集无法在内存中完成索引构建,因此中间结果保存在磁盘。


?


基于块的排序索引BSBI

BSBI基于块的排序索引算法(blocked sort-based indexing)


基本思想:


内存放不下所有数据,所有数据分为10块,每一块读到内存中按第一章的算法来构建索引。最后,合并10个结果 ,得到最终结果。


缺点:在内存中保存了一份词项到词项ID的映射,太占空间。


BSBI:文档本来就需要编号(使用4字节存储) 把词也编号,brutus给个编号1


    对词项ID??文档ID进行排序将具有同一词项ID的所有文档ID放到倒排记录表中,其中每条倒排记录表仅对应一个文档ID将基于块的倒排索引写到磁盘上


?


词的编号? 文档编号


1????? ?? 1????? 2


块1:中把python设定为3


文档1:Hello World Hello Python


hello 1


world??????? 2


python????? 3


....?


词id 文档id


1????? 1


2????? 1


3????? 1


?


块2:


i wrote python


同一个词即使不同块,也要使用同一编号


分块后内存放得下,可以按第一章的方法来完成。


?


BSBI相对第一章算法的区别:


1.分块


2.词项进行编号,需要在内存中存储这个词项与编号的映射


需要不同的块同一个词要使用同一编号,


?


缺点:在内存中维护一个词项??词项id的映射,占空间太多。


?


每个块按第一章算法来构建倒排索引。每处理完一个块的倒排索引后,先写到磁盘连续空间。


当所有块处理完后,得到10个块的倒排索引。需要合并。



分块??合并



算法:


?


算法解释:


1.n是块的个数,初始化为0


2.所有文档没处理完时继续循环


3.n要增1


4.读取一个块直到放满 一个块空间


5.用BSBI算法处理这个块,得到中间倒排索引


6.把中间结果写入磁盘


7.合并所有的中间结果 。


?


?


内存式单遍扫描索引SPIMI

内存式单遍扫描索引构建方法SPIMI(single-pass in-memory indexing)


?


方法思想:


    为每个块单独生成词典,无需词项ID无需对词项-文档ID进行排序,当每个倒排表出现时即可计算每个块生成完整的倒排索引,每个块对应的索引合并成一个

?


?


算法:



SPIMI-Invert:SPIMI构建倒排索引的算法


伪代码:


token_stream:词条(文档中切出来的)流。


?


1.新建文档叫output_file


2.创建一个哈希表叫dictionary


3.while(有可用的内存就一直循环)


4.从词条流中取出下一个词条放在token中


5.判断term(token)是否属于词典(是否不存在于词典)


term(token):将词条处理为词项


6.如果词典中不存在该词项,把词项添加到词典,返回了倒排表postings_list


7.如果词典中存在该词项,把该词项对应的倒排表取出放在postings_list


8.倒排表是否己满


9.如果满了,申请双倍空间再赋给postings_list


10.把词条所在的文档编号添加到倒排表


11.对词典进行排序


12.把当前块写到磁盘(排好序的词条,词典,输出中间结果)


13.返回中间结果


SPIMI压缩


压缩使SPIMI更高效


    词项压缩倒排表压缩

?


BSBI算法与SPIMI算法


BSBI算法:把词项映射为词项ID占空间。


SPIMI算法:不要那个映射,没有词项ID


分块:记录(词项,文档ID)


区别:BSBI算法块内使用词项ID,SPIMI算法直接存储词项。


优点:不需要在内存中保留那个词项到词项ID的映射。


?


?


分布式索引MapReduce

Web搜索引擎通常使用分布式索引


(文档集非常大时,在单台计算机上很难高效地构建索引,对web构建规模合理的索引通常需要大规模的计算机集群cluster。)



?


Master-Slave模式主控节点(Master)负责处理索引工作 ? 假定主控节点是安全的.将索引任务划分成并列的子任务块.主控节点将每个子任务块分配给集群中的空闲节点(Slave).并行任务可分为两类
分析器??Map 拆倒排器??Reduce 收集、排序、写入最终倒排表

动态索引


1.迄今为止,我们都假设文档集是静态的.


2文档集:



每时每刻都会出现新文档,这些新文档应当被插入.文档经常被更新或修改.

思想方法:


1.维护一张大的主索引


2.新文档加入到小的辅助索引中


3.检索时可以同时遍历两个索引并将结果合并


4.周期性将辅助索引合并到主索引


5.删除记录 文档的删除记录在一个无效位向量中,在返回结果之前可以利用无效位向量过滤掉己删除文档


?


缺点


主索引太大了,合并起来开销大。


?


?


算法



LMergeAddToken


indexes:所有的I系列索引。


Z0:内存中的临时索引


token:词条


||:不是绝对值,而是指Z0的长度或大小


1.新的文档(词条)写入Z0


2.判断Z0满了(判断限定的大小,Z0如果已经达到了n的大小就是满)没有


3.死循环,


4.判断Ii是否存在(indexes中是否有Ii)


5~7:如果己存在


5.将Ii与Zi合并为Zi+1


6.一条注释


7.合并后要清空了Ii


8~10:如果不存在


8.直接把Zi写到Ii


9.把Ii添加到indexes中


10.只要数据写入硬盘后就可以结束循环break


11.清空Z0


?


LogArithmicMerge:


1.初始化Z0为空


2.初始化indexes为空


3.死循环,调 用LMergeAddToken


?


?


动态索引

动态索引:很多小的索引文件,但文件数并没有很多。


?


有两组索引:


n???? 2n?? 4n?? 8n?? 16n


I0??? I1??? I2??? I3??? I4....??放在硬盘上,有些是永久的,有些是临时性索引。


Z0?? Z1?? Z2?? Z3?? Z4....??放在内存中,都是临时性索引,肯定会被删除。内存中的东西一旦被写入硬盘就可以清空。


?


原理:


新文档进来??存入内存??内存满时??判断是否在硬盘中存在


    不存在:直接写入硬盘,内存中的删除存在:两者合并,内存和硬盘原来的都要删除

注意:内存和硬盘都是有大小限制的


Z0满判断L0,Z1满判断L1,相对应


?


举例:


1.Z0满,判断I0是否存在,现在I0不存在,把Z0写入I0,把Z0清空,现在的索引变成以下的状态


2.新文档继续进来还是写Z0,假若Z0又满了,判断I0是否存在,现在是存在,Z0与I0合并成为Z1,然后把Z0与I0清空,


?


3.此时Z1已经达到了限制的大小2n,相当于Z1己满 ,判断I1是否存在,不存在,直接把Z1写到I1,把Z1清空


4.新文档进来,还是写Z0,Z0满了后判断I0是否存在,不存在直接把Z0写入I0,


5.新文档进来,总是写Z0,满了判断I0是否存在,合并成Z1(合并后记得清空),Z1此时也满了,判断I1是否存在,存在合并为Z2,Z2己满,


规则:不存在,直接写入;存在,合并后总是先写Zi,不断循环,直至把数据写入硬盘就可以停止


Zi满了


1.判断Ii是否存在,如果不存在写入硬盘后停止循环;


2.判断Ii是否存在,如果存在,合并为Zi+1,不断的循环直至写入硬盘后停止循环


关键:合并后/写入硬盘后记得清空。


?


?


PPT4√


Note10.14×



友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网