1. 背景：搜索引擎与索引压缩
在搜索引擎或类似需要对海量文档进行检索的系统中，通常会构建倒排索引（Inverted Index）。为降低存储成本、减少 I/O 并提升检索速度，对倒排索引所包含的大量整数序列进行压缩是一种行之有效的手段。
• 目标：在确保解压速度的同时，尽量获得更好的压缩率。
• 挑战：需要一种兼顾解压效率与压缩比的整数压缩算法，以满足高并发、低延迟的检索需求。
2. PForDelta 与 New PForDelta 的基本概念
2.1 PForDelta（Patched Frame-of-Reference Delta）
• Frame-of-Reference (FOR)：将一批（batch）整数序列减去某个参考值（通常是最小值或前一个值），以缩小数值范围。
• Delta Encoding：对相邻整数做差分，进一步减小数值的绝对大小。
• PForDelta：在 FOR + Delta 的基础上，为在批次中仍然较大的“异常值”（exceptions）预留单独的存储空间，使主体部分可以使用更少的位宽进行紧凑编码。
2.2 New PForDelta
New PForDelta 是对传统 PForDelta 的改进版本，主要优化点在于：
1. 自适应位宽选择：更灵活地确定批次内大部分数值所需的位宽，减少“异常值”的数量。
2. 异常值处理：在补丁（patch）方式之外，还可能通过分块等技术减少异常值对压缩效率的影响。
3. 实现复杂度：在确保压缩/解压速度不降低的情况下，使算法在实际系统中更易实现。
通过这些改进，New PForDelta 在大部分场景下相对于原始 PForDelta 有了更好的压缩率和更快的解压速度，同时依然保持了算法相对简单、易于工程化的特点。
3. SIMD 技术简介
3.1 什么是 SIMD
SIMD（Single Instruction, Multiple Data）是一类 CPU 指令集（如 Intel 的 SSE、AVX，ARM 的 NEON 等），它可以在一次指令中同时对多组数据进行并行计算。利用 SIMD 技术，我们可以在处理批量数据时显著提升性能。
• 关键：将数据打包（pack）到较宽的寄存器（如 128 位、256 位、512 位），通过单条指令执行多个操作。
3.2 为什么在压缩/解压中使用 SIMD
• 批量处理：整数压缩往往需要对连续块（batch）中的所有数字进行相同的解压或编码操作，易于进行并行化。
• 减少分支：通过 SIMD，可以减少在循环中显式判断“异常值”的分支，提高现代 CPU 的流水线利用率和缓存命中率。
• 更高吞吐：对于解压环节，需要快速将压缩格式转回可用的整数序列，SIMD 的批量解码可以显著提升吞吐。
4. New PForDelta 中使用 SIMD 的优化思路
1. 批处理：New PForDelta 通常将数据分成固定大小的块（例如 128 个或 256 个整数），这样可以把待解压的一整个批次直接加载到 SIMD 寄存器中进行处理。
2. 位操作（bit-packing/unpacking）：解压阶段核心是把紧凑编码的数据还原为原始整数，需要频繁的位移和掩码操作。SIMD 指令集中的“按位并/或/异或/移位”可以一次性对多组数据并行操作。
3. 异常值处理：New PForDelta 在异常值的存储上，往往需要先判断异常值位置，再单独读取。当利用 SIMD 时，可以将异常值标记或索引批量读入寄存器，通过减少循环中的分支判断、利用“掩码（mask）”操作来快速处理异常值。
4. 流水线优化：现代 CPU 擅长处理重复性强、无数据依赖的指令序列。将多批次（batch）的数据顺序进行 SIMD 解压时，可以最大限度地利用缓存并减少指令跳转。
5. 实际效果与应用
• 高吞吐：在 Intel 或 ARM 的处理器环境下，使用 SIMD 优化后的 New PForDelta，解压速度可显著提升，常见的评测中可达到几千万甚至上亿整数/秒的解压吞吐量。
• 更好的压缩率：New PForDelta 保留了原算法良好的压缩率，通过对异常值的灵活处理能够在多种分布的整数序列上取得不错的表现。
• 使用场景：常见于搜索引擎、大规模日志分析、时间序列数据库、实时分析引擎（如 Elasticsearch、Lucene、ClickHouse 等）中，用于快速查询时的索引解压。
6. 进一步思考
• 硬件适配：不同 CPU 架构拥有不同的 SIMD 指令集（SSE、AVX2、AVX-512、NEON、SVE 等），对相应的实现要进行有针对性的优化。
• 扩展到更广泛场景：在部分场景中，数据分布的离散程度较大，PForDelta 系列算法未必最优；可考虑差分字典压缩、字典编码、Varint-G8IU 等其他技术。
• 混合算法：在实际工程中，往往会针对不同列/字段选用不同的压缩算法，以平衡压缩比与解压速度；有时也会使用多线程加速与 SIMD 并行解压相结合，进一步提高吞吐。
总结
• New PForDelta 是一种面向搜索引擎倒排索引、时间序列数据等场景的整数压缩算法，相比传统 PForDelta 具有更高的压缩率和解压性能。
• SIMD 优化 在压缩/解压过程中的批量处理、位操作、异常值处理等方面具备显著优势，可有效提高吞吐量。
• 在实际系统中，需要结合具体的数据分布和硬件架构进行针对性实现和调优，从而取得在存储与速度上的最佳平衡。
下面给出一个简化示例，演示 PForDelta 如何利用 Frame-of-Reference (FOR) 与 Delta Encoding，并为“异常值”单独预留存储空间。、
示例数据
假设我们有这样一批（batch）无符号整数（或ID）：
[100, 105, 106, 120, 121, 122, 200, 201]
我们希望以较少的位宽（bit-width）对其进行压缩。
第一步：Frame-of-Reference (FOR)
1. 选定参考值（frame）
• 通常会选取本批次中的最小值或其他合适的参考值。
• 在这里，最小值为 100，我们将其作为参考值 base。
2. 计算与参考值的差（差值序列）
• 新的序列为：
• 对应到示例数据：
100 -> 100 - 100 = 0
105 -> 105 - 100 = 5
106 -> 106 - 100 = 6
120 -> 120 - 100 = 20
121 -> 121 - 100 = 21
122 -> 122 - 100 = 22
200 -> 200 - 100 = 100
201 -> 201 - 100 = 101
• 差值序列如下：
[0, 5, 6, 20, 21, 22, 100, 101]
第二步：Delta Encoding（如果需要）
有些场景还会对差值序列再次做相邻差分（Delta Encoding），比如再将上述差值序列转化为相邻元素的差。但是 PForDelta 最常用的做法是：先做 “” 或 “” 的差分，再结合后续的异常值处理。这里为了示例简单，我们先不叠加“相邻差分”，主要关注 FOR 与异常值。
第三步：挑选位宽与识别“异常值”
3.1 统计差值范围
• 现有差值序列：
[0, 5, 6, 20, 21, 22, 100, 101]
• 可以看到：
• 大部分数值（0, 5, 6, 20, 21, 22）都在 0 ~ 31 的范围内，用 5 bits 就能表示最大值 31。
• 但是 100 和 101 明显超过了 31，需要更多 bits 表示。
3.2 设定“主位宽”(b) 与“最大异常值数目”(e)
• PForDelta 常见做法：
1. 在批次中，大多数元素都可以用较小的位宽（例如 5 bits）来编码。
2. 少数超出此范围的元素（异常值，exception）要单独处理。
3. 压缩端需要记录异常值的 位置 与 真实值，解压时才能“打补丁”（patch）。
• 在此示例中，我们选择：
• 主位宽：5 bits（可表示范围 0~31）。
• 异常值：凡是差值大于 31 的，都视为异常值。这里 100 和 101 就是异常值。
3.3 拆分主数据区 & 异常值区
• 主数据区：
• 能够用 5 bits 表示的差值序列：[0, 5, 6, 20, 21, 22]
• 在实际的压缩格式中，这些 6 个数会打包（bit-packing）到连续的若干个 5-bit 段，比如：
• 0 -> 二进制 00000
• 5 -> 二进制 00101
• 6 -> 二进制 00110
• 20 -> 二进制 10100
• 21 -> 二进制 10101
• 22 -> 二进制 10110
• 这部分数据就可以非常紧凑地存储。
• 异常值区：
• 100, 101（差值都超出主位宽能表示的范围）
• 除了要存储这两个实际值（或者可以进一步差分存储），还需要记录它们分别对应在原批次中的位置（index），以便解压时“打补丁”。
• 例如，我们可能存储一个 “异常值位置数组”：[6, 7]（表示这两个异常值是本批次的第 6、7 号数字），然后存储异常值各自的完整位宽表示，或使用更灵活的方式进行压缩。
第四步：解压及“打补丁”
1. 解压时，首先读到 base = 100。
2. 读到 “主数据区”，用 5 bits 解出这 6 个数的差值：[0, 5, 6, 20, 21, 22]。
• 还原后分别加上 base = 100:
[100, 105, 106, 120, 121, 122]
3. 读到异常值区，获取 “异常值位置数组”和 “异常值本身”：
• 位置：[6, 7]
• 值：[100, 101]
4. 将这两个异常值“打补丁”回到相应位置：
• 原批次第 6 个整数（下标从 0 计）= 100 + 100 = 200
• 原批次第 7 个整数（下标从 0 计）= 100 + 101 = 201
5. 最终还原回完整序列：
[100, 105, 106, 120, 121, 122, 200, 201]
整体流程图示
1. 原始数据: [100, 105, 106, 120, 121, 122, 200, 201]
2. FOR (base=100): [0, 5, 6, 20, 21, 22, 100, 101]
3. 划分主数据区 (5 bits) 与异常值:
• 主数据区: [0, 5, 6, 20, 21, 22]
• 异常值区: 位置 [6, 7]，数值 [100, 101]
4. 存储:
• 主数据区（bit-packing using 5 bits each）
• 异常值区（包括异常值位置和完整数值）
5. 解压:
1. 从主数据区解出差值，加上 base 得到部分还原数据；
2. 从异常值区补足剩余值；
3. 恢复最终完整序列。
总结
• PForDelta 核心思路：对一批数据选取一个合适的位宽来编码“大部分”差值，然后将极少数超出这个位宽的值（异常值）打上特殊补丁。
• 优势：
• 主数据可紧凑存储，获得较高压缩率；
• 异常值较少时，对整体的编码/解码性能影响不大。
• 解压时：先对主数据区进行批量解码，再“打补丁”还原异常值。对于大规模的倒排索引或时间序列数据，这种方法可以在 空间占用 和 解压速度 之间取得很好平衡，也为后续利用 SIMD 并行解压打下基础。
这就是一个简单的 PForDelta 示例流程。真实生产环境中，还会考虑 批次大小、自适应位宽的选取策略、异常值最多可有多少、Delta Encoding 细节等，以进一步提升压缩比和解压速度。
=================
下面我们以一个具体的数字示例，来说明 PForDelta 是如何“省位宽”、从而体现出压缩能力的。示例中会对比 未压缩 与 PForDelta 压缩后 的大致存储大小，让你直观看到压缩效果。
示例数据
仍然使用下面 8 个整数作为示例：
[100, 105, 106, 120, 121, 122, 200, 201]
1. 未压缩存储大小
假设每个整数占用 32 位（4 字节），那么 8 个整数的存储总大小是：
8 × 4 字节 = 32 字节
PForDelta 压缩流程回顾
1. Frame-of-Reference (FOR)：
• 选取批次最小值 base = 100，将每个数减去 100 得到差值序列：
[0, 5, 6, 20, 21, 22, 100, 101]
2. 挑选主位宽 (b)：
• 观察差值序列可知，大多数数值（0, 5, 6, 20, 21, 22）都在 0~31 范围内，可用 5 bits 表示；但 100、101 超过了 31，属于异常值 (exceptions)。
• 因此，这里令“主位宽”= 5 bits。
3. 存主数据区 & 异常值区：
• 主数据区（可用 5 bits 的差值）：[0, 5, 6, 20, 21, 22]
• 异常值区：位置 [6, 7]，差值 [100, 101]（在真实实现中也可能再做一层差分或进一步压缩，但这里先按最简单方式看待）。
下面我们分别估算这几部分在存储时所需的空间。
2. PForDelta 压缩后各部分大小估算
注意：这是一个示例性的空间估算，实际生产环境中可能还有额外的元信息存储、块对齐方式等，但能帮助你理解 PForDelta 的压缩思路。
2.1 存储 base（参考值）
• 通常会用一个整型（例如 32 位）来存储批次的最小值 base = 100。
• 大小：4 字节
2.2 存储主数据区（6 个差值，主位宽 5 bits）
• 我们有 6 个差值都能用 5 bits 表示：
0 -> 二进制 00000
5 -> 二进制 00101
6 -> 二进制 00110
20 -> 二进制 10100
21 -> 二进制 10101
22 -> 二进制 10110
• 总共 6 × 5 = 30 bits ≈ 3.75 字节。
• 考虑到实际实现时往往会对齐到 1 字节或 4 字节的边界，这里先简单取整为 4 字节存储（或者可能打包成更大的块）。
所以主数据区大约占用：4 字节。
2.3 存储异常值区
这里包括两类信息：
1. 异常值的位置（exception positions）
• 本批次大小是 8，所以索引位置只需要 3 bits 就能区分 0~7 的位置。
• 有 2 个异常值 => 2 × 3 = 6 bits => ~0.75 字节。
• 同样为了对齐，实际实现往往会按字节或字对齐，这里粗略计为 1 字节。
2. 异常值的本身（exception values）
• 最简单的情况下，直接用 32 位存储每一个异常值的“差值”（也可能有更紧凑方式）。
• 2 个异常值 => 2 × 4 字节 = 8 字节。
所以异常值区大约占用：1（位置） + 8（实际值） = 9 字节。
2.4 压缩后总大小
将以上各部分相加：
• base：4 字节
• 主数据区：4 字节
• 异常值区：9 字节
合计：17 字节（示例性的粗略估算）
3. 对比未压缩数据
• 未压缩：32 字节
• PForDelta 压缩后（示例）：~17 字节
从 32 字节降到约 17 字节，压缩比大约是 32 / 17 ≈ 1.88，即原先需要 32 字节的存储，在该示例中只需约 53% 的空间。当然这是一个很小的批次示例，实际大批量数据通常会使用更大的批次大小（例如 128 或 256 个整数一块），并且往往会有更少的异常值、乃至更好的压缩效果。
4. 为什么“批次越大”往往会压缩得越好？
1. 当批次规模增大（比如一次处理 128 个整数），主位宽通常能更准确地贴近大部分数值的分布，使得“异常值”出现的频率更低。
2. “异常值”在大批次中的占比越小，主数据区就越紧凑，进而提高整体压缩率。
3. 存储 base 等“元信息”的开销也会分摊到更多数据上。
5. 小结：PForDelta 如何体现“压缩能力”
1. 主体用小位宽：绝大部分数值都用一个尽可能小的位宽进行紧凑编码（比如 5 bits），从而大幅减少整体的 bit 数量。
2. 少数异常值打补丁：把个别超出范围的数值分离出来单独存储。只要异常值不多，额外开销相对主数据区来说不算太大。
3. FOR / Delta 的帮助：
• 通过减去最小值（或相邻值），把数据分布向 0 附近集中，降低编码所需的位宽。
• 若再结合相邻差分、分块策略等，可进一步提升压缩比。
4. 大批次分块：在搜索引擎或日志分析这类高并发场景中，对海量整数进行批量压缩能带来更可观的空间节省，也为之后的 SIMD 并行解压 提供良好的数据布局。
最终，你可以将“压缩后占用多少字节”与“原始 32 位或 64 位整数的总字节数”做对比，看到 PForDelta 带来的压缩比例。这就是它在检索系统中广泛应用的原因：在保证解压速度的同时，又节省了大部分存储与 I/O 成本。
标签：解压,PForDelta,字节,压缩算法,压缩,SIMD,100,异常 From： https://www.cnblogs.com/zhangkele/p/18651865