我正在致力于设计索引策略来查找相似的哈希值。哈希值是为图像生成的。即
String A = "00007c3fff1f3b06738f390079c627c3ffe3fb11f0007c00fff07ff03f003000" //Image 1
String B = "6000fc3efb1f1b06638f1b0071c667c7fff3e738d0007c00fff03ff03f803000" //Image 2
这两个哈希值相似(基于汉明距离和编辑距离)，因此图像也相似。我有超过 1.9 亿个这样的哈希值。我必须选择一个合适的索引数据结构，其中查找相似哈希的最坏情况复杂度不是 O(n)。哈希数据结构不起作用，因为它会搜索 <、= 和 >(或者会吗？)。我可以找到汉明距离或其他距离来计算相似度，但在最坏的情况下我最终会计算它 1.9 亿次。
这是我现在的策略:
目前我正在研究 BTree，我将根据编号对节点中的所有键进行排名。连续相同的字符并遍历排名最高的键，如果子键的排名小于父节点中其他键的排名，我将开始遍历父节点中的该键。如果父级的所有等级都相同，我将进行正常的 BTree 遍历(givenkey < nodeKey --> 使用 ASCII 比较转到 nodeKey.. 的子节点)，这就是我的问题所在。
因为这会导致搜索中出现大量漏报。在最坏的情况下，我将仅遍历树的一部分，在其他遍历中可以找到可能相似的键。否则我必须搜索整个树，这又是 O(n)，我可能还没有树。
我觉得必须有更好的方法，现在我陷入困境，很高兴听到有关解决问题的任何意见。请分享您的想法。
P.S:我无法使用任何外部数据库。
最佳答案
首先，这是一个非常困难的问题。不要期待干净利落的答案。
我见过的一个近似数据结构是 Spatial Approximation Sample Hierarchy (SASH) 。
A SASH (Spatial Approximation Sample Hierarchy) is a general-purpose data structure for efficiently computing approximate answers for similarity queries. Similarity queries naturally arise in a number of important computing contexts, in particular content-based retrieval on multimedia databases, and nearest-neighbor methods for clustering and classification.
SASH 仅使用距离函数来构建数据结构，因此距离函数(在您的情况下，还包括图像哈希函数)需要“良好”。基本直觉大致是，如果 A ~ B(图像 A 与图像 B 接近)且 B ~ C，则通常是 A ~ C。数据结构会在相对接近的项目之间创建链接，您只需查看即可修剪搜索对于更接近您的查询的事情。该策略是否真正有效取决于数据的性质和距离函数。
自从我查看 SASH 以来已经有 10 年左右的时间了，所以可能也有更新的发展。 Michael Houle's page似乎表明他对名为 Rank Cover Trees 的东西有更新的研究，其目的似乎与 SASH 类似。这至少应该让你开始该领域的研究；阅读一些论文并遵循引用线索。
关于image - 查找相似字符串的索引策略，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38555154/