精华区文章阅读

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 指南：高性能信息检索
发信站: 哈工大紫丁香 (2001年06月08日21:21:44 星期五), 站内信件

指南：高性能信息检索
Alistair Moffat (University of Melbourne) and Justin Zobel (RMIT)
文档数据库 3
相似性衡量 6
倒排文件索引 9
建立索引 9
倒排文件索引 9
倒排文件索引示例 9
倒排文件的结构 10
倒排文件的大小 10
使用倒排文件进行查询 10
分级示例 11
查询的开销 11
减小索引的尺寸 12
存储索引指针 12
整数的表达 12
ELIAS编码 12
编码字示例 13
编码字的长度 13
GOLOMB编码 13
GOLOMB编码示例 13
编码要与分布匹配 14
压缩倒排列表 14
D-GAPS编码 14
聚簇压缩 15
减少内存消耗 16
词典 16
累加器 16
“限定”(LIMIT)方法 16
“阈值”(THRESHOLDING)方法 16
性能 17
减少CPU时间 18
压缩列表的解码 18
快速倒排列表处理 18
再次压缩 18
性能 18
分块索引 19
分块结构 19
加速 19
最大值查找 19
减少磁盘访问通信量 20
文档数据库
文档数据库
用来存储报刊短文，会议记录和法律诉讼，网页，电子邮件，新闻集等…
无结构文本，可能包含某些结构属性。
一般会很庞大并且缺乏组织。
可以赋予文档一个唯一标识，但一般不作为主要的访问机制。
一般通过对内容的查询来定位所需信息。
典型的记录示例
下面是TREC文集中的一篇文档：
<DOC>
<DOCNO> AP880212-0006 </DOCNO>
<FILEID> AP-NR-02-12-88 1644EST </FILEID>
<FIRST> r i AM-CagedHens   02-12 0159 </FIRST>
<SECOND>AM-Caged Hens, 0162 </SECOND>
<HEAD> Court Rules Caging Hens Is Not Cruelty </HEAD>
<DATELINE> STROEMMEN, Norway (AP). </DATELINE>
<TEXT>
  A court ruled Friday that an egg producer who kept his 2,000 hens in small
cages was not guilty of cruelty to animals, as alleged by animal rights act
ivists.
  “The verdict is a great relief. It would have been too much to be found g
