Skip to content

沿分块压缩路线,先完成RRR类别/偏移,再完成分块Elias–Fano。交付物是可从字节独立解码的记录,不是仅给几个压缩率数字。

下载标准库执行器,运行 python algorithms-block-compression-check.py。程序只写标准输出,python -O也保留所有显式检查;可与完整结果JSON逐项对照。两种教学格式由调用者分别选择解码器,未加入统一文件类型标记。

一、逐位还原RRR文件 ​

取32位输入

text
00000000 11111111 10101010 00010000

使用块宽8、每大块2个小块。交付四块的真实长度、类别、组合秩与偏移宽度;第三块必须得到类别4、秩20、七位码 0010100,末块类别1、秩3、三位码 011。

接着交出全局和局部目录。两个大块的全局项是 (0,0)、(8,0);四个局部项依次为 (0,0)、(0,0)、(0,0)、(4,7)。每对的第一个数计此前1数,第二个数计此前偏移位数,不能交换。

完整账单为:头33、类别16、全局目录24、局部目录40、偏移10,共123有效位,补五位零后占16字节。最终字节必须为

text
042211a5042080010000000000439460

从这份字节重新构造 RRR,不用保留原位串,核rank(21)=11、select(11)=20、select(14)无值,以及全部access。说明这个小例的类内负载虽短,完整文件为什么仍比原32位更长。

二、对同一集合走另一条查询路线 ​

将上面位串的1位置列成

text
8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 27

在宇宙 [0,32) 中运行分块EF。最优方案只有一块,使用28位BITMAP负载;18位目录加29位头,得到75有效位、10字节。它保存的对象与上面的RRR相同,但块内信息、目录布局和查询方法不同。

把 next_geq(i) 返回的序列下标读作“小于i的元素数”;若没有后继,则这个数等于集合大小13。由此重新核RRR的全部rank。第k个1就是整数列access(k−1),从而核全部select。位位置i的access则检查后继数值是否恰等于i,不能把整数列access(i)当成原位串第i位。

三、用完整账单认证最优分区 ​

改用宇宙1024中的八项

text
0, 1, 2, 3, 1000, 1001, 1002, 1003

交付 W=10,C=4,P=7,F=23,以及完整DP表

text
0, 23, 23, 23, 23, 58, 68, 77, 81

最优回溯链是 8 → 5 → 4 → 0。三块模式依次为ALL、EF、ALL;目录 (模式,末值,累计元素数,负载起点) 为

text
(0,    3, 4,  0)
(2, 1000, 5,  0)
(0, 1003, 8, 12)

中间块基数4,局部值996;低九位表示484,一元高位串为 010。请把九位低位与三位高位按格式顺序写出,再复算69位目录、12位负载和39位头,总长120位。字节为

text
1200400318006802fa1401f5c0cf22

核access(6)=1002,next_geq(500)=(4,1000),next_geq(1004)无值。然后独立枚举七个潜在切点的128种选择,给每一种支付完整目录费,确认没有账单低于81。强制一块得到134有效位,强制八块得到235有效位;如果你的优化器偏好八块,先检查是否忘记每块23位目录。

四、迁移到不同密度与非法码 ​

同样八项、宇宙1024,连续列0到7只需一块ALL,总有效长度62位;间距128的列0到896选择一块EF,总长133位。解释为什么“全局N/U相同”不足以推断局部最优分界。

RRR再采用两条4096位输入,块宽64、每大块16块。第一条为2048个0接2048个1;第二条为交替的01重复2048次。它们长度和1数相同,但前者偏移负载0、总长2033位,后者偏移负载3904、总长5937位。这里实际执行组合逆秩,没有构造大小为2^64的微表;这些可调参数例不冒用渐近微表的常数查询速度。

最后提交18项真实拒绝记录,包括布尔值冒充位、零块宽、越界查询、重复整数、漏切点、截断/额外字节、未用类别码、模式3、错误负载指针和非零字节填充。把第三块七位偏移改为127时,位宽仍正确,但127不在70种排列的编号范围内,必须拒绝。

报告结尾分别回答:存了多少实际字节,装载验证经过哪些数据,单次查询解了哪个块,DP在哪个固定格式内最优。原始输入、临时解码列表和Python对象开销也占运行内存;文件长度不等于进程内存大小。