第15章 Compressed Data Structures：压缩数据结构

来源、版次与独立重写边界

“15 Compressed Data Structures”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“15 Compressed Data Structures”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“在压缩空间内支持 bitvector、树和图的导航与查询”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：15 Compressed Data Structures

• 15.1 Compressed Representation of (Binary) Arrays：在本页正文中以“在压缩空间内支持 bitvector、树和图的导航与查询”的对象、状态、复杂度或工程边界核对。
• 15.2 Succinct Representation of Trees：在本页正文中以“在压缩空间内支持 bitvector、树和图的导航与查询”的对象、状态、复杂度或工程边界核对。
• 15.3 Succinct Representation of Graphs：在本页正文中以“在压缩空间内支持 bitvector、树和图的导航与查询”的对象、状态、复杂度或工程边界核对。

从“指针为何比节点内容还贵”开始

compressed data structures关注的不只是 storage bytes。普通 compressor 把对象变成短 bitstream，查询前往往要恢复全部或大块数据；compressed structure 则把操作本身重新表达在 compressed representation 上。

先预测一棵每节点只有1-byte label 的二叉树。64-bit 机器上 left/right pointers 各8 bytes，结构开销是 payload 的16倍；allocator metadata、alignment 与 cache miss 还未计入。问题不是 gzip 能否把 dump 压小，而是运行时能否不创建这些 pointers 仍执行 parent、child、Rank 或 neighbor query。

pointerless programming 把“第 i 个对象在哪里”改写成紧凑数组上的数值操作。若所有 strings 拼成 payload D，并以 bitvector B 标出每个 string start：

• Select1(B,i) 返回第 i 个 string 的起点。
• Rank1(B,p) 返回 position p 属于第几个 string。
• 相邻两个 Select 的差给出 string length。

这种布局连续、可 mmap、prefetch 友好，也不需要 relocation。代价是 pointer dereference 变成 Rank/Select；本章的关键是用 o(n) auxiliary bits 让这些 primitive 保持常数时间。

15.1 Compressed Representation of Binary Arrays

compressed representation of binary arrays是 pointerless structures 的基座。对 B[1..m]：

上图采用 inclusive Rank；实现也常定义 half-open Rank(B[0..i))。两种都正确，但公式、directory 和 tests 必须统一。Select0/Rank0 可由1操作与位置长度推得，也可为速度单独建目录。

Rank：superblock、block 与共享微表

为每个位置保存 prefix count 需要 m log m bits，比 B 本身还大。succinct 方案把 B 切成大 superblocks 与小 blocks：

1. 每个 superblock 保存从 B 开头到该块前的1总数，字段宽 O(log m)。
2. 每个小 block 保存相对所在 superblock 开头的1总数，只需 O(log log m) bits。
3. query 剩余的短尾块作为 bit pattern，查全局共享 table 得内部 popcount。

典型取 superblock 长约 log²m、block 长约一半 log m。superblock entries 数 m/log²m，第一层占 O(m/log m) bits；第二层与微表也都是 o(m)。于是总空间 m+o(m) bits，Rank O(1)。

现代 CPU 有 popcount，可把微表替换为 word operation；理论分块仍说明为何 directory 是 sublinear。工程上 block size 还要按 cache line、SIMD width 与 serialized format 调整。

Rank1(i):
  s = floor(i / superblockBits)
  b = floor(i / blockBits)
  return superPrefix[s]
       + blockOffset[b]
       + popcount(bits from block start through i)

Select：按“1的数量”切块

Select 的困难是目标 position 未知，不能先按 position 找 block。本页采用多级 decomposition：每 K 个1划一个 big block。若该 block 跨越的 bit range 很长，称 sparse，直接保存其中1的 positions；否则称 dense，再每 k 个1切 small blocks。

dense small block 若跨度仍长就显式存相对 positions；跨度短则整个 bit pattern 足够短，用共享 table 回答“第 r 个1在何处”。K、k 与稀疏阈值选成 log m 的幂后，所有显式 positions 与 tables 合计 o(m)，Select O(1)。

这与 Rank 的“按固定位置分块”不同：Select 的 blocks 按固定 one-count 分组，才能由 k 直接算目标 big block id。Rank 与 Select directories 可以共享 B，却有不同 sampling geometry。

Elias–Fano：稀疏1位置的压缩解法

plain B 总要 m bits。当只有 n 个1且 n 远小于 m，信息下界约为：

把1的位置提取成递增数组 A[1..n]，就能用 Chapter 11 的 Elias–Fano。取 ℓ≈log2(m/n)，每个 A[i] 的 ℓ 个 low bits 定宽存入 L，high parts 以 unary bucket bitvector H 保存。

示例 B=01100001010 的1位置 A=[2,3,8,10]。Access(i) 从 L 取 low，再用 Select1(H,i)-i 得 high bucket；拼接恢复 A[i]。NextGEQ(x) 先在 H 定位 high bucket，再比较该 bucket 的 low values。

空间约：

H 上 Select 的 auxiliary space 是 o(n)，相对 number of ones 而非 m。选择 plain bitvector 还是 Elias–Fano 要看 density 与 query mix：dense B 的 direct word Access/Rank 更快；sparse B 的 EF 可显著省 cache traffic。

15.2 Succinct Representation of Trees

succinct representation of trees先把 labels/payload 与 shape 分开。n-node ordered binary trees 的数量是 Catalan number：

因此任何能表示所有 shape 的编码都约需2n bits；传统2n pointers 却要16n bytes。

Binary tree：node/null preorder

preorder 扫描时，真实 node 写1，null child 写0。n个 nodes 有n+1个 null links，总长2n+1 bits，且可递归唯一解析：读1就创建 node 并解析 left/right，读0就返回 null。

