一键难忘520

这个屌丝很懒，什么也没留下！

热门标签

信息检索专题复习_信息检索中用于估计集合词汇量的公式称为什么

作者：一键难忘520 | 2024-07-17 10:06:04

踩

信息检索中用于估计集合词汇量的公式称为什么

信息检索

Made by ® Isaac. Ty

信息检索模型：描述信息检索中的文档、查询和他们之间的关系（匹配函数）的数学模型

IR新课题

自然语言理解
多媒体检索
垂直检索技术
移动搜索
对社会媒体信息检索
问答
知识发现
行为分析、舆情控制
自动对话

2.布尔检索

信息检索模型概述

定义

文档表示

一个文档被表示为关键词(bag of words)的集合

查询表示

查询式（Queries）被表示为关键词的布尔组合，用“与、或、非”连接起来（主析取范式）

非结构化数据

没有清晰和明显的语义结构的数据，计算机不易处理这些数据

结构化数据

最典型的时关系数据库，用来保存公司的产品清单和人事记录

聚类（clustering）

基于文档内容进行自动聚团的任务。很像在书架上将一系列书按照它们所属的主题重新摆放的过程。

分类（classification）

根据给定的主题、固定的信息需求或者其他类别体系，将每一个文档分到一个或多个类别的任务。

布尔模型：优缺点

优点

查询简单，容易理解
通过使用复杂的布尔表达式，可方便地控制查询结果
相当有效的实现方法
经过某种训练的用户可以容易地写出布尔查询式
布尔模型可以通过扩展来包含排序的功能

缺点

弱，不支持部分匹配，完全匹配会导致结果太多或太少
非常刚性：“与”意味着全部；“或”意味着任何一个，所有匹配文档都将被返回
不考虑索引词的权重，所有文档都以相同的方式和查询相匹配
很难进行自动的相关反馈

信息检索的基本假设

集合：固定数量的文档
目标：找到与用户信息需求相关的含有信息量的文档，帮助用户完成一个任务。

典型的搜索模型

构造矩阵→信息需求→文字形式→查询→查询优化→结果

返回文档的好坏

查准率

返回的能满足用户信息需求的文档占总的返回文档的百分比

召回率

返回的能满足用户信息需求的文档占总的能满足用户信息需求的文档的百分比

倒排索引

对于每一个词项，存储所有包含这个词项的文档的一个列表。一个文档用一个**序列号**docID来表示
应当使用可变长度的记录表
- 在硬盘上，一串连续的记录是正常的，也是最好的
- 在内存里，可以使用链表，或者可变长度的数组

倒排索引建立步骤

收集需要建立索引的文档
将每篇文档转换成一个个词条（token）的列表，此个过程称为词条化（tokenization)
进行语言预处理，产生归一化的词条来作为词项
对所有文档按照其中出现的词项来建立倒排索引，索引中包括一部分词典和一个全体倒排索引表
- 词条序列Token Sequence

（修改过的词条，文档ID）对序列

排序

先按照词条排序，再按照docID排序
词典和倒排表
- 同一篇文档中多次出现的词被合并
- 分割成词典和倒排表
- 词汇的文档频率也被记录
查询的处理:AND
- 考虑这样的查询： Brutus AND Caesar
- 在字典中找到Brutus，得到它的倒排记录表
- 在字典中找到Caesar，得到它的倒排记录表
- 合并两个倒排列表
- 同时扫描两个倒排记录表求交集，所需时间和倒排记录的数量呈线性关系。

布尔检索模型

文档表示

一个文档被表示为关键词的集合

查询表示

查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来(主析取范式DNF)

形式化表示

定义：用q~dnf~ 表示查询q的析取范式，q~cc~表示q~dnf~的任意合取分量
文献d~j~与查询q的相似度为

布尔检索模型：布尔代数

布尔变量

只有“真”、“假”取值的变量

布尔操作（关系）

布尔表达式

精确匹配

布尔模型可以用来处理布尔表达式形式的查询

布尔查询使用AND,OR和NOT来连接查询词汇
- 将文档看作词汇的集合
- 精确：匹配或不匹配
布尔模型式IR系统中最简单的模型

查询优化

按照文档频率的顺序进行处理。先处理文档频率小的，再处理大的。

3.词项词典和倒排记录表

建立词项词典

文档解析

文档格式
文档中的语言
文档的编码方式

