信息检索与数据挖掘 2019/3/7 1 信息检索与数据挖掘 第4章索引构建与索引压缩 一一第二讲索引压缩
信息检索与数据挖掘 2019/3/7 1 信息检索与数据挖掘 第4章 索引构建与索引压缩 ——第二讲 索引压缩
信息检索与数据挖掘 2019/317 3 索引压缩 ·统计信息（对RCV1语料库） ·词典和倒排记录表将会有多大？ 为什么要压缩 ·词典压缩 ·倒排记录表压缩 怎么压缩 Brutus 24113145173174 Caesar 2 4561657132 Calpurnia 23154101 词项词典 Dictionary 倒排记录表 Postings List
信息检索与数据挖掘 2019/3/7 3 索引压缩 • 统计信息(对RCV1语料库) • 词典和倒排记录表将会有多大？ • 词典压缩 • 倒排记录表压缩 为什么要压缩 怎么压缩
信息检索与数据挖掘 2019/3/7 4 索引压缩 ·统计信息（对RCV1语料库） 。词典和倒排记录表将会有多大？ ·Heaps定律：词项数目的估计 。Zipf定律：对词项的分布建模 ·词典压缩 ·将词典看成单一字符串的压缩方法 ·按块存储/前端编码 ·倒排记录表压缩 ·可变长字节码 ·一元编码/Y编码
信息检索与数据挖掘 2019/3/7 4 索引压缩 • 统计信息(对RCV1语料库) • 词典和倒排记录表将会有多大？ • Heaps定律：词项数目的估计 • Zipf定律：对词项的分布建模 • 词典压缩 • 将词典看成单一字符串的压缩方法 • 按块存储/前端编码 • 倒排记录表压缩 • 可变长字节码 • 一元编码/ γ 编码
信息检索与数据挖掘 2019/3/7 5 为什么要压缩（一般来说）？ 。节省磁盘空间 。省钱 ·提高内存的利用率 ·提高速度 ·加快数据从磁盘到内存的传输速度 ·[读取压缩数据][解压缩]比直接[读取未压缩的数据]快 ·前提：解压缩算法要很快 ·我们目前所用的解压缩算法在现代硬件上运行相当快
信息检索与数据挖掘 2019/3/7 5 为什么要压缩(一般来说)？ • 节省磁盘空间 • 省钱 • 提高内存的利用率 • 提高速度 • 加快数据从磁盘到内存的传输速度 • [读取压缩数据][解压缩]比直接[读取未压缩的数据]快 • 前提：解压缩算法要很快 • 我们目前所用的解压缩算法在现代硬件上运行相当快
信息检索与数据挖掘 2019/3/7 6 为什么要压缩倒排索引？ ·词典 ·压缩的足够小以便能够放入内存中 ·当词典足够小时，我们也可以在内存中存储一部分的倒 排记录表 ·倒排记录文件 ·减少所需的磁盘空间 ·减少从磁盘读取倒排记录文件所需的时间 ·大的搜索引擎在内存中存储了很大一部分的倒排记录表 ·压缩可以让我们在内存中存储的更多 ·我们将设计各种基于IR系统的压缩架构
信息检索与数据挖掘 2019/3/7 6 为什么要压缩倒排索引？ • 词典 • 压缩的足够小以便能够放入内存中 • 当词典足够小时，我们也可以在内存中存储一部分的倒 排记录表 • 倒排记录文件 • 减少所需的磁盘空间 • 减少从磁盘读取倒排记录文件所需的时间 • 大的搜索引擎在内存中存储了很大一部分的倒排记录表 • 压缩可以让我们在内存中存储的更多 • 我们将设计各种基于IR系统的压缩架构