uilty of cruelty to my 2,000 hens,” Karl Wettre was quoted as saying by the
national NTB news agency after his acquittal.
</TEXT>
</DOC>
布尔查询
布尔查询（Boolean queries）中指定了一些查询项以及逻辑关系运算符（AND，OR和NO
T），集合中的每篇文档对应此查询只能有一个“真”或“假”的值：
( weather | lightning | avalanche | tornado | typhoon | hurricane | heat | w
ave | flood | snow | rain | downpour | blizzard | storm | freezing )
& ( fatal | death | die | killed | dead | injuries | fatalities )
查询项一般会被提取出相应词根（stemmed）：raining，rained，rains和rainy都被视
为rain。
典型的信息需求
两个TREC主题：
主题216：现在有哪些关于减少骨质疏松症后遗症的研究？
主题250：现有数据是否表明美国的军火销售量与枪械犯罪率成正比？
基于相似性的查询
在分级查询中的相似性试探用于访问最“相关”的文档：
weather lightning avalanche tornado typhoon hurricane heat wave flood snow r
ain downpour blizzard storm freezing fatal death die killed dead injuries fa
talities
将返回前r个“最相关的”文档。
传统的信息检索（IR）系统只支持布尔查询。但大多数用户发现分级查询更为自然，新
的信息检索系统同时支持这两种查询，有些系统则提供一种混合查询模式。
检索的有效性
有效性可以按以下方面衡量：
精度（Precision）：返回文档与查询的相关率。
查全率（Recall）：与查询相关文档的查出率。
一般当查全率上升时，精度会下降。
TREC样本
检索的有效性很难被量化！它需要三种资源：
- 庞大而逼真的测试数据库
- 示例查询集合
- 文档/查询的相关性判定
1992-1999的TREC文集包含了这三种资源，它有数个G的大小。
相关性判定是非公平的，采用一种被广泛应用于许多实际系统中的pooling方法。
TREC集合
5个1G的磁盘数据（来源于Associated Press, Federal Register, San Jose Mercury,
US Patents, Wall Street Journal, Ziff）。
1999年有100GB的文本。
400个查询或主题（到1998年为止），平均每年50个。
大约630,000个相关判定，其中73,000为“真”。
平均每个查询返回180个相关文档。
关于磁盘1和磁盘2的统计：
尺寸（MB） 2,070.84
记录数 741,856
单词数 333,338,738
取词根后的不同单词数 535,346
每个文档中取词根后的不同单词数合计 134,994,414
平均文档尺寸（KB） 2.85
最大文档尺寸（KB） 2,577.32
TREC会议
研究人员在年度TREC会议上互相交流。
在每次会议的几个月之前都会发布一批新查询（有时还会发布数据）。
研究小组会执行这些查询，给每个查询返回一个文档级别（r = 1000）。
每个查询的前100个返回文档供专业人员使用。
检索有效性结果以图表形式在会议上展示，讨论集中于如何获取最好的结果。
相似性衡量
基本参数
大多数公式中将用到以下参数：
- fd,t，基本项t在文档d中的出现频率
- fq,t，基本项t在查询q中的出现频率
- ft，包含基本项t的文档个数
- N，集合中的文档总数
- n，集合中的不同基本项总数
这些值一般会引用取过词根的基本项表，有时还会使用stop list。
“基本项”也可以是一个短语，比如“information retrieval”。
单调性
基本参数按照如下三个原则合并：
- 如果某些基本项出现在许多文档中，则赋予它们较小的权重
- 如果某些基本项多次出现在一个文档中，则赋予它们较大的权重
- 如果文档中包含了许多基本项，则赋予它较小的权重
目的是区别对待相关的文档，减少随即分布基本项的影响。
余弦衡量
一种有效的衡量方法是计算n维空间中查询向量<wq,t>和文档向量<wd,t>之间的角度余弦
。
wt = ln(1+N/ft)
rd,t = 1+ln fd,t  rq,t = 1
wd,t = rd,t   wd,t = wt × rq,t
存在余弦衡量方法的许多变种（例如，对于长查询会设定）。
典型行为
TREC磁盘2，TREC主题51-200，r=1000。
平均的11点查全率-精度值为24.1%。
改进的试探性
人们提出了多种方法来改进检索的有效性。
词典扩展方法能自动或人工地区分出查询项的同义词。
短语分析方法能自动感知查询中的短语，并尽量返回包含相同短语的文档。
相关反馈方法通过增加从高等级文档中提取的基本项来扩展查询（自动反馈），用户也
可以预先指定某些文档的等级（人工反馈）。
旋转方法侧重于规范化文档的权重，从而与训练数据的相关度更高。
分级查询的评价？
怎样计算检索的有效性？
1. 对于每个查询项t，计算wt和wq,t
2. 对于集合中的每个文档，
(a) 令Sd0.
(b) 对于每个查询项t，
  计算或读出wd,t，并且令Sd Sd+wq,t′wd,t
(c) 计算或读出Wd
(d) 令Sd Sd/wd
3. 标识出r个最大的Sd值
4. 返回r个相应文档
简单算法的缺点
需要线性扫描整个数据库，即使已经预先分析了文档也是很庞大的开销。
每个文档都要处理，但实际上只需要返回r个文档。
重要发现：在文档中至少要包含一个查询项，它的度量才不会为0。
因此应该采用面向基本项的查询评价策略。
倒排文件索引
建立索引
为了快速响应查询就要用到索引：一种将词目映射到相应文档的数据结构。例如，一本
书的索引就是将关键词映射到相应的页。
使用索引就可以快速找到至少包含一个查询词目的文档。
书的索引一般是手工建立的，而文档集合的索引必须自动建立。
那么该索引些什么呢？最好是任何东西都建立索引：所有的词，所有的数字。只有标点
符号和标记符被忽略。但以后你将会需要庞大的存储空间。
倒排文件索引
人们已经发明了许多索引类型。
对于文本检索来说，最有效的索引结构则是倒排文件：它是一个列表集合，每个词目对
应一条记录，在记录中列出了包含此词目的所有文档的标识符。
另外两种索引结构（后缀数组，签名文件）将在以后讨论。但这两种结构都不适合于通
用的查询应用。
倒排文件可被视为文档-词目频率矩阵的转置，从(d,t)转换为(t,d)，因为行优先的访问
比列优先的访问更为有效。
倒排文件索引示例
dog
      dog
      red dog