词条化

将给定的字符序列拆分成一系列子序列的过程，其中每一个子序列称之为一个“词

条”Token。
词条(Tokens)、词项(Terms)
针对不同的语言，采用不同策略的词条化方法
分词的基本方法：
- 基于词典的最大匹配法
- 机器学习方法

停用词

停用词表：将词项按照文档集频率，从高到低排列。选取与文档意义不大，高频出现的词，例如a ,an , the , and, ….
优点：停用词消除可以减少term的个数
缺点：有时消除的停用词对检索有意义的。的士， to be or not to be
消除方法：查表法，基于文档频率

词项归一化

将不完全一致的多个词条归纳成一个等价类，以便在它们之间进行匹配。
归一化结果：在IR系统的词项词典中，形成多个近似词项的一个等价类
归一化策略：建立同义词扩展表

词干还原

很粗略的去除单词两端的词缀的启发式过程
能提高召回率，但是会降低准确率
porter算法

词形归并

利用词汇表和词形分析来减少曲折变化的形式，将其转变为基本形式
词形归并可以减少词项词典中的词项数量

区别：

词干还原在一般情况下会将多个派生相关词合并在一起
词形归并通常只将同一词元的不同曲折形式进行合并

实现倒排记录表

合并算法

通过在两个倒排表之间同时移动指针来实现合并，此时的操作与线性表的总数成线性关系。

基于调表的倒排记录表快速合并算法

跳表指针能够跳过那些不可能出现在检索结果中的记录项
如果倒排表的长度是L，那么在每个 $\sqrt L$ 处均放置跳表指针
跳表指针只对AND类型查询有用，对OR类型查询不起作用

短语查询

二元词索引

将文档中每个连续词对看成一个短语，其中的每个二元词对豆浆作为词典中的词项。

扩展的二元词索引

位置信息索引

在此索引中，对每个词项，都采取以下方式存储倒排表记录：

<词项，词项频率;

文档1：位置1，位置2，……

文档2：位置1，位置2，……

4.索引构建

硬件基础

语资料库

索引构建算法

基于块的排序索引算法（BSBI：Blocked sort-based Indexing）

在索引构建过程中需要依次分析所有的文档，不能很容易利用压缩技巧。只有分析完所有文档，最终的倒排记录表才会完整。
基本思想：对每一个块都生成倒排记录，并排序，写入硬盘。然后将这些块合并成一个长的排好序的倒排记录。
每条数据占用12字节（4+4+4）（词项，文档，频数）
在内存中处理，累积放满固定的块，排序后写入硬盘f~i~ ，合并所有索引文件成一个

基于BSBI排序算法存在的问题

假设能够将词典存入内存中
需要该词典动态增长去查找任一词项和词项ID之间的对应关系。
（一个可扩展的，但效率非常低的构建索引算法）

内存式单遍扫描索引算法（SPIMI Single-pass in-memory indexing)

核心思想：为每个块单独生成一个词典—— （不需要维护全局的<词项,词项ID>映射表）
不进行排序。有新的<词项,文档ID>对时直接在倒排记录表中增加一项。
- 可以为每个块生成一个完整的倒排索引，然后将这些单独的索引合并为一个大的索引
压缩技术将会使SPIMI算法更加高效
- 压缩词项
- 压缩倒排记录表

分布式索引构建（Distributed indexing）

Web规模的索引构建

必须使用一个分布式的计算机集群
计算机都是故障频发的
- 可能会在任意时刻失效
利用集群中的主控节点来指挥索引构建工作
- 认为主控节点是“安全的”
将索引构建过程分解成一组并行的任务
主控计算机从集群中选取一台空闲的机器并将任务分配给它
采用两组不同的并行任务
- Parsers分析器
  1. 主节点将一个数据片分配给一台空闲的分析服务器
  2. 分析器依次读取文档并生成<词项,文档>对。
  3. 分析器将这些<词项,文档>按照词项对分成 $j$ 个段
  4. 每一段是按照词项首字母划分的一个区间。
    
    例如：a-f,g-p,q-z 这里j=3
  5. 然后进行索引的倒排
- Inverters倒排器
  1. 对于一个词项分区，倒排器收集所有的<词项,文档>对（倒排记录）。
  2. 排序，并写入最终的倒排记录表。
