汉明距离/相似度在数据库中的应用

Question

汉明距离/相似度在数据库中的应用

sqlsearchnosqlsimilarityhamming-distance

10

我有一个进程，类似于tineye，可以生成感知哈希值，这些值是32位整数。

我打算将它们存储在sql数据库中（可能是nosql数据库）。

但是，我不知道如何根据哈希值的相似性检索记录。

你有什么想法吗？

- oPless

可能需要更多信息：您是否考虑了二进制表示的汉明距离，还是其他什么？ - nickgrim

我将考虑从图像中获取的哈希值与数据库中存储的哈希值之间的汉明距离。 - oPless

我的意思是：除非我误解了，海明距离是一对“字符串”的属性，而你有整数。你是如何将整数转换为字符串的 - 是32个1和0，还是其他方式？ - nickgrim

你把数学术语和字符串类型搞混了。整数可以看作是由'0'和'1'元素组成的列表。而“字符串”类型只是一个字节列表（我们不讨论DBCS和Unicode）。 - oPless

3个回答

3

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

- riothamus

1

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

SQL不适用于这种类型的处理。大数据集上的比较变得非常混乱，并且不会具有利用系统优势的查询速度。话虽如此，我做过类似的事情。

这将为您提供单个差异，需要在完整数据集上运行并排序，这最好是混乱的。如果您希望它运行得更快，您需要使用诸如按“区域”索引或查找数据中的自然分组等策略。有伞形聚类策略和类似的策略 - 有很多文献。但是，在大多数传统数据库系统中，这将是混乱的。

- David Manheim

1

正如您从相关的问题和答案中所看到的，几乎所有的建议都没有使用数据库。 - David Manheim

2

就我所知，许多人认为你所谓的“巧妙技巧”是有界汉明距离查询的最新技术；）... 我同意SQL在这方面并不是万能解决方案（如果使用排序文件和二分查找，则此技巧同样有效甚至更好）。 - Philippe Ombredanne

1

聪明的技巧是将其实现在SQL中，而不是方法本身！ - David Manheim

1

@David Manheim - 我不确定是谁给你点了踩，但是Phillipe的回答对我遇到的问题进行了更深入的讨论。 - oPless

1

@oPless - 绝对同意！ - David Manheim

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Philippe Ombredanne · Accepted Answer

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

因此，简单地说：假设您在DB中有一堆32位哈希，并且您想要找到与您的“查询”哈希相差4位汉明距离的每个哈希：

1. 创建一个具有四个列的表：每个列都包含32位哈希的8位（作为字符串或int）切片，islice 1到4。 2. 将查询哈希以相同的方式切片为qslice 1到4。 3. 查询此表，以使任何qslice1=islice1或qslice2=islice2或qslice3=islice3或qslice4=islice4。这会给您每个DB哈希，其与查询哈希相差3位（4-1）。它可能包含更多结果，这就是为什么有第4步的原因。 4. 对于每个返回的哈希，使用您的查询哈希逐一计算精确的汉明距离（从四个切片重建索引侧哈希）

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

据我所知，这种方法最早由Moses Charikar在其"simhash"开创性paper和相应的Googlepatent中描述：

在汉明空间中进行近似最近邻搜索

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

对于每个排列σ，我们在O σ上执行二分搜索以定位距离q最近的两个位向量（按σ排列的位获得的词典顺序）。现在，我们在每个排序顺序O σ中搜索，在匹配q的最长前缀的长度的顺序下检查在二进制搜索返回的位置上方和下方的元素。

Monika Henziger在她的论文中详细阐述了算法"Finding near-duplicate web pages: a large-scale evaluation of algorithms"的内容：

3.3 算法C的结果

我们将每个页面的位串分成12个不重叠的4字节块，共创建20B块，并计算所有具有至少一个公共块的页面的C相似度。这种方法保证可以找到差异最多为11的所有页面对，即C相似度373，但可能会错过一些较大差异的页面对。

NB：C相似度与汉明距离相同：汉明距离是相应位不同的位置数，而C相似度是相应位相同的位置数。

这也在Gurmeet Singh Manku、Arvind Jain和Anish Das Sarma的论文Detecting Near-Duplicates for Web Crawling中有所解释。

海明距离问题

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

[...] 直觉：考虑一个由 2 的 d 次方个 f 位真随机指纹排序的表格。关注表格中最重要的 d 位。这些 d 位数字的列表相当于“几乎计数器”，因为 (a) 存在相当多的 2 的 d 次方个二进制组合，且 (b) 很少有 d 位组合被复制。另一方面，最不重要的 f − d 位是“几乎随机”的。

现在选择 d，使得 |d − d| 是一个小整数。由于表格是排序的，单次探测就足以识别所有在 d 个最重要的位位置上与 F 匹配的指纹。由于 |d − d| 很小，这样匹配的数量也预计很小。对于每个匹配的指纹，我们可以轻松地确定它们是否与 F 在最多 k 个位位置上不同（这些差异自然限制在最不重要的 f − d 个位位置上）。

上述描述的过程帮助我们找到一个已有的指纹，它与 F 在 k 个位位置上不同，这些位置都在 F 的最不重要的 f − d 个位中。这解决了相当多的情况。为了涵盖所有情况，只需按照下一节的正式概述构建少量附加排序表格即可。

PS：这些优秀的大脑中的大多数都曾在某个层面或某个时间与谷歌有关。