索引和搜索IndexingandSearching.ppt

各种编码方式（一)
一元编码（Unary Code）
一个数n由n-1个1跟着一个0组成
以n=9为例，111111110
n占用的空间为 n bit
γ(Gamma) Code
联合unary编码和二进制编码binary codes
unary 编码 存储 用二进制编码表达n所用的位数，二进制编码 存储 用于恢复n的信息
unary 编码占用存储空间为 1 + |_log n_|，binary 占用存储空间为|_log n_|，存储的数为 n - 2 |_log n_|
以n=9为例，|_log 9_| = 3, so unary code is 1110，9-8=1, so binary code is 001，其编码为 1110 001 (7 bits)
n占用的空间为 1 + 2 * |_log n_|
索引和搜索IndexingandSearching
1
各种编码方式（二）
δ(delta) Code
用γ编码 编码 γ编码的长度部分
以n=9为例，其γ编码的长度为4，4的γ编码为 11000，故9的δCode为 11000 001
n占用的空间为
Golomb 编码
前 q+1 用 unary编码, q=|_(x-1)/b_|
余数 r=x-q*b-1 用二进制编码，需要 或 位，如果 r<2 |_logb_|-1，在二进制编码中需要 位，否则需要 位，其中第一个位为1。若b=3，则r=0 (0)、 r=1 (10)、 r=2 (11)
b取3，以n=9为例，q=|_(9-1)/3_|=2，故其unary编码为 110， r=9-2*3-1=2，故其二进制编码为 11，故9的Golomb编码为11011
索引和搜索IndexingandSearching
2
7. 索引和搜索Indexing and Searching
倒排文件构建Inverted Files Construction
搜索Searching
索引和搜索IndexingandSearching
3
索引大小
在第一讲我们初步研究了索引空间
同时也考虑了 stemming, case folding, stop words ...
提取词根等操作对于索引大小的影响如何？
索引和搜索IndexingandSearching
4
索引大小
词根化和小写归一化处理能够降低
词的数量降低 ~40%
指针的数量降低10-20%
总空间大小降低 ~30%
停用词
Rule of 30：大约30个最常见的词占了书面文字中所有词的30%
从索引里消除150个最常见的词能够降低大约25%的索引空间
索引和搜索IndexingandSearching
5
包含位置信息的索引大小
需要每个出现位置有一个条目, 不是一个文档一个条目
索引的大小取决于平均文档大小
Average web page has <1000 terms
filings, books, even some epic poems … easily 100,000 terms
考虑一个出现频率为 %的词(所需条目空间如下表所示)
100
1
100,000 words
1
1
1000 words
Positional postings包含位置信息的记录
Postings一般记录
Document size
索引和搜索IndexingandSearching
6
经验性的规律
包含位置信息的索引positional index大小大概是只包含出现情况的索引non-positional index的 2-4倍
包含位置信息的索引平positional index大小大概是原始文本的35-50%
一些商用软件也称此比率为膨胀率，并用它作为衡量搜索引擎效率的一个重要指标
以上这些数据主要是对英文类似的语言有效
索引和搜索IndexingandSearching
7
索引构建
索引的空间
索引建立的时间
有限内存情况下采用怎样的策略建立和维护索引?
索引和搜索IndexingandSearching
8
对于比较大的语料库
Number of docs = n = 40M
Number of terms = m = 1M
用齐普夫率 Zipf 来估量记录条目的数量
n + n/2 + n/3 + …. + n/m ~ n ln m = 560M entries
在不包含位置信息的情况下, 每个条目10-12 bytes （term, doc, freq）
索引和