首先，将输入文档集分割成n个数据片
- 每个数据片就是一个文档子集（与BSBI/SPIMI算法中的数据块相对应）
- 两种分割方法
  - 基于词项的分割
  - 基于文档的分割

动态索引

动态索引构建方法

文档集通常不是静态的

文档会不断的加入进来
文档也会被删除或者被修改

词典和倒排记录表需要修改

对于已在词典中的词项更新倒排记录
新的词项加入到词典中
1. 周期性索引重构
建立索引的同时，旧索引继续工作
条件
- 更新次数不是很多
- 能够接受对新文档检索的一定延迟（重构之前新文档检索不到）
- 有足够的资源进行重构
  1. 维护一个大的主索引
- 新文档信息存储在一个小的辅助索引中（位于内存）
- 检索可以同时遍历两个索引并将结果合并
- 删除
  - 文档的删除记录在一个无效位向量中
  - 在返回结果前利用它过滤掉已删除文档
- 定期地将辅助索引合并到主索引中
- 文档更新通过先删除后插入的方式实现

主索引与辅助索引存在的问题

频繁的合并带来很大开销
合并过程效率低
- 如果每个词项的倒排记录表都单独成一个文件，那么合并主索引和辅助索引将会很高效。
- 合并是一个简单的添加操作
- 需要使用很多倒排文件—— 对文件系统来说是低效的

对数合并

维护一系列索引 $I_0, I_1 , I_2, … ,$ 每个都是前一个的两倍大小
辅助索引 $Z_0$ 存储在内存中，而较大的（ $I_0, I_1 , I_2, … ,$ ）存储在磁盘中
当达到上限时，将它写入磁盘中，当下一次达到上限时，它会和合并，生成
- 此时，如果 $I1$ 不存在，存储到 $I1$ 中
- 如果 $I1$ 已存在，则 $Z1$ 与 $I1$ 合并成 $Z2$ (大小 $2^{2*n}$ )
- 此时，如果 $I2$ 不存在，存储到 $I2$ 中
- 如果 $I2$ 已存在，则 $Z2$ 与 $I2$ 合并成Z3 (大小 $2^{2*n}$ )
- ……

4.索引压缩

压缩

节省磁盘空间
提高内存的利用率（加快速度）
加快数据从磁盘到内存的传输速度
- [读取压缩数据][解压缩] 比直接 [读取未压缩的数据]快
- 前提：解压缩算法要很快

压缩倒排索引的原因

词典
- 压缩的足够小以便放入内存中
- 当词典足够小时，也可以在内存中存储一部分倒排索引记录表
倒排记录文件
- 减少所需要的磁盘空间
- 减少从磁盘读取倒排记录文件所需的时间
- 大的搜索引擎在内存中存储了很大一部分倒排记录表
- 压缩可以在内存中存储的更多
将涉及各种基于IR系统的压缩架构

词项统计量

词典压缩

有损压缩和无损压缩

无损压缩：压缩之后所有原始信息都被保留
- 在IR系统中常采用无损压缩
有损压缩：丢掉一些信息
一些预处理步骤可以看成是有损压缩：大小写转化，停用词剔除，词干还原，数字去除等
有损还是无损与需求相关

Heaps定律：M=kT^b^

M是词项的数目，T是文档集中词条的个数
词汇量大小M和文档集大小T在对数空间存在斜率为1/2的线性关系。
不同单词的数目与文本篇幅之间存在幂函数的关系，其幂指数小于1
提供了对文档集中词汇量的估计

Zipf定律

词项在文档中的分布情况
排名第i多的词项的文档集频率与1/i成正比
词项t~i~在文档集中出现的次数
高频词项很少，低频罕见词项很多

为什么要压缩词典

搜索从词典开始
想将词典放入内存中和其他应用程序共享内存资源
手机或者嵌入式设备通常只有很小的内存
即使不在内存中，也希望足够小以便搜索能够快速启动

压缩词项列表：将词典看成单一字符串

将所有词项存储为一个长字符串
- 指向下一词项的指针同时也标识着当前词项的结束
- 期望节省60%词典空间

按块存储（Blocking）

每k个词项分词一块，只保留第一个指针
需要存储词项长度（额外一字节）

前端编码

按照词典顺序排列的连续词项之间往往具有公共前缀
（块内k个词项的最后k-1个）

倒排记录表压缩