EncodeBinary(node):
  if node is null:
    emit 0
    return
  emit 1
  EncodeBinary(node.left)
  EncodeBinary(node.right)

labels 按 preorder 独立排成 compact array。structure bit position 与 preorder node id 由 Rank1 互转；Select1(id) 找该 node 的 opening bit。进一步加 excess/min-max directories，可在 O(1) 导航而不递归扫描整棵 subtree。

Arbitrary rooted ordered tree：balanced parentheses

进入 node 写 open bit 1，离开 node 写 close bit 0，n节点恰好2n bits。open position 的 excess 是当前 depth；matching close 界定 subtree interval。第一个 child 是 open 后紧随的 open；next sibling 是 matching close 后的 open；parent 可用 enclosing-open query。

Jacobson 的核心贡献是给这种 bit sequence 加 o(n)-bit index，在常数时间支持 Rank/Select 与括号导航，达到2n+o(n) bits。任意 degree 不再需要每节点 child array；degree、k-th child、subtree size、preorder/postorder number 都可归约为 parentheses primitive。

若 node 有 labels，按 preorder 存 label sequence；若还要 child(u,c)，可在 label array 上加 wavelet tree/Rank。结构、标签、payload 各用最合适的 compressed representation，而不是把节点对象整体 serialize。

15.3 Succinct Representation of Graphs

succinct representation of graphs没有一种方案对所有 graph 都最优。arbitrary directed graph 的 adjacency matrix 有 n² bits；若恰有 m 条边，组合下界约：

但 Web graph 有 URL locality、similarity 与 small gaps；spatial/sparse matrix 则有 empty quadrants。本页分别用结构专门化方案说明压缩不是一个万能 codec。

WebGraph：相邻 adjacency lists 高度相似

WebGraph先把 URLs 排成使相关 pages 靠近的 node ids。页面 v 的 outgoing neighbors 往往与前面某个 reference page 相似：

1. 编码 reference distance。
2. 用 copy mask 指出 reference list 的哪些 neighbors 被复用。
3. 把连续 target ids 变成 intervals。
4. 剩余 links 排序做 d-gap，再用 Elias gamma/delta 等整数码。

每个 adjacency list 的 bit offset 形成单调数组，可再用 Elias–Fano 保存，支持 Access 到第 v 个 list。解码一个 list 可能递归依赖 reference chain，因此格式限制 chain depth 或周期性写 materialized lists；否则随机访问会退化。

本课程还强调 neighbor ids 与 current node 的差通常小，URL/node ordering 直接影响 gaps。压缩评测要固定 ordering，分别报告 bits/link、reference depth、list decode ns/edge 与 random node latency。

k²-tree：递归编码 adjacency matrix 的非空块

k²-tree从 n×n binary adjacency matrix 开始。每层把当前 region 切为 k×k blocks，按固定顺序写 occupancy bits；只递归值为1的 blocks。所有内部层 bits level-order 存 T，最后一层存 L。

若 edge clusters 只占少量 quadrants，大量0会在高层终止，不再为内部 cells 付费。child offset 不是 pointer：某个1之前的 Rank1 决定它拥有的 k² children 在下一层的起点。

Children(bitPosition):
  if T[bitPosition] is 0:
    return empty
  childGroup = Rank1(T, bitPosition) * k * k
  return the k*k consecutive bits at childGroup

neighbor query 固定 matrix row，沿与该 row 相交的 child blocks 下降；edge(u,v) 每层只走一个 quadrant，成本 O(log_k n)；range query 剪掉不相交或 empty regions。k=2 树更深、每 node 4 bits；更大 k 树浅但每 node fanout bitmap 更宽，需按 graph clustering 和 cache width调参。

统一视角：Rank/Select 是压缩域里的地址计算

工程验收分三层。space 报告 raw payload、main compressed bits、Rank/Select auxiliary bits、alignment 与 object headers；time 报告 Access/Rank/Select latency、tree navigation、neighbors ns/edge、cold-cache 与 mmap first-touch；correctness 做 forward/reference decoder round-trip、所有 boundary positions、empty/full bitvector、deep tree、isolated vertex、self-loop 与 malformed offsets。

真正的收益常来自 memory hierarchy：少占空间意味着更多 working set 进入 LLC、少读 DRAM/SSD，即使每次 query 多几条 bit operations，端到端仍可能更快。反过来，对极小或极热数据，plain arrays 往往胜过复杂 succinct indexes；格式应保留 density/size based fallback。

先预测，再操作三个章专属实验

rank1(select1(j)) = j

可重放工程合同

“15 Compressed Data Structures”的实验必须保留：原始结构、压缩位串、辅助表、查询序列、空间位数与朴素预言机。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

本章回顾

1. 压缩数据结构在 compressed representation 上直接查询，不要求先整体解压。
2. pointerless programming 用 contiguous payload 与 bitvector boundary 取代4/8-byte offsets。
3. Rank 统计前缀1，Select 定位第k个1，是数组、树、图导航的共同 primitive。
4. plain bitvector 配两级 directory 与微表可在 m+o(m) bits 内常数 Rank/Select。
5. 稀疏 bitvector 可转1-position monotone array，用 Elias–Fano 接近 n log(m/n)+2n。
6. binary tree 的 node/null preorder 用2n+1 bits，接近 Catalan shape 下界。
7. arbitrary ordered tree 的 balanced parentheses 恰用2n bits，导航归约到括号查询。
8. WebGraph 利用 URL locality、reference copy、interval 与 residual gap coding。
9. adjacency-list offsets 可用 Elias–Fano；reference chain depth控制随机访问。
10. k²-tree 只展开非空 matrix quadrants，以 Rank 计算 child groups 而无需 pointers。

名词解释