我正在尝试实现一个通用的指纹记忆器：我们有一个可以通过智能指纹表示的文件（如图像的pHash或音频的色度图），如果我们想要的（昂贵的）函数已经在类似的文件上计算，然后我们返回相同的结果（避免昂贵的计算）。
局部敏感哈希(LSH) 是一种流行且性能良好的解决方案，用于解决昂贵的多维空间中的近似最近邻问题。
pHash是一个很好的库，它实现了图像的感知散列。
因此 pHash 将多维输入（图像）转换为一维对象（哈希码），这与 LSH（同样，LSH 中的多维对象）有所不同。
所以我想知道我们如何为 pHash 哈希值实现一维 LSH？或者简而言之：我们如何将相似的 pHash 值分组？它可以替代经典的 LSH 方法（如果不是为什么）？
您可以使用n 随机投影将 pHash 空间拆分为2^n桶，然后最有可能从同一个桶中找到相似的图像。您甚至可以使用汉明权重为 1 的所有 64 个可能整数对哈希进行异或运算，以方便地检查相邻的桶，并确保您找到所有近似匹配项。
仅当您对哈希值几乎相同（小汉明距离）的图像感兴趣时，这才有效。如果您想容忍更大的汉明距离（例如 8），那么高效准确地找到所有匹配项会变得很棘手。通过 GPU扫描整个表，我获得了非常好的性能，即使我 3 岁的笔记本电脑的 GT 650M 也可以检查 7 亿哈希/秒！
编辑 1：您可以将 64 位散列视为 64 维立方体上的单个角，如果将角坐标标准化为-1和1（这样它的中心位于原点），数学会更容易。您可以将图像表示为大小m矩阵（一行/图像，一位哈希/列）。Mm x 64
将其拆分为2^n不同组的最简单方法是生成n64 维向量v_0, v_1, ..., v_n（从正态分布 N(0,1) 中选择每个向量元素），这可以表示为V大小矩阵64 x n（一列/向量）。正如随机投影中提到的那样，可能会执行正交性，但我将在此处跳过它。
现在通过计算A = (M * V) > 0得到m x n矩阵（一个图像/行，一个投影/列）。接下来将每一行的二进制表示转换为一个数字，您会得到2^n不同的可能性，并且相似的哈希最有可能最终出现在同一个桶中。
该算法适用于数据的任何正交表示（例如SURF特征），而不仅仅是二进制字符串。我确信二进制哈希有更简单（计算效率更高）的算法，但这是实现随机投影的一种方法。
我建议使用 XORring，因为如果图像没有相同的哈希值，则不能保证它们最终会出现在同一个存储桶中。通过检查与原始哈希的所有可能的小偏差，您可以查看哪些其他 bin 可能匹配。
在某种程度上，这类似于计算机游戏引擎如何将 2D 地图拆分为大小为 的单元格网格x，然后要从一个点查找半径内的所有单元，x您只需要检查 9 个单元格（包含该点的单元格 + 8周围的细胞）以获得 100% 准确的答案。