现代信息检索 Chapter 6：文档-语言及属性

1 文本相似度

文本的相似度依靠距离函数度量，距离函数应该是对称的，即不受参数顺序影响，并且应该满足三角不等式：

$distance(a,c)\leq distance(a,b)+distance(b,c)$

常见的距离函数如下：

海明距离(Hamming distance)：对于相同长度的字符串，定义它们之间的距离为他们拥有不同字符的位置的个数。
编辑距离(Edit distance)：使两个字符串相同而在其中任何一个字符串上进行字符插入、删除和替换操作的最少次数。如“color”和“colour”的编辑距离是1。编辑距离是处理语法错误的首选模型。
最长公共子序列(longest common subsequence, LCS)：如“survey”和“surgery”的最长公共子序列是“surey”。
余弦相似度：第三章提到过。
类似度(resemblance)：两个文档词汇表的重合度。定义 $W(d_j)$ 是 $d_j$ 中所有不同词的集合，两个文档的类似度定义为： $R(d_i,d_j)=\frac{|W(d_i)\cap W(d_j)|}{|W(d_i)\cup W(d_j)|}$

任何在 $[0,1]$ 范围内的相似度度量都可以通过以下方式方便地转换为距离函数：

$D(d_i,d_j)=1-Sim(d_i,d_j)$

2 文档预处理

文档预处理阶段的逻辑视图如下，主要分为五个步骤：

2.1 词汇分析

词汇分析(Lexical analysis)是将字符流转化为单词流的过程，就是分词。主要考虑以下几种情况：

空格(Space)：最常见的分词符。
数字(Numbers)：根据上下文确定数字代表的意义，如量化数值、时间点，或是“512B.C.”这样的混合词。
连字符(Hyphens)：要不要拆，像“state-of-the-art”可拆可不拆，像表示序号的“A-3”最好不要拆。
标点符号(Punctuation marks)：区别对待句间分隔符、词间分隔符和词内分隔符。
大小写：要不要区分单词大小写，通常会影响到一些专有名词，如人名、地名、组织名。

2.2 去除停用词

停用词(Stopwords)通常是出现频率较多的词，被认为没有什么区分度，常见的是冠词、介词和连词。去除停用词可以减少索引结构的大小，但也会造成召回率的降低，也就是把一些相关的文本删到识别不出。所以有些Web搜索引擎会采用全文检索，不去除停用词。

2.3 词干提取

词干(stem)提取就是所谓的词形还原，把名词复数、动词过去式等还原。我觉得比较靠谱的方法也就是根据语法规则和查词表两种，但是词干提取对检索性能是否有帮助仍然存在争论。

2.4 关键词选择

和全文索引相对立，只选取文本中一部分代表性的词作为索引项，因此这种索引项也叫作关键词。关键词通常都是名词或者名词组，因为名词能够携带更多的信息。

2.5 同义词典

好像没什么用。

3 组织文档

顾名思义，就是文档的组织方式。主要有分类体系法(Taxonomies)和分众分类法(Folksonomies)。

分类体系法的核心是层次化，需要有一个清晰的分类层次，也需要对文档的类别有准确的描述，如下图：

分众分类法的核心是扁平化，最常见的是标签云，如下图。因为不能准确、完全地描述文档，所以只提取一些用户感兴趣的关键词作为标签。

4 文本压缩

文本压缩的目的是减少空间开销、输入/输出开销和通信时延。选择压缩方法时需要考虑的因素有：

压缩比，即压缩后大小与压缩前大小之比。
压缩和解压缩的速度，通常解压缩的速度更重要，因为只有在存储文档的时候需要压缩，而后续每次访问文档时都需要进行解压。
压缩文本是否支持搜索，即检索过程可以直接在压缩文档上进行，不需要预先解压缩，直接搜索压缩文档的速度会更快。

4.1 基本概念

文本压缩有两个通用方法：统计方法(statistical)和基于字典的方法(dictionary based)。统计方法估计每个文本符号出现的概率，根据出现概率将文本符号转换为二进制编码。字典方法从文档中识别出一系列可以被引用的短语，短语的集合称为字典，压缩的过程就是把文本中的短语替换成相应字典条目的指针。虽然压缩分为无损压缩和有损压缩，但在文档存储和检索的任务中，使用的基本都是无损压缩。

4.2 统计方法

统计方法定义为两个任务的组合：建模和编码。前者估计每个后续字符的概率，后者把后续符号编码成模型分配给他的概率函数，把每个符号表示成码字(codeword)。统计方法的理论基础是香农的信息论，信息压缩的下界是信息熵，文本的熵定义为：

$E=\sum p_ilog_2\frac{1}{p_i}$

也就是出现概率为 $p_i$ 的符号至少需要长度为 $log_2\frac{1}{p_i}$ 的码字表示，由于码字通常是整数个编码单元，实际长度往往会大于这个理论值。同时，编码需要给出现概率高的符号尽可能短的码字，这样才能保证较低的压缩率。

4.3 统计方法：建模