red         red dog
      red
         red
searchstructure  inverted lists mapping table records
倒排文件的结构
查找结构：对于每个不同的词目t，保存
? 指向相应倒排列表起始地址的指针
? 包含t的文档总数ft
倒排列表：对于每个不同的词目t，保存
? 包含t的每个文档的标识符d（顺序的数）
? t在每个文档d中的出现频率fd,t
存储为<d, fd,t>的列表。
另外和数组Wd一起，就可以满足布尔（Boolean）查询和分级（Ranked）查询的需要。
倒排文件的大小
对于TERC磁盘1和磁盘2，统计数据如下：
? 20MB空间用于记录535,000个词目，指针，记数
? 515MB空间用于记录134,000,000个文档标识符（每个4字节）
? 255MB空间用于记录134,000,000个文档频率（每个2字节）
一共需要790MB，大约为原始数据的40%。
检索结构类似于B-树。
每个倒排列表都是连续存储的。
使用倒排文件进行查询
为了实现一般的布尔查询，
? 取得每个查询词目对应的倒排列表
? 对于AND操作符，计算列表的交集
? 对于OR操作符，计算列表的并集
? 对于NOT操作符，计算列表的补集
? 忽略文档内的词频
对于强制连接查询，首先以最短的列表作为候补文档集合（a set of candidates），然
后从次短到最长集合，删除那些没有出现在其它列表中的文档。
为了实现分级查询，
1. 给每个文档d分配一个累加器（accumulator）Ad，并令Ad=0。
2. 对于每个查询词目t
a) 计算wt和wq,t，并提取t的倒排列表
b) 对于倒排列表中的每个<d, fd,t>
计算wd,t并令
3. 读入数组Wd的值，然后对于每个文档令
4. 识别出r个最大的Ad，然后返回相应的文档
分级示例
考虑包含两个词目“red dog”的查询，对应的倒排列表为
dog: 3,1  4,3  6,1  因此
red: 2,1  6,2   因此
数据库中共有6个文档，它们的长度（Wd）分别为
11.3 6.1  2.9  16.9  6.5  8.4
假设(1+ln1)=1，(1+ln2)=1.7，(1+ln3)=2.1，则通过倒排列表的处理可以得到累加器的
值：
red 0.0   1.4   0.0   0.0   0.0   2.4
dog 0.0   1.4   1.1   2.3   0.0   3.5
得到最终的相关度为
  0.0   0.23   0.38  0.14  0.0  0.42
