6

我有一个过程，类似于生成感知散列的 tineye，这些是 32 位整数。

我打算将来将这些存储在 sql 数据库（可能是 nosql db）中

但是，我对如何根据哈希的相似性检索记录感到困惑。

有任何想法吗？

4

3 回答 3

14

一种常见的方法（至少对我来说很常见）是将您的哈希位字符串分成几个块，并在这些块上查询精确匹配。这是一个“预过滤”步骤。然后，您可以对返回的结果执行按位汉明距离计算，这应该只是整个数据集的一小部分。这可以使用数据文件或 SQL 表来完成。

简单来说：假设您在数据库中有一堆 32 位哈希，并且您希望找到在“查询”哈希的 4 位汉明距离内的每个哈希：

  1. 创建一个包含四列的表：每列将包含 32 位散列的 8 位（作为字符串或 int）切片，即 1 到 4 切片。

  2. 在 qslice 1 到 4 中以相同的方式对查询散列进行切片。

  3. 查询此表，以便任何qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. 4 - 1这为您提供了查询哈希3 位 ( ) 内的每个 DB哈希。

  4. 对于每个返回的哈希，使用查询哈希计算精确的汉明距离（从四个切片重建索引侧哈希）

步骤 4 中的操作数应该比整个表的完整成对汉明计算少得多。

Moses Charikar在其“simhash”开创性论文和相应的 Google专利中首先描述了这种方法：

  1. 汉明空间中的近似最近邻搜索

[...]

给定每个由 d 位组成的位向量，我们选择 N = O(n 1/(1+ ) ) 个位的随机排列。对于每个随机排列 σ，我们维护位向量的排序顺序 O σ，按照由 σ 排列的位的字典顺序。给定一个查询位向量 q，我们通过执行以下操作找到近似最近邻：

对于每个置换 σ，我们对 O σ 执行二分搜索以定位最接近 q 的两个位向量（按照由 σ 置换的位获得的字典顺序）。我们现在按照与 q 匹配的最长前缀的长度的顺序在每个排序顺序 O σ 中搜索由二分搜索返回的位置上方和下方的元素。

Monika Henziger在她的论文“寻找近乎重复的网页：算法的大规模评估”中对此进行了扩展：

3.3 算法 C 的结果

我们将每个页面的位串分成 12 个不重叠的 4 字节片段，创建 20B 个片段，并计算至少有一个共同片段的所有页面的 C 相似度。这种方法可以保证找到差异高达 11 的所有页面对，即 C 相似度 373，但可能会因为更大的差异而遗漏一些。

Gurmeet Singh Manku、Arvind Jain 和 Anish Das Sarma在Detecting Near-Duplicates for Web Crawling的论文中也解释了这一点：

  1. 汉明距离问题

定义：给定一组 f 位指纹和一个查询指纹 F，识别现有指纹是否与 F 最多 k 位不同。（在上述问题的批处理模式版本中，我们有一组查询指纹而不是单个查询指纹）

[...]

直觉：考虑一个 2 df 位真正随机指纹的排序表。只关注表中最重要的 d 位。这些 d 位数字的列表相当于“几乎一个计数器”，因为 (a) 存在相当多的 2 d 位组合，并且 (b) 很少有 d 位组合是重复的。另一方面，最低有效的 f-d 位是“几乎随机的”。

现在选择 d 使得 |d − d| 是一个小整数。由于该表已排序，因此单个探针足以识别在 d 个最高有效位位置中与 F 匹配的所有指纹。由于|d - d| 小，这样的比赛的数量预计也很少。对于每个匹配的指纹，我们可以很容易地确定它是否与 F 最多 k 位位置不同（这些差异自然会限制在 f - d 个最低有效位位置）。

上面描述的过程帮助我们在 k 位位置上找到与 F 不同的现有指纹，所有这些都被限制在 F 的最低有效 f-d 位之间。这处理了相当多的情况。为了涵盖所有情况，只需构建少量额外的排序表就足够了，如下一节中正式概述的那样。

PS：这些优秀的大脑中的大多数都/曾经在某种程度上与谷歌相关联，FWIW。

于 2017-11-25T16:07:25.193 回答
1

要找到汉明距离，您可以使用按位加法和减法（整数上的 & 和 ~）来计算这些距离。

SQL 不适用于此类处理。对大型数据集的比较变得非常混乱，并且不会具有利用系统强度的查询速度。也就是说，我做过类似的事情。

这会给你带来个体差异，这需要在完整的数据集上运行并排序，这充其量是混乱的。如果您希望它运行得更快，您将需要使用按“区域”索引或在数据中查找自然分组等策略。有伞形聚类策略，和类似的——有很多文献。然而，它在大多数传统的数据库系统中会很混乱。

于 2012-06-22T14:31:20.213 回答
1

大卫的讨论是正确的，但如果你没有很多数据，请查看SQL 中二进制字符串的汉明距离

于 2013-04-01T21:43:24.013 回答