索引压缩
目录
索引压缩
：对词典和倒排记录表这两个数据结构进行压缩。
为什么需要压缩？
- 使用更少的磁盘空间
节省资金
- 在内存中存放更多信息
提高速度
- 提高数据从磁盘传输到内存的速度
读取压缩数据|解压缩 比 读取未压缩数据 快得多
前提：解压缩算法是高效的
词典尽可能全部放在内存中，如果放不下，
倒排表没有办法全部放在内存中，把查询最多的词项的倒排表放在内存。
词典：
- 使其足以存放在内存中
- 使内存可以多容纳一些倒排记录表
倒排记录表：
- 减少所需的磁盘空间
- 减少从磁盘中读取倒排记录表所需的时间
- 大型搜索引擎将一部分倒排记录表保存在内存中（压缩使内存能保存更多的倒排记录表）
两种压缩方式：
无损压缩
：所有原始信息都保留（大多数IR系统的做法）
有损压缩
：大小写转换，词干还原，停用词…
会造成一定的信息丢失，但是有时候对检索没影响
信息检索中词项的统计特性
- 词项的个数：Heaps定律
- 词项在文档出现的次数，有的词项出现的多，有的词项出现的次数少：Zipf定律
文档集频率
：一个词项在文档集中总共出现次数
文档频率
：一个词项在几个文档中出现，倒排索引一部分。
区别
：词A中文档1中出现了3次，文档频率只算1个，但文档集频率算3
Heaps定律
词项数目的估计
-
Heaps’
定律:
M = kTb
-
M
是词汇表大小,
T
是文档集中的词条个数
-
参数k和b的典型取值为: 30 ≤
k
≤ 100
，
b
≈ 0.5
-
Heaps定律认为，在对数空间中词汇量
M
和
T
,存在线性关系
Zipf定律
对词项分布的建模
自然语言中存在一些高频词项，也存在一些极低频词项
-
Zipf’s 定律: 排名第i多的词项的文档集频率与1/
i
成正比.
-
cf
i
是
文档集频率
: 文档集中排名第i多的词项的文档集频率.
-
cf
i
∝ 1/
i = K/i
，
K
是一个常量
-
如果出现最多的词项的出现次数是cf
1
的话
-
出现第二多的词项的出现次数就是 cf
1
的一半
-
出现第三多的词项出现次数是cf
1
的1/3 …
-
-
等价变换: cf
i
=
K/i
,其中k=1, 因此
-
log cf
i
= log
K
– log
i
-
-
版权声明：本文为notqq555原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。