知识卡片
插值编码：用双向已知边界代替单向递推
内容
普通文档间隔编码是单向的——只用”前一个数是多少”推算当前数的编码范围。插值编码换了顺序：先编码列表中间位置的数，再递归对左右两半分别编码，这样编码某数时它的左右两侧都已有确定边界，能用的编码位数由这个区间宽度决定。存在聚类时，双向夹逼能把区间收窄到只剩一两个可能值，理论上可用不到1比特表示一个数，代价是实现更复杂（需维护端点栈递归处理）。
参考来源
- 位置：第3章《索引》「插值编码」小节（源文件：_chapter-text/ch03.txt）
- 结论依据：原文说明插值编码先编码中间位置数值，再递归对左右两半编码，利用双向已知边界收缩取值范围，实现复杂但压缩效果通常优于Golomb编码，直接支持卡片论点。
- 原始内容："这个插值编码（interpolative code）用下面这个例子阐述是再好也不过了……该方法仅有的一个缺点是实现复杂，编码和每次解码都需要利用一个端值构成的栈……插值编码在所有的4个测试文件中给出的结果最为突出。"