倒排记录表远大于词典，至少10倍
紧密地存储每一个倒排记录表
每个倒排记录用文档ID来定义

倒排记录表：相反的两点

像“arachnocentric”这样的词项可能在一百万个文档中才会出现一次可以用log21M ≈ 20 bits来存储这一倒排记录。
像“the”这样的词项在每个文档中都会出现，所以对它采用20bit/倒排记录太浪费了。
- 这种情况更希望是0/1的bit向量

倒排记录表项中文档ID的间距（GAP）

按照文档ID的递增顺序来存储一个词项的倒排列表
- Computer： 33，47，154，159，202，…
可以存储间距
- 33，14，107，5，43，…
期望：绝大多数间距存储空间都远小于20bit

可变长度编码

目标：
- 对于arachnocentric，使用20bit/间距项
- 对于the，使用1 bit/间距项
如果词项的评价间距为G，我们想使用log2Gbit/间距项
关键问题：需要利用整个字节对每个间距编码
- 可变长度编码：对一些小数字用短码来实现
可变字节码：
- 用一个字节来存储G，并分配1bit作为延续位
- G $\le$ 127 对7位有效码采用二进制编码并设置延续位c=1（结束)
- G $>$ 127 则先对G低阶的7位编码，然后采用相同的算法用额外字节对高阶bit位进行编码
- 设置最后一个字节的延续位为1（c=1)，其他字节的c=0（未结束）

5.Web搜索

Web搜索基础

重复文档

完全复制Duplication ：可以通过指纹（fingerprints）来检测精确匹配
近似重复Near-Duplication：通过编辑距离计算语法上的相似性

相似性计算

搭叠Shingles（N元词N-Grams）
- 给定正整数K及文档d的一个词项序列可以定义文档d的k-shingle为d中所有k个连续词项构成的序列
Jaccard系数：衡量重复度
- 表示公式：交集 / 并集
- 计算所有文档对之间搭叠的精确交集非常费时而且难以处理
- 使用冲Shingles中选出一个子集（素描sketch）来近似计算（抽样Sample）

小结：近似重复检测

Shingle算法的核心思想是将文件相似性问题转换为集合的相似性问题
数量较大时，对Shingle集合进行抽样，以降低空间和时间计算复杂性
shingle取样三种方法：Min-Wise,Modm,Mins

Web采集

采集器

从已知种子URL开始
获取页面并解析
1. 提取页面中包含的链接
2. 将链接放入URL队列
对队列中的URL转2

采集器必须具有的功能

礼貌性：Web服务器有显示或隐式的策略控制采集器的访问
鲁棒性：能从采集器陷阱中跳出，能处理Web服务器的其他恶意行为
分布式：可以在多台机器上分布运行
可扩展性：添加更多机器后采集效率应该提高
性能和效率：充分利用不同的系统资源，包括处理器、存储器和网络带宽
新鲜度：对原来爬取的网页进行更新
功能可扩展性：支持多方面的功能扩展，例如处理新的数据格式、抓取新的协议。

采集器基本架构

采集器

Web 图

Web →Web图

将静态Web看成静态HTML网页通过超链接互相连接而成的有向图，其中每个网页是图的顶点，而每个超链接式图的有向边。
该有向图可能不是一个强连通图，即从一个网页出发，沿着超链接前进，有可能永远不会到达另外某个网页
指向某个网页的链接称为 入链接（in-link)，而从某个网页指出去的链接称为出链接（out-link）。
入度：网页的入链数目。出度：网页的出链数目

邻接表

每个网页都用唯一的整数来表示
建立一个类似于倒排索引的邻接表，每行对应一个网页，按照其对应的整数大小排序。
任一网页P对应的行中包含的也是一系列整数的排序结构，每个整数对应链向P的网页编号。（那些网页指向P）

链接分析

Web是有向图

假设1：A到B的超链接表示A的作者对B的认可
假设2：指向页面B的锚文本式对B一个很好的描述

索引锚文本

索引文档D的时候，也索引指向文档D的锚文本
可以根据锚文本所在页面的权威性来确定锚文本的权重

小结：锚文本

Web上很多网页的内容并不包含对自身的精确描述
Web搜索者不一定要使用网页中的词项来对网页进行查询，而使用锚文本。
锚文本周围窗口中的文本也可以当成锚文本一样来使用。

链接分析：PageRank