压缩模型分为自适应模型(adaptive model)、静态模型(static model)和半静态模型(semi-static model)。

自适应模型：不需要关于文本的先验知识，只需要处理文本一遍，在处理过程中根据读入的新文档动态调整字符的概率分布。有两个缺点，一是速度慢，因为需要动态更新，二是只能从压缩文档的开头进行解压，因为关于分布的信息数据实在文件中增量存储的。
静态模型：对所有输入的文本假设一个分布，只需要处理文本一遍，对所有要压缩的文本都使用这个分布。缺点是不使用，假设的分布在新的文档上往往效果很差。
半静态模型：不需要假设分布，但是要处理文本两遍。第一遍学习字符的概率分布，第二遍进行压缩，优缺点也很明显。

模型的阶(order)指的是用来估计下一个符号的概率而使用的前面符号的个数。 $0$ 阶模型就是所谓的上下文无关模型，每个符号概率的计算都是独立的。高阶模型压缩效果更好，但是需要更大的空间存储和运行，此外，任一位置的解压都需要知道前面 $k$ 个符号，所以高阶模型只能从开头进行解压，不支持随机访问。

除了基于字符的模型，还有基于词的模型，也就是直接对单词进行编码。词模型的理论基础是两个统计法则。一是 $Heaps$ 法则，指出 $n$ 个词的自然语言文本的词汇表大小 $V$ 的增长是 $V=O(n^\beta)$ ，其中 $\beta <1$ 是一个依赖于特定文本的常数。第二个法则是 $Zipf$ 法则，指出最常出现的第 $i$ 个单词出现 $O(n/i^\alpha)$ 次，其中 $\alpha >1$ 是依赖于文本的常数。这两个法则保证了基于词的模型不会产生量级的爆炸，同时概率分布具有良好的偏斜性。

4.4 统计方法：编码

霍夫曼编码(Huffman coding)是基于二叉树的前缀无关编码，通常使用霍夫曼树的规范树(canonical tree)形式，规范树规定任何结点的右子树不能高于他的左子树，因此给出有序的叶节点可以方便地还原规范树的结构。霍夫曼编码的缺点是只能从开头解码，因此不支持随机检索，例如考虑以下编码：A(0)、B(10)、C(110)、D(111)，若随机检索到编码片段 “11110”，就无法确定是“DB”还是开头少了一个1的“DC”，也就是两个码字的结合包含了第三个码字。更严谨的说法是不支持从任意位置解码，支持从任意码字的开头进行解码，虽然这么说没什么意义吧。

字节霍夫曼编码(Byte-Huffman coding)是基于词的模型，使用字节代替位进行编码，因此编码树不是二叉树，而是256叉树。好像用的不是很多。

密集编码(Dense coding)也是基于字节的编码，如下图，其中“<128>”指的是该字节的值是128。密集编码比字节霍夫曼编码更简单，在各个方面都优于字节霍夫曼编码，更重要的是密集编码支持从任意位置解码。因为密集编码可以很好地区分码头和码尾，整个字节的识别是很简单的，而观察到密集编码的结束字节值是在128到255之间的，这种属性称作自同步(self-synchronizing)，结束的字节称为停止符，之前的所有字节都称为持续符。更广义的密集编码记作 $(s,c)$ 密集编码，不把128作为持续符和停止符的界限，只要保证 $s+c=256$ ，可以修改为 $c$ 个持续符和 $s$ 个停止符，选择最优的组合。

算术编码，只写了一段，细节太少，没看懂。

4.5 字典方法

字典方法就不区分建模和编码的环节了，核心就是查字典而已。唯一需要考虑的问题是如何选择字典条目，同样也分成静态、半静态和自适应的方法，缺点也和上面说的类似。静态方法泛化性差，自适应方法的代表是 Ziv-Lempel 算法，字典随着压缩过程动态创建，问题就是不支持随机访问，半静态的方法最好，代表是 Re-Pair 算法。 Re-Pair 算法的核心简单说就是消除所有的重复符号对，首先给每个符号赋予一个整数，如果有重复的整数对“AB”，就用新的整数“C”替换“AB”，替换规则也可以嵌套，比如“CD”又重复了，就用“E”替换“CD”。缺点其实就是半静态方法的缺点，慢。

4.6 压缩预处理

文本压缩的最新趋势是压缩前的预处理，比较著名的方法是 Burrows-Wheeler 变换，简称BWT。流程就看下面两张图，原始字符串是“mississippi$”，其中“$”是可以是别的特殊终结符。首先列出原始字符串循环移位的矩阵，矩阵的每一行是上一行左移一位后的字符串。然后根据矩阵第一列按字典序排序，排序后矩阵的最后一列就是变换后的字符串。BWT的优点有两个，一是可逆，根据变换后的字符串可以还原出原始字符串，二是能够保证原始字符串中重复出现的字符可以在变换后的字符串中连续出现或至少离得比较近，图中的例子不太明显，比如“SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES”经过变换后成了“TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT”，就很明显了。