交付一份共享随机键抽样记录
共享随机键与加权抽样路线最终交付四种结果:集合相似度指纹、可合并不同键摘要、固定子集权重估计,以及加权相似度指纹。它们都给对象安排随机位置,但对象身份、抽样阈值与目标量并不相同。交付物必须同时保存原始目标和实际状态,才能判断一个小数来自哪一种估计。
下载可执行核验器和完整结果JSON。只用Python标准库,普通执行与 python -O 使用同一批显式检查;任何失败都会抛异常。脚本有限排列与有理数部分给精确离散结果,CWS部分明确是浮点参考及数值诊断。
一、先冻结身份、权重和随机源
本次集合宇宙为0至5,共N=6;集合A={0,1,2}、B={1,2,3}。输入流可以包含重复,例如A流为0、1、0、2、1;重复键仍指同一集合成员。手算排列依次为0、1、2、3、4、5,名次从1开始,两侧共用。
另一份加权记录有不同ID 0、1、2、3,权重分别为2、5、1、3,U依次为1/2、1/2、1/5、3/4。这里每个ID只出现一次,权重已经冻结。若日志的目标单位原本是同键累计量,应先聚合,不能把本记录序列默认为一个已经支持任意计数更新的接口。
CWS单独使用二维向量s=(1,5)、v=(1,3)、w=(1,1)。各坐标共用R=log4、β=1/2,C=(2,1),并让三份输入共享同一参数表。三种向量的“坐标1”都指同一个属性,不能在输入之间重新编号。
一份可审核记录至少要写明:宇宙/坐标编码、容量或副本数、共同随机源身份、是否按不同键去重、是否按出现记录计数、是否已经聚合权重。附件的有限排列兼容性直接比较完整名次数组,没有把偶然相同的短配置指纹当成相同排列的证明。
二、从单个指纹到并集样本
MinHash在上述排列下给A选0、B选1,本副本不碰撞。真实Jaccard却是2/4=1/2,两者并不矛盾:一次碰撞只是0或1。把四个相关键的24个排列全部枚举,12次碰撞,才得到这组输入的精确概率。
Bottom-k摘要取k=2。A的候选按名次为[0,1],B为[1,2],两侧complete都为假。合并去重后候选是0、1、2,再截成C=[0,1];其中1在两侧局部样本都有,估计J为1/2。若直接把局部交集大小1除以局部并集大小3,本次得到1/3,全部排列的平均也只是4/9,不能用“更多随机试验”消除这个公式偏差。
A的第2小名次R=2,有限排列基数估计为6/(2−1)=6;B的R=3,估计为3。两集合真实大小都为3,这两份单次结果允许不同。对固定三键集合,在全部6!排列上平均才应得到3。
检查更新时,当前堆只保存两个键及名次,字典也只保存候选。已经淘汰的键再次到来,其固定名次不可能低于不断下降的保留阈值,所以无需另存全体历史去重集合。
三、额外一名决定总量修正
优先级抽样取k=2,四个优先级分别为4、10、5、4。堆保留前k+1名,即ID1、2、0;ID0与ID3并列时按较小ID优先。前两名参与估计,第三名只确定τ=4。
ID1贡献max(5,4)=5,ID2贡献max(1,4)=4,所以全体权重估计9,真实总量11。查询固定子集I={0,2}时只见入选的ID2,估计4,真实为3。无偏性并不使每份摘要精确;它由条件于其它记录优先级后的一维均匀积分保证。
容量至少2时,这份样本的全体方差估计为12,来自ID2的4(4−1);ID1原权重高于门槛,贡献为零。请分别写“原权重”“修正贡献”“方差估计”,不要把同一个数字栏位混用。
把ID0、2放进一个分片,ID1、3放另一个,分别保留前3名后合并,与集中前3名完全相同。若改成同一个ID在两片各给部分权重,这个互斥记录合并接口就不适用;应先说明目标是否要将它们聚成一条记录。
四、对数格点的两次缩权
一致加权抽样先逐坐标计算t、y、z、a。对s=(1,5),两坐标分别为:
| 坐标 | t | y | z | a |
|---|---|---|---|---|
| 0 | 0 | 1/2 | 2 | 1 |
| 1 | 1 | 2 | 8 | 1/8 |
坐标1胜出,完整指纹为(1,1)。缩为v=(1,3)后,旧点高度2还在新区间内,格点与分数不变,仍输出(1,1)。再缩为w=(1,1),旧点已在外面,坐标1改为t=0、y=1/2、z=2、a=1/2,指纹变为(1,0)。
三次胜出坐标都为1,但最后的格点整数变了。只保留坐标会丢掉所需区别。更短的失败例是只有一个正坐标、两权重为1和2:只比坐标永远碰撞,正确加权Jaccard却是1/2。
一般概率证明须交出两份证据。第一份是变量变换:固定权重后V=R{log(s)/R+β}、W=R−V的联合密度分解为e^(−v)e^(−w),从而y均匀且与指数比赛分数独立。第二份是固定参数后缩权:其它分数只能上升,仍覆盖旧点的胜出坐标分数不变。模拟频率不能替代其中任何一份。
五、结构迁移:换目标后重新判断接口
重放与删除
将A流改为2、2、1、0、1、2,保留集合含义不变;逐前缀核候选和complete。再构造两个原集合,它们在同一排列下都只保存[0,1],但删除0后应补回不同键。说明仅有前二摘要无法同时给两者正确恢复结果,而不仅是调用一个不存在的delete函数。
阈值不等于名次
把优先级记录0的权重从2改成20,保持它的U为1/2,重新计算前3名和τ,再查询同一固定子集I。这会改变抽样排序及补偿门槛。禁止只在旧样本上修改显示的w然后复用旧τ;新目标已经需要重新处理该记录集合。
固定子集与依赖样本的挑选
分别给出一个抽样后才提出、但成员由固定属性决定的子集,以及一个读过U或样本后才确定成员的子集。只对前者引用固定子集无偏定理。解释晚提出问题本身不是障碍,依赖抽样随机性的挑选才改变了证明量词。
共享参数与坐标聚合
在两个权向量增加第三坐标,权重分别为0与4,并为该坐标加入共同R、C、β。原有两坐标参数不得重抽。手算新并集面积、交叠面积与加权Jaccard,记录新坐标是否胜出;再把一侧同坐标的两条贡献先相加后运行,与错误地拆成两个不同坐标进行对照。
六、执行记录与验收
核验器普通与优化模式的确定性输出必须逐字节相同。发布结果至少包括:
- N=4的6144组集合对/排列MinHash碰撞检查,以及仿射模5族的7、6、7最小键次数
- 247016组有限排列基数状态,24576组摘要合并及Jaccard均值/方差,20000个有重复输入的前缀不变量
- 4000份有理优先级记录历史,逐前缀堆与全排序一致、互斥分片合并一致,以及1620个条件门槛精确积分
- 轻项在有限U网格永不入选的反例;它作为预期失败模型被检查,不应被改成“无偏通过”
- CWS手算三指纹、数值缩权检查、并集点与两侧碰撞的对应;附模拟次数和碰撞频率,但明确这一栏仅为数值诊断
参考执行不验证未知调用方是否重复使用记录ID,完整参数表也不包含在O(k)或O(q)的每对象摘要账中。合格交付要报告这两项输入和空间边界。最终目录包含运行命令、结果JSON、关键状态、一般证明和一个跨接口误用反例;只给所有检查“PASS”无法解释为何抽样在这个统计目标上正确。