信息检索系统中的数据压缩

### 信息检索系统中的数据压缩 在信息检索系统中，数据压缩是一项关键技术，它能够有效减少数据存储空间，提高数据传输和处理效率。本文将深入探讨信息检索系统中的数据压缩方法，包括文本压缩、字典压缩以及索引压缩等方面。 #### 文本压缩 文本压缩是信息检索系统中最基本的数据压缩方式。其中一种常见的方法是基于重复字符串的压缩。该方法的核心思想是将文本中的重复字符串用偏移 - 长度对来表示，从而减少数据的冗余。 压缩过程的输出是一个元素序列，每个元素可以是单个未压缩字符，也可以是偏移 - 长度对 `(J, €)`。这些元素通过标志位进行标识，单个字符编码以 0 开头，后面跟着 8 位 ASCII 码表示该字符；而 `(J, i)` 对的编码以 1 开头。可能的偏移和长度集合被分为不同的类别，具体编码方案如下： 设 `Bfn(n)` 表示 `n` 的标准 `m` 位二进制表示（必要时补前导 0），编码方案 `AM` 定义为： - 偏移量 `d` 的编码： - 当 `1 < d < 64` 时，`A,M(offset d) = B6(d - 1)` - 当 `64 < d < 320` 时，`A,M(offset d) = 01Bs(d - 65)` - 当 `320 < d < 4416` 时，`A,M(offset d) = nBn(d - 321)` - 长度 `€` 的编码： - 当 `€ = 2` 时，`AM(length €) = 0` - 当 `2^j < € - 2 < 2^(j + 1)`（`j = 0, 1, 2, ...`）时，`AM(length €) = V + ^0Bj(€ - 2 - 2^j)` 例如，前几个长度编码为 `0, 10, 1100, 1101, 111000, 111001, 111010, 111011, 11110000` 等。偏移量用 8、11 或 15 位编码，长度 `€` 的编码位数在 `€ = 2` 时为 1 位，`€ > 2` 时为 `2⌈log2(€ - 1)⌉` 位。 #### 字典压缩 在大型全文检索系统中，字典的使用非常广泛。字典不仅可以用于快速访问索引，还可以对文本本身进行压缩，并为用户选择关键词提供有用的额外信息。 字典可以像普通文本一样进行压缩，但考虑到其特殊结构，可能会有更优的方法。一种简单而有效的技术是前缀省略法（POM），也称为前端压缩。该方法基于字典中连续条目大多共享一些前导字母的观察。设 `x` 和 `y` 是连续的字典条目，`m` 是它们最长公共前缀的长度，那么只需将公共前缀存储一次（与 `x` 一起），并从后续条目中省略该前缀，同时记录前缀长度 `m`。这可以很容易地推广到更长的字典条目列表。 | 字典条目 | 前缀长度 | 存储后缀 | | --- | --- | --- | | FORM | 0 | FORM | | FORMALLY | 4 | ALLY | | FORMAT | 5 | T | | FORMATION | 6 | ION | | FORMULATE | 4 | ULATE | | FORMULATING | 8 | ING | | FORTY | 3 | TY | | FORTHWITH | 4 | HWITH | 如果字典条目采用标准格式编码，每个字符占一个字节，可以使用压缩字典中每个条目的第一个字节来存储前缀长度 `m` 的值。由于大型字典中连续条目的公共前缀平均长度通常远大于 1，因此这种方法通常能带来显著的压缩效果。即使条目已经通过逐个字符的霍夫曼编码进行了压缩，仍然可以节省一些空间。 为了方便处理，可以选择一个固定的整数参数 `k`，并预留每个条目的前 `k` 位来表示 `0 < m < 2^k` 的 `m` 值，其中 `k` 不一定需要大到能容纳最长省略的前缀。 然而，标准字典可能无法满足复杂系统的灵活性需求。例如，处理各种截断词是一个重要的功能，可以通过可变长度的通配符 `*` 来实现。后缀截断可以由常规字典处理，但前缀截断存在问题，因为相关词条分散在文件中，难以定位。一种解决方案是在系统中添加逆字典，即将每个词条反转后按字典序排序。搜索时，如搜索 `*ache`，可以通过反转字符串 `ehca` 访问逆字典，检索以其为前缀的条目，再将这些字符串反转回来得到原始词条。但逆字典的解决方案无法同时处理前缀和后缀截断。 一种优雅的方法是置换字典。给定一个字典，通过以下步骤得到相应的置换字典： 1. 给每个词条添加一个不在任何词条中出现的字符 `/`。 2. 对于长度为 `n` 个字符的词条 `x`，通过将字符串 `x/` 循环移位 `k` 个字符（`0 < k < n`），形成 `n + 1` 个新词条。 3. 对生成的列表按字母顺序排序。 ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(添加字符 `/`):::process B --> C(循环移位):::process C --> D(按字母顺序排序):::process D --> E([结束]):::startend ``` 使用置换字典的关键是 `get(x)` 函数，它可以访问文件并检索所有以 `x` 为前缀的字符串。这些字符串很容易定位，因为它们连续出现，通过简单的循环移位即可恢复相应的原始词条。 #### 索引压缩 数据库中每个单词的每次出现都可以通过一个数字序列唯一表征，该序列给出其在文本中的精确位置。通常，这个序列包括文档编号 `d`、段落编号 `p`、句子编号 `s` 和单词编号 `w`，即 `(d, p, s, w)` 四元组，称为出现的坐标。 索引以压缩形式存储在二级存储中，需要时提取部分并进行解压缩。压缩文件被划分为等大小的块，以便通过单次 I/O 操作读取一个块。由于任何给定单词的坐标列表是有序的，相邻坐标通常具有相同的 `d` 字段，甚至相同的 `d` 和 `p` 字段，有时对于高频单词，`d`、`p` 和 `s` 字段也相同。因此，POM 方法可以应用于索引的压缩，为每个坐标添加一个头部，指示可以从前面坐标复制的字段数量，然后省略这些字段。 为了方便计算机处理，通常为每个字段选择固定的长度，这要求字段长度足够大以表示最大可能的值。然而，大多数存储的值较小，因此每个坐标通常会浪费大量空间。在某些情况下，可以通过牺牲更长的处理时间来节省一些空间。 一种新的方法是允许 `p`、`s` 和 `w` 字段具有可变长度。与 POM 类似，每个压缩坐标前面都有一个头部，用于编码解压缩坐标所需的信息。这些方法的区别在于对头部的解释。每个字段长度的选择基于从整个数据库收集的每个字段值分布的统计信息。因此，对于动态变化的数据库，压缩方法需要频繁更新，更适合静态数据库。 头部代码可以有多种解释： - 表示长度 `€`，表示相应字段以 `€` 位编码。 - 表示某个值 `v`，表示相应字段包含该值。 - 表示不存储相应字段的值，应使用前一个坐标的值。 这种方法比前缀省略技术更通用，因为可以针对每个字段单独决定是否省略，而在 POM 中，只有当 `d` 字段被省略时，`p` 字段才会被省略。 具体的方法包括： - **简单方法**：头部包含每个字段的大小（以位为单位）的代码。 - 为 `p`、`s` 和 `w` 字段各分配两位，每个字段有四种可能的选择。 - 一种可能的代码表示省略该字段，因此每个字段的长度只剩下三种可能的选择。 - 四种选择用于编码字段长度，不允许使用前一个坐标的值。 - 对 `p` 和 `s` 字段使用第一种方式，对 `w` 字段使用第二种方式。 - 为 `p`、`s` 和 `w` 字段各分配三位，每个字段有八种可能的选择。通过增加可能性的数量，可以更有效地划分可能值的范围，从而在坐标的其余部分节省空间。 - **使用某些字段编码频繁值**：对于一些非常频繁的值，头部代码将直接解释为其中一个值，而不是存储这些值的字段的长度。因此，在所有这些情况下，可以省略相应的字段。但频繁值的节省是以减少不频繁值的字段长度选择数量为代价的。 - 为 `p`、`s` 和 `w` 字段各分配两位，其中一个代码指向最频繁的值。 - 为 `p`、`s` 和 `w` 字段各分配三位，其中三个代码指向三个最频繁的值。 - **组合方法**：为 `p`、`s` 和 `w` 字段分别选择上述方法中的最佳方法。 - **编码长度组合**：为了进一步改进简单方法，可以为每个字段的每个可能长度设置一个代码，但值的最大值可能很大。例如，在 RRP 中，`w` 字段的最大值需要 10 位，`s` 字段需要 9 位，`p` 字段需要 10 位。这将意味着每个字段的头部长度为 4 位，相对于简单方法（ii）的改进微不足道。 通过用单个代码替换 `p`、`s` 和 `w` 字段大小的三个代码，可以减少头部的大小。用 `lp`、`ls` 和 `lw` 分别表示 `p`、`s` 和 `w` 字段的长度，即存储在其中的值的二进制表示的位数（不包括前导零）。在模型中，`1 < lp, ls, lw < 10`，因此最多有 `10^3` 种可能的三元组 `(lp, ls, lw)`。然而，大多数这些长度组合很少出现。在 RRP 中，255 个最频繁的 `(lp, ls, lw)` 三元组已经占了索引的 98.05%。因此： - 分配 9 位作为头部，其中 1 位用于 `d` 字段；剩余 8 位中的 255 个可能代码指向 255 个最频繁的 `(lp, ls, lw)` 三元组；最后一个代码用于表示坐标对应于“罕见”三元组，在这种情况下，`p`、`s` 和 `w` 字段以解压缩形式出现。 - 分配 8 位作为头部，其中 1 位用于 `d` 字段；剩余 7 位用于编码 127 个最频繁的 `(lp, ls, lw)` 三元组。 - 分配 8 位作为头部；255 个代码指向 255 个最频繁的四元组 `(b, lp, ls, lw)`，其中 `b` 是一个布尔变量，表示 `d` 字段的值是否与前一个坐标相同。 在选择合适的压缩方法后，按顺序扫描索引，并对每个坐标进行压缩，可以使用或不使用前一个坐