查询的开销
要考虑如下资源的开销：
磁盘空间：索引大约占原始数据的40%（如果不对词目取词根，则索引约占原始数据的8
0%）
内存空间：包括每个文档的累加器，可能还有词汇表
CPU时间：处理倒排列表，更新累加器
磁盘通信量：提取倒排列表
与直接表示方法相比，这些开销可以大幅度降低。
减小索引的尺寸
存储索引指针
为什么一定要用32位（bit）或16位来存储文档标识符和频率呢？
对于N个文档，位足以存储每个文档的标识符，TREC磁盘1和2约需320MB。
相当不错，那么这是最好的方法吗？
该如何表示频率呢？
采用合适的压缩技术可以大幅度减小存储开销。
首先，让我们来了解关于整数的一些编码方法。
整数的表达
使用固定长度的二进制位来表示数字是不合适的——限制了能表达的最大数并且当大多
数数字都很小时会浪费空间。
变长位编码才是更有效的表达方法。
编码可以是无限的，从而避免了固定上界的问题。
最简单的变长位编码是unary，使用x个位来表示x>0。
根据Shannon关系，很明显unary编码对应的概率分布为，这是非常苛刻的条件。
Elias编码
实际上，unary是无限（infinite）编码方法中最基本的方法。
Elias的Gamma编码：
? 将x>0分解为2e+d，其中且0≤d<2e
? e+1用unary编码表示，d用e位binary编码表示
Elias的Delta编码：
? 将x>0分解为2e+d，其中且0≤d<2e
? e+1用gamma编码表示，d用e位binary编码表示
等等...
编码字示例
数字 Unary Gamma Delta
1 0 0: 0::
2 10 10:0 10:0:0
4 1110 110:00 10:1:00
7 1111110 110:11 10:1:11
1044 110430 11111111110:0000010100 1110:010:0000010100
2, 9, 3 10, 111111110, 110 10:0, 1110:001, 10:1 10:0:0, 110:00:001, 10:0:1
冒号和逗号只是为了清楚显示编码，在实际的位流中并不出现。
编码字的长度
到底哪种方法更好？取决于数字集合的分布概率Pr(x)。
x的值 Unary Gamma Delta
1 1 1 1
2 2 3 4
4 4 5 5
8 8 7 8
16 16 9 9
1,000,000 1,000,000 39 28
x x
Golomb编码
可能需要一种编码，它允许整数1的编码字长度大于1位？？？
在Golomb编码中，
? 将x>0分解为r·b+d+1，其中b>0是一个预定参数而且0≤d<b
? 用unary编码表示r+1
? 令且
? 如果0≤d<g，则用e-1位binary编码表示d
? 如果g≤d<b，则用e位binary编码表示d+g
因为b不一定是2的幂，用变长binary编码来表示d则不会浪费空间。
Golomb编码示例
数字 b=1 b=3 b=8
1 0: 0:0 0:000
2 10: 0:10 0:001
4 1110: 10:0 0:0111
7 1111110: 110:0 0:110
1044 110430: 13470:11 11300:011
2, 9, 3 10, 111111110, 110 0:10, 110:11, 0:11 0:001, 10:000, 0:010
那么该如何选取参数b呢？
编码要与分布匹配
当时，采用Unary编码是最小冗余编码（一种Huffman编码）。
当或时，Gamma和Delta编码是最小冗余编码。
当时，令，则Golomb编码是最小冗余编码，其中p是几何分布的参数（Bernoulli试探
序列的成功概率）。
压缩倒排列表
每个倒排列表是一个<d, fd,t>序列。
频率常常非常小（一般为1或2），可以用Unary或Gamma编码有效表示。
但是使用这些编码来表示文档标识符则效率不高，因为平均值为N/2，需要用约log2N位
来表示。
不过如果文档标识符是顺序的而且只保存步长（d-gaps），就可以节省大量空间。
d-Gaps编码
ft 个文档编号序列为 7, 18, 19,. 23, 25, 63, ...
用步长来表示为  7, 11, 1, 3, 1, 2, 38
其中，如果词目在文档中是随机出现的，步长就符合几何分布（参数p=ft/N）。
这些步长就可以用Golomb编码有效表示。
对于TREC磁盘1和2，采用Golomb/Gamma编码的索引（包括所有的单词和数字）占用约13
0MB（小于7%）空间。
非随机的词目分布
如果文档是按年代顺序存储的，则词目的分布就会出现聚簇。
在TREC的Associated Press中包含了242,918个文档，其中对于“hurricane”就存在两
个明显的聚簇：
聚簇压缩
？？？
压缩的pros和cons
优点：
? 减少索引所需磁盘空间
? 减少传输开销，减少磁头定位次数
? 更为有效的索引构造（在下文中详细讨论）
缺点：
? 在使用倒排列表前必须解压
在台式机上处理开销主要包括磁盘定位（文件更小）和传输（记录更小）的开销。
因此，如果索引比可用内存更大且无法缓冲的话，压缩的缺点将不复存在。
减少内存消耗
词典
内存的消耗包括：词典和累加器。
词典的主要部分可以放在磁盘上，用索引块的形式保存。
甚至对于“海量”数据库都可以仅用一次磁盘访问找到某个单词。
可以用前端编码（front-coding）来保存单词块，以减少磁盘存储空间。
例如，如果在一块内有8个单词：
7,decease; 8,deceased; 8,deceases; 9,deceasing;
8,decedent; 9,decedents; 6,deceit; 9,deceitful;
前端编码为：
-,7,decease; 7,1,d; 7,1,s; 6,3,ing; 4,4,dent; 8,1,s; 4,2,it; 6,3,ful.
累加器
对于标准查询算法和经典的长查询来说，大多数累加器是非零的，数组是空间和时间开
销上最为有效的结构。
但是大多数累加器的值都特别小——除非被查询的单词是个常见词。
如果只对wt的值比较大（即罕见）的词目创建累加器，则可以大幅度减少累加器的数目
。
可以通过限定累加器的数目L来实现。
“限定”(limit)方法
1. 创建一个空的累加器集合A
2. 对于每个查询词目t（按wt的值递减排序），
a) 计算wt和wq,t，并提取t的倒排列表
b) 对于倒排列表中的每个<d, fd,t>，
i. 如果d没有累加器且|A|<L，则为d创建一个累加器Ad
ii. 如果d有累加器则计算wd,t并令
3. 对于每个累加器，令Ad=Ad/wd
4. 标识出r个最大的Ad，然后返回相应文档
“阈值”(thresholding)方法
1. 创建一个空的累加器集合A
2. 对于每个查询词目t（按wt的值递减排序），
a) 计算wt和wq,t，并提取t的倒排列表
b) 对于倒排列表中的每个<d, fd,t>，
i. 计算wd,t
ii. 如果d没有累加器且，则为d创建一个累加器Ad
iii. 如果d有累加器则计算wd,t并令
3. 对于每个累加器，令Ad=Ad/wd
4. 标识出r个最大的Ad，然后返回相应文档
性能
当L≈文档总数的1%-5%时，对于TREC类型的查询，减少内存开销不会影响检索性能。
限定方法使得你可以直接控制内存的使用。
阈值方法允许为常见词目创建累加器（如果它在文档中有足够多的出现频率），而不管
你已经处理了多少词目。
在阈值方法中，如果在查询处理中S是递增的，那么新文档就很难进入前r位，因为要处
理更多的词目。
改进的方法是首先递增累加器，使之趋向于L，然后在处理后续词目时递减使之趋向于r
。
减少CPU时间
压缩列表的解码
对于简单查询，每个查询词目的倒排列表将被完全地提取和处理。
这就是说，每个<d, fd,t>都会影响累加器的值。
而在限定累加器的查询实现中，大多数<d, fd,t>并没有对应的累加器，因此对它们解码
完全是在浪费时间。
但是由于已经被压缩，每个数字都是用变长位存储，因此对倒排列表随机访问（二分法
查找）是不可能的。
快速倒排列表处理
通过增加有限的附加信息，就可以进行伪随机访问。
一种方法是在倒排列表中嵌入指针（skips）。使用这些指针就无须解码其间的内容。
再次压缩
下面是文档号和词频的序列：
12,2  17,2  29,1  32,1  40,6  78,1  101,3  106,1  110,3  216,...
为每三对增加一个指针：
p1 : (32, p2)  12,2  17,2  29,1
p2 : (101, p3)  32,1  40,6  78,1
p3 : (216, p4)  101,3  106,1  110,3 ...
这样就可以删除冗余信息并用步长（differences）方式存储：
p1 : (32, p2 -p2)   12,2  5,2  12,1
p2 : (69, p3 -p2)   ,1  8,6  38,1
p3 : (115, p4 –p3)   ,3  5,1  4,3 ...
性能
被加码对的个数是跨度（skip length）的一个函数。
如果要从列表中提取很多d的值，那么使用长块就意味着几乎所有块都要被解码。
如果只需提取少量d的值，那么使用短块意味着要处理过多的指针。
如果已知列表长度以及累加器数目的估计值，块的长度可以被预先计算，从而尽量减少
整个处理时间。
实验表明处理时间与块的长度密切相关——它决定了极小开销。
对于TREC磁盘1和2，索引的大小将从7%增加到9%，但查询时间则减少差不多一半。
分块索引
如果在倒排列表中使用相同长度的分块，就可以使用二分法查找，而不必线性查找。
每个块内会包含未使用的位，但这种开销是可以接受的。
在二分法查找中，每个块的边界文档号（Critical document number）的编码与相临块
的前导文档号相关。
在每个块中，可以采用Rice编码代替Golomb编码，分开存储unary部分和binary部分。
在查找候选文档时，对合并的unary编码部分按字节操作处理。
与递减累加器试探相结合，可以提高速度。
同样的技术可用于布尔查询。
分块结构
文档频率被分离，并在块尾反向编码存储。边界文档号存储在列表的头部。
块的个数    边界文档号    每块的指针个数
     第1块          第2块
      编码依赖     浪费空间
加速
检索速度由低到高依次为：compressed/continue, skipped/continue, random/decrea
se
最大值查找
当r<<N时，就算限制累加器的个数，对累加器完全排序也需要很大开销。
叠代查找最大值同样开销很大，除非r非常小。
推荐使用包含r个最小值的最小堆结构：
减少磁盘访问通信量

--


<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]

Algorithm 版 (精华区)