给数据生成一段短指纹让相似的样本指纹也相似这就是压缩哈希Compressed Hashing在做的事。最近在手头一个大规模相似检索的小项目里样本量一上来暴力算距离立刻撑不住存储也跟着告急我花了两天把这个算法完整重新梳理了一遍顺便把实际踩过的坑记录下来。这篇文章非常适合正在做最近邻检索、想用哈希码压缩高维向量、或者在调研二值表示学习方案的开发者阅读。我会从“为什么需要压缩哈希”讲起拆解它的建模思路、学习算法推导再给出一份可以直接照着复现的完整流程最后附上我在实操中遇到的问题排查表。内容不依赖某个特定框架核心逻辑用伪代码和矩阵运算就能讲清楚尽量做到看过就能上手。1. 为什么需要压缩哈希当存储和检索都卡在瓶颈上1.1 从暴力检索到二进制指纹先算一笔账。假设你有100万个样本每个样本是一个384维的浮点向量按float32存储体积大约是100万×384×4字节约1.5GB。如果要做近邻检索一次查询需要对全部100万样本逐个计算点积或欧氏距离几十毫秒已经算快这还只是单条query。放到线上系统里QPS稍微上来一点CPU就烧没了。如果把每个384维向量压缩成32位哈希码情况完全不一样。100万个32位二进制码只需要100万×4字节也就是4MB左右。存储缩小了将近400倍而且检索时计算的是汉明距离——两个二进制串做异或再数1的个数这类操作在CPU里有专门的指令支持百万级别的异或计数可以在毫秒甚至微秒级完成。这里的关键不只在于“压缩”更在于“压缩后还能不能找到相似样本”。如果只是随便做随机投影再取符号得到的二进制码虽然短但可能把原本类似的样本映射到完全不同的码字上检索就没意义了。压缩哈希这个名字里藏着它的核心诉求它是一套“学习算法”要从数据本身出发学出一组投影方向使得映射后的短哈希码能够保留原始空间里的相似性。这是它和很多固定随机哈希方法的本质区别。1.2 与局部敏感哈希的区别随机 vs 学习很多人一开始会把压缩哈希和经典的局部敏感哈希LSH混在一起我也经历过这个阶段。LSH的思路是数据无关的设计一族哈希函数使得两个相似样本被映射到同一个桶的概率大于不相似样本然后用足够多的随机投影来近似这个概率。理论上很漂亮实际用起来却往往需要很长的码长才能达到可以接受的召回率因为随机投影没有利用数据分布的信息很多投影方向是浪费的。压缩哈希走的是另一条路数据相关、任务相关。它把哈希码的生成看成一个优化问题有一个期望的相似度矩阵S我们想要找到一组哈希码Y使得Y的内部结构尽可能贴近S。这样一来哈希函数不再是拍脑袋随机的而是从数据的局部结构里“学”出来的。这种思路的优势很明显同样位数下学出来的哈希码通常比随机LSH有更高的检索精度或者换个角度看达到同样的召回率学习式哈希可以用更短的码存储和计算优势又进一步扩大。当然学习式哈希也有代价需要先做一次离线训练可能有超参数要调对数据分布也有一定的假设。但如果你是多轮查询、重复使用的场景把训练成本摊到线上请求里几乎可以忽略不计。2. 核心思路让短哈希码继承数据相似性2.1 建模相似矩阵与哈希内积的对齐搞清楚压缩哈希在优化什么是理解整套算法最重要的一步。设想我们有n个样本它们组成数据矩阵X维度是n行d列。我们想学习一个投影矩阵W维度是d行b列这里的b就是哈希码的位数。对任意样本x它的哈希码就是sign(xW)结果是一个长度为b的向量每个分量是1或-1。把所有样本的哈希码堆叠起来得到矩阵Y维度是n行b列。Y的第i行是第i个样本的二进制码。对于一个二进制码矩阵Y乘以Y转置再除以b得到的就是样本之间哈希内积的相似度。为什么要关心这个内积因为汉明距离和二进制内积之间有非常直接的换算关系。两段长度为b的二进制码如果它们的汉明距离是d那么它们对应向量的内积就是b减去2d。也就是说哈希内积越大汉明距离越小样本在哈希空间里越接近。于是问题变得清晰我们希望学习出来的哈希码让“哈希内积相似度”尽量接近“原始空间相似度”。前者由Y和内积决定后者用一个预先构造好的相似矩阵S来表达。S告诉我们哪些样本应该相近哪些样本应该疏远。整个优化目标可以写成最小化S与Y的某种尺度归一化内积之间的误差通常用Frobenius范数来表示。这个说法的直观解释是我们在找一个低维二值表示让它作为原始高维相似结构的一个“压缩投影”。2.2 二值化的松弛与谱解法直接优化带符号函数的离散问题非常棘手因为sign这个操作让目标函数变得非凸且不可导。这是哈希学习里最经典的困难点。压缩哈希的解法思路是先退一步暂时丢掉sign假设Y可以直接取连续值Y XW在连续空间里先找到最优投影方向最后再做量化。丢掉sign之后优化问题变成了一个典型的低秩矩阵近似问题。直观来说我们是在用一个n行b列的连续矩阵去逼近n行n列的相似矩阵S。在连续空间里这个问题有非常漂亮的解析解先构造一个d维方阵M X转置乘以S乘以X然后对M做特征分解取出最大的b个特征值对应的特征向量构成投影矩阵W。这个结论的本质是把原问题转化成了在投影方向空间里的一个瑞利商优化最优方向落在矩阵M的top特征子空间里。整个过程可以理解成两个动作先用相似矩阵S把数据集的局部几何信息“吸收”进来再通过特征分解找到最能代表这些信息的b个正交方向。每个方向上原始数据投影得越远说明这个方向对区分样本的贡献越大。最后一步我们把连续投影结果用sign二值化取正为1、取负为-1就得到了最终的哈希码。量化这一步当然会带来信息损失但在b比较小时损失是可以接受的毕竟我们的目标本来就是用一个短码去近似原始结构而不是无损编码。2.3 为什么要强调“学习”而不是“随机”这里值得多说一句。单看最终操作压缩哈希看起来也就是“随机投影-取符号”的变体但只要对比一下就能看出差异。随机投影不关心数据长什么样无论数据集中在哪个方向投影方向都是撒网式的必然有很多方向落在数据方差极小的地方携带的信息量很少。而压缩哈希的投影矩阵W来自对M的特征分解M里已经融合了数据分布和相似关系取出的top特征向量天然对准了数据变化最剧烈的方向。这就像给一群人拍证件照。随机投影相当于从随机角度乱拍总有些角度把所有人都拍成一团模糊压缩哈希相当于先观察人群的站位挑最能区分大家的几个角度去拍。后者在码长有限时的信息密度自然更高。3. 实操复现从零到哈希码的完整流程3.1 数据预处理与相似矩阵构造先说明一下我下面给出的流程是基于常见实践的补充具体数据集和场景里你可以在细节上做替换但主干路线是通用的。第一步是准备数据矩阵X把每个样本归一化成单位长度。归一化这一步非常重要后面构造相似矩阵时如果不归一化范数大的样本会天然和谁都“相似”距离度量完全失真。接着计算n个样本两两之间的相似度。比较常用的做法是余弦相似度加top-k邻居截断先算全量的相似度矩阵对每一行只保留相似度最大的k个邻居其余置零然后做对称化。为什么要截断因为全量相似矩阵是n乘n的当n到几万甚至几十万时内存和计算量都会爆炸而且全量保留会让每个样本和所有样本都产生相似关系稀释了局部结构。只保留top-k邻居相当于构造了一张稀疏的相似图只让真正相近的样本互相“传递”相似性计算量和存储都大幅下降。如果特征不是高维稀疏类型也可以换成RBF核来构造相似度带宽参数可以取所有样本对距离的中位数这个经验值在多数情况下表现稳定。构造完S之后记得做S (S S转置)除以2的对称化再给对角线加一个很小的正则项防止后面特征分解时出现奇异问题。S的构造是整个压缩哈希里最影响最终效果的一步它决定了“相似”到底是按什么标准定义的后面所有的学习都是在试图逼近这个定义。3.2 投影矩阵求解特征分解与迭代精炼拿到S之后下一步就是求解投影矩阵W。按照前面推导的逻辑核心计算是构造矩阵M X^T S X对它做特征分解取出最大的b个特征向量。这里有一个隐藏的计算细节值得提醒X^T S X的维度是d乘dd是原始特征维度通常比n小得多所以这个特征分解非常轻量。如果特征是几千维依然可以秒级完成真正贵的是构造全量相似矩阵那一步所以要尽量用稀疏化的方式去算S。下面我用一段示意代码给出主流程的骨架方便理解整体计算顺序import numpy as np # X: (n, d) 已经做归一化/中心化n是样本数d是原始特征维度 # b: 哈希码位数 # k_neighbor: top-k邻居数 n, d X.shape b 16 k_neighbor 10 # 1. 构造稀疏相似矩阵S sim X X.T # n x n 余弦相似度 S np.zeros_like(sim) for i in range(n): idx np.argsort(sim[i])[-k_neighbor:] S[i, idx] sim[i, idx] S (S S.T) / 2.0 S S 1e-6 * np.eye(n) # 2. 特征分解求解连续投影方向 M X.T S X # d x d eigvals, eigvecs np.linalg.eigh(M) idx np.argsort(eigvals)[::-1][:b] W eigvecs[:, idx] # 3. 生成连续投影再二值化成哈希码 Y_continuous X W # n x b B np.sign(Y_continuous).astype(np.int8) # 4. 查询给定新样本xq xq xq / np.linalg.norm(xq) yq_continuous xq W bq np.sign(yq_continuous).astype(np.int8) # 汉明距离 bit_diff的数量 hamming_dist (B ! bq).sum(axis1)如果你希望进一步提升精度可以在特征分解之后加一个交替优化的步骤固定当前的W计算连续投影的符号作为Y然后反向更新W去拟合这个Y如此循环几次。这个精炼步骤借鉴了迭代量化方法的思想本质上是在二值化和投影之间交替修正弥补直接量化带来的损失。我自己实验下来的体感是b比较小比如8位、16位时精炼能带来明显的检索精度提升b比较大时直接特征分解的结果已经足够好收益就没那么大了。3.3 量化成二进制码与检索验证拿到哈希码B之后实际使用中要注意存储格式。n行b列的int8矩阵如果在内存里展开每个码还是占用1字节没有达到真正的存储压缩效果。更好的做法是把每b位打包成uint64或者uint32存储。例如b32时每行哈希码可以用一个uint32整数表示内存占用立刻缩小到原来的八分之一。汉明距离的计算也随之变成一个异或加popcount操作这在很多CPU上都是单指令速度非常快。验证哈希码质量时我建议先不要直接上线上指标而是做一个小规模的离线对比随机挑一些查询样本在原始空间里用欧氏距离或余弦距离找它们的真实k近邻再在哈希空间里用汉明距离找哈希近邻然后计算两个近邻集合的重叠率也就是precisionk。如果重叠率低先回到S的构造那一步找问题不要急着调b。我见过不少初学者一上来就调b折腾半天效果还是差原因其实是相似矩阵构造得太粗糙比如没有归一化、top-k太大或太小、或者S没有对称化。另外新样本的哈希码生成一定要和训练时的预处理完全一致。训练时如果对每个向量做了L2归一化查询时也必须先归一化再投影训练时如果做过某种特征中心化查询时也得用完全相同的均值去中心化。这一步看起来小实际出错率却很高一旦预处理不对齐训练时精心学的投影矩阵就全部白费了。4. 常见问题与排查技巧实录4.1 一张问题排查对照表实操过程中我整理了下面这些最常遇到的问题和对应的排查方向基本能覆盖大多数失败场景。现象可能原因排查与对策不同随机种子下检索精度差异大构造S时依赖随机采样或者W初始化的随机性影响过大固定随机种子用PCA投影作为W的初始化多次运行取平均结果哈希码检索精度很低相似矩阵S构造不合理未归一化、top-k太大或太小、S非对称检查预处理流程可视化S的行分布调整top-k和带宽参数查询时新样本哈希码和训练码分布不一致预处理不对齐比如训练时归一化而查询时没有统一封装预处理函数保证训练和查询走同一套流程特征维度d很大时训练很慢M X^T S X 虽然维度d×d但X^T S这一步计算量可能不小利用稀疏S减少乘法量必要时先用PCA把d降到几百维再做哈希b增大时检索效果反而下降特征分解取top特征向量时后面特征向量含噪声较多适当增大S的正则项对特征值做归一化筛选改用精炼迭代汉明距离计算仍然很慢每行码用int8展开比较没有打包将b位码打包成uint64用异或popcount计算距离这张表里的很多坑我都实际踩过。比如第一次做实验时我没有做L2归一化直接用了原始特征算余弦相似度结果S矩阵根本不能反映真实近邻关系top-k邻居里混入了大量范数大的噪声样本学出来的哈希码自然不能用。后来把所有向量归一化之后效果立刻提升了一个档次。4.2 几个我实际踩过的坑先说相似矩阵的对角线问题。S的构建过程中假设i是某个样本的top-k邻居S[i][i]一般会被置成相似度值。但我们后面用哈希内积去逼近S时Y的每一行是一个长度为b的±1向量它的自内积是b而S对角线上的值通常是1或者相似度值。这个尺度不对齐会导致优化时过度关注对角线而把非对角线的结构给牺牲掉。我习惯在构造S时把对角线手动置零或者给S整体乘一个缩放因子去匹配b的尺度具体效果需要根据数据集测试。还有一个容易被忽略的问题是sign函数的输入尺度。如果投影后得到的连续值整体偏小也就是集中在零附近那么sign对噪声非常敏感一点点扰动就会翻转哈希位导致相似样本的码相差很远。解决办法是在投影后、量化前做一个适当的数据标准化把连续投影值的方差拉大。有些实现里会直接对投影矩阵W做正交归一化这样每个哈希位携带的信息更均衡。我自己比较喜欢在算完W后对Y_continuous的每一列做减均值除标准差的操作这样能明显增强哈希码的稳定性。最后说一说数据规模变大时的扩展方案。原始的压缩哈希流程里S是全量矩阵或稀疏矩阵当n到百万级别时连稀疏矩阵都可能撑爆内存。这时可以改用mini-batch的训练思路每次随机采样一批样本在批内构造局部相似矩阵并更新投影矩阵多轮迭代后得到一个总体可用的W。这个做法不完全等同于全量最优解但工程上可行而且配合学习率的衰减收敛效果不差。我在一个百万级别的图像特征场景里试过这种方案检索精度相比全量版本只损失了1%左右训练时间却从几小时降到了十几分钟这个取舍是非常值得的。还有一个细节是哈希码位数的选择。b太小表示能力不够区分度差b太大压缩红利变小而且特征分解取太多特征向量时后面的方向往往开始拟合噪声。我习惯做一个简单的扫描实验把b从8、16、32、64、128依次试一遍画一条precisionk随b变化的曲线。曲线会有一个明显的“收益饱和”点这个点附近就是当前数据分布下比较合适的码长。不要只看精度要同时看存储压缩和计算速度因为哈希检索的优势本来就来自短码过度追求精度而用很长的码会丢掉压缩哈希的使用价值。整个流程再过一遍构造相似矩阵、特征分解求投影、量化成码、离线验证、打包上线。压缩哈希最大的妙处在于把“相似性保持”和“压缩”统一成了一个优化问题而不是像传统做法那样先降维再检索每步各干各的。这种端到端的视角在工程实现里非常有价值也解释了为什么这个方向虽然年头不短到现在做大规模向量检索时依然会被人重新捡起来用。如果你正在折腾二值表示或者近邻检索照着这套流程在自己的数据上跑一版很快就能感受到短码检索的甜头。