PageRank

对Web图中的每个节点赋一个0~1间的分值，这个分值为PageRank
查询词无关的排序
第一代版本：使用链接的数目作为流行程度的最简单度量
两个改进：
- 无向流行度：赋予每个页面一个分：出链数+入链数
- 有向流行度：页面分数 = 入链数

查询处理

检索出所有满足文本查询词的页面，然后把这些页面按照链接的流行的排序。
更复杂：把链接按流行度当作静态得分，结合文本匹配的分数进行综合排序

PageRank打分

假设一个浏览者在网络上随机行走
- 从一个随机页面开始，每一步从当前页等概率地选择一个链接，进入链接所在页面
在稳定状态下，每个页面都有一个访问概率——用这个概率作为页面的分数
当浏览者在Web上进行节点间的随机游走时，某些节点的访问次数会比其他的节点更多
访问频繁的节点具有很多从其它频繁访问节点中指向的入链接
PageRank思路：在随机游走过程中越频繁访问的网页越重要

随机跳转（Teleporting）

遇到dead end时，随机跳转到一个页面，如果页面总数总是N，那么随机跳转的概率式1/N
非dead end，以 $a$ (值较小)的概率跳转到一个随机页面；以剩余1-a的概率从页面的出链中选择一个
随机跳转结果：不会再困在一个地，将会有比率表示所有网页长期被访问的概率

马尔科夫链

一个Markov链有N个状态，以及一个NxN的转移概率矩阵P。每一步只能处在一个状态
$1 \le i,j\le N$ ，转移概率矩阵P~ij~给出了从状态i到下一个状态j的条件转移概率
P中每一行的元素之和为1，从该页面跳转道其所有出链的概率之和为1
满足上述性质的非负矩阵被成为随机矩阵。最大特征值是1，与该特征值对应的有一个左特征向量
马尔科夫链中下一个状态的分布仅仅依赖于当前的状态，与如何到达当前状态无关。
马尔科夫链的状态概率分布可以看成一个概率向量，每个元素都在[0,1]，且所有元素的和为1（行）

邻接矩阵A→概率转移矩阵P

如果一行没有1（没有出链），用1/N代替每个元素
否则
- 每行中用1的个数除每个1。（归一化）若某行3个1，每个1用1/3表示
- 上面处理的结果矩阵乘以1-a
- 上面结果矩阵元素加上 a/N

概率向量的变化

最终访问频率收敛与固定的、稳态概率π
算法：给 X 乘上P的k次方，k不断增加，直到乘积稳定
π***P = π*
- 解矩阵等式得到π
- π是P的主左特征向量，π~i~是页面i的PageRank

链接分析：HITS

对每个网页给出两个得分 hub值（导航），authority值（权威）
确定基本集
精选出Hub页和Authority页
迭代跟新h(x),a(x)
- 输出h(x)最高作为Top Hub页，a(x)最高作为Top Authority页
大概5次迭代就会稳定
h是 $AA^t$ 的特征向量，a是 $A^tA$ 的特征向量

6.向量模型

排序式检索

布尔检索：文档要么匹配要么不匹配。对自身需求和文档集性质非常了解的专家而言，布尔查询式不错的选择。然而对大多数用户来说不方便

布尔查询的结果不是太多就是太少
需要花费很多精力去构造一个合适的query才可以获得一个在数量上可以接受的查询结果。

排序检索模型

在排序检索模型中，系统根据文档与query的相关性排序返回文档集合中的文档，而不是简单地返回所有满足query描述的文档集合。
自由文本查询：用户query是自然语言的一个或多个词语而不是由查询语言构造的表达式。
总体上，排序检索模型中有布尔查询和自由文本查询两种方式，但是实际中排序检索模型总是与自由文本查询联系在一起，反之亦然。

过多、过少不再是问题

当系统给出的式有序的查询结果，查询结果数目多不再是问题。只需要给出top K（10个左右）个结果，为用户减轻负担。
前提是有合适的排序算法

排序检索的基本—-评分

希望根据文档对查询者的有用性大小顺序将文档返回给查询者

给每个“查询—文档”对进行评分，在[0,1]之间
*这个评分值衡量文档与query的匹配程度*
以单个单词组成的query为例
- 如果单词不出现在文档中，该文档得分为0
- 该词项在文档中出现的频率越高，则评分越高

