string - 将 400 万行数据相互匹配并按相似性对结果进行排序的最佳方法？

Question

我们使用 libpuzzle ( http://www.pureftpd.org/project/libpuzzle/doc ) 比较 400 万张图片的相似度。

效果很好。

但不是使用 libpuzzle 函数进行图像与图像比较，还有另一种比较图像的方法。

这里是一些快速背景:

Libpuzzle 为任何给定图像创建一个相当小的(544 字节)散列。该散列又可用于使用 libpuzzles 函数与其他散列进行比较。有一些 API...PHP、C 等...我们正在使用 PHP API。

另一种比较图像的方法是从给定的哈希创建向量，这里是来自文档的粘贴:

Cut the vector in fixed-length words. For instance, let's consider the following vector:

[ a b c d e f g h i j k l m n o p q r s t u v w x y z ]

With a word length (K) of 10, you can get the following words:

[ a b c d e f g h i j ] found at position 0 [ b c d e f g h i j k ] found at position 1 [ c d e f g h i j k l ] found at position 2 etc. until position N-1

Then, index your vector with a compound index of (word + position).

Even with millions of images, K = 10 and N = 100 should be enough to have very little entries sharing the same index.

因此，我们可以使用矢量方法。它实际上比图像与图像比较效果更好，因为当我们进行图像与图像比较时，我们使用其他数据来减少样本量。我们使用哪些其他数据来减少样本量有点无关紧要并且特定于应用程序，但是使用向量方法......我们不必这样做，我们可以对 400 万个哈希中的每一个进行真实测试.

我们遇到的问题如下:

有了 400 万张图片，每张图片有 100 个向量，这就变成了 4 亿行。我们发现 MySQL 在处理大约 60000 张图像(60000 x 100 = 600 万行)后往往会阻塞。

我们使用的查询如下:

SELECT isw.itemid, COUNT(isw.word) as strength
FROM vectors isw
JOIN vectors isw_search ON isw.word = isw_search.word
WHERE isw_search.itemid = {ITEM ID TO COMPARE AGAINST ALL OTHER ENTRIES}
GROUP BY isw.itemid;

如前所述，即使有适当的索引，当涉及到 4 亿行时，上述速度也相当慢。

那么，有人可以建议任何其他技术/算法来测试它们的相似性吗？

我们愿意尝试任何事情。

一些值得一提的事情:

1. 哈希是二进制的。
2. 散列的长度始终相同，均为 544 字节。

我们能想出的最好办法是:

1. 将图像哈希从二进制转换为 ascii。
2. 创建向量。
3. 创建如下字符串:VECTOR1 VECTOR2 VECTOR3 etc etc.
4. 使用 sphinx 搜索。

我们还没有尝试过上面的方法，但是这可能会比执行 mysql 查询产生更好的结果。

有什么想法吗？如前所述，我们愿意安装任何新服务(postgresql？hadoop？)。

最后请注意，可以在问题 Libpuzzle Indexing millions of pictures? 中找到有关此向量 + 比较方法的确切工作原理的概述。 .我们本质上是在使用 Jason 提供的确切方法(目前是最后一个答案，获得 200+ so 分)。

Answer 1

不要在数据库中执行此操作，只需使用一个简单的文件即可。下面我展示了一个文件，其中包含来自两个向量 [abcdefghijklmnopqrst](图片 1)和 [xxcdefghijklxxxxxxxx](图片 2)

的一些单词

 <index>       <image>
0abcdefghij      1
1bcdefghijk      1
2cdefghijkl      1
3defghijklm      1
4efghijklmn      1
...
...
0xxcdefghij      2
1xcdefghijk      2
2cdefghijkl      2
3defghijklx      2
4efghijklxx      2
...

现在对文件进行排序:

  <index>       <image>
0abcdefghij      1
0xxcdefghij      2
1bcdefghijk      1
1xcdefghijk      2
2cdefghijkl      1       
2cdefghijkl      2       <= the index is repeated, those we have a match
3defghijklm      1
3defghijklx      2
4efghijklmn      1
4efghijklxx      2

当文件被排序后，很容易找到具有相同索引的记录。编写一个可以遍历排序列表并找到重复项的小程序或其他东西。