评分方案一—-Jaccard系数

一种常用的衡量两个集合A,B重叠度的方法

$Jaccard(A,B) = |A \cap B| / |A \cup B|$
$Jaccard(A,A) = 1$
$Jaccard(A,B) = 0 \ if\ A \cap B=0$
集合A和B不需要具有同样的规模
Jaccard(A,B)的取值在[0,1]

用Jaccard系数评分的问题

没有考虑词项频率（词项在文档中出现的次数）
没有考虑罕见词比高频词的信息量更大，更具区分度

词项频率

词项–文档二值关联矩阵

每个文档用一个二值向量表示 $\in \{0,1\}^{|v|}$ 。每个词项是否属于某个文档

词项—文档词频关联矩阵

考虑词项在文档中出现的频率，将每个文档看成是一个词频向量：矩阵中的一列

词袋模型（Bag of words）

不考虑词在文档中出现的顺序

“John is quicker than Mary” 和 “Mary is quicker than John” 的表示结果一样

词项频率tf（Term frequency）

词项频率：词项t在文档d中出现的次数，记为 $tf_{t,d}$

采用原始tf值（raw tf）
- 某个词项在A文档中出现10次，即tf=10，在B文档中tf=1，那么A比B更相关，但是相关度不会相差10倍
- 相关性不会正比于词项频率
对数词频
- 词项t在文档d中的对数频率权重
- - 文档——词项的匹配得分是所有同时出现在query和文档d中的词项的词频的对数之和
  - $Score(q,d) = \sum_{t\in q\cap d} (1+log^{tf_{t,d}})$
  - 评分为0，表示文档和query没有公共词项

tf-idf权重计算

除词项频率tf之外，利用词项在整个文档集中的频率进行权重和评分计算

罕见词所期望的权重

罕见词比常见词所蕴含的信息更多
考虑查询中某个词项，它会在整个文档集中非常罕见
某篇包含该词项的文档很可能相关，故罕见词项将有较高权重

常见词项所期望的权重

常见词项的信息量不如罕见词
考虑一个查询此项，它频繁出现在文档集中
一篇包含该词项的文档当然比不包含该词项的文档的相关度要高
但是，这些词对于相关度而言并*不是非常强的指示词*，故*给一个正的权重，但是整个权重小于罕见词权重*

文档频率（Document frequency，df）

罕见词项赋予高权重
常见词项赋予正的低权重
文档频率 $df$ 因子来计算查询–文档的匹配得分
文档频率：出现词项的文档数目

idf（inverse document frequency）逆文档频率

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/839351

信息检索专题复习_信息检索中用于估计集合词汇量的公式称为什么

信息检索

IR新课题

2.布尔检索

信息检索模型概述

定义

文档表示

查询表示

相关度计算

非结构化数据

结构化数据

聚类（clustering）

分类（classification）

布尔模型：优缺点

优点

缺点

信息检索的基本假设

典型的搜索模型

返回文档的好坏

查准率

召回率

倒排索引

倒排索引建立步骤

布尔检索模型

文档表示

查询表示

相关度计算

形式化表示

布尔检索模型：布尔代数

布尔变量

布尔操作（关系）

布尔表达式

精确匹配

查询优化

3.词项词典和倒排记录表

建立词项词典

文档解析

词条化

停用词

词项归一化

词干还原

词形归并

区别：

实现倒排记录表

合并算法

基于调表的倒排记录表快速合并算法

短语查询

二元词索引

扩展的二元词索引

位置信息索引

4.索引构建

硬件基础

语资料库

索引构建算法

基于块的排序索引算法（BSBI：Blocked sort-based Indexing）

基于BSBI排序算法存在的问题

内存式单遍扫描索引算法（SPIMI Single-pass in-memory indexing)

分布式索引构建（Distributed indexing）

动态索引

动态索引构建方法

主索引与辅助索引存在的问题

对数合并

4.索引压缩

压缩

压缩倒排索引的原因

词项统计量

词典压缩

有损压缩和无损压缩

Heaps定律：M=kT^b^

Zipf定律

为什么要压缩词典

压缩词项列表：将词典看成单一字符串

按块存储（Blocking）

前端编码

倒排记录表压缩

倒排记录表：相反的两点

倒排记录表项中文档ID的间距（GAP）

可变长度编码

5.Web搜索

Web搜索基础