我有 N < 2^n 随机生成的 n 位数字存储在一个文件中，其查找成本很高。给定一个数字 Y，我必须在文件中搜索一个最多为 k hamming dist 的数字。来自 Y。现在这需要 C(n 1) + C(n 2) + C(n 3)...+C(n,k) 最坏情况查找，这在我的情况下是不可行的。我尝试在内存中的每个位位置存储 1 和 0 的分布，并优先考虑我的查找。因此，我存储了位 i 为 0/1 的概率：
Pr(bi=0), Pr(bi=1) 用于从 0 到 n-1 的所有 i。
但这并没有太大帮助，因为 N 太大并且在每个位位置几乎相等的 1/0 分布。有没有办法可以更有效地完成这件事。现在，您可以假设 n=32，N = 2^24。
谷歌在这篇论文中针对k=3, n=64, N=2^34（更大的语料库，更少的位翻转，更大的指纹）给出了这个问题的解决方案。基本思想是，对于小的 k，n/k 相当大，因此如果您形成几个具有置换位顺序的表，您希望附近的指纹应该具有相对较长的公共前缀。但是，我不确定它是否适合您，因为您的 n/k 小得多。
您可以使用量子计算来加快搜索过程，同时最大限度地减少所需的步骤数。我认为 Grover 的搜索算法将对您有所帮助，因为它为搜索问题提供了二次加速.....
如果通过“查找”，您的意思是在整个文件中搜索指定的数字，然后为每个可能的匹配项重复“查找”，那么只需读取整个文件一次，检查每个条目的汉明距离应该会更快到指定的号码。这样，您只需读取一次文件，而不是 C(n 1) + C(n 2) + C(n 3)...+C(n,k) 次。
如果您的应用程序有能力进行一些广泛的预处理，您可以在生成 n 位数字时计算与该数字最多 k 距离的所有其他数字并将其存储在查找表中。它类似于地图 >。riri 声称您可以将其放入内存中，因此哈希表可能工作得很好，但除此之外，您可能需要一个 B+ 树用于 Map。当然，正如您之前提到的那样，这很昂贵，但是如果您可以事先做到这一点，那么以后您将可以进行快速查找，无论是 O(1) 还是 O(log(N) + log(2^k))。
也许您可以将其存储为图形，并通过汉明距离将其链接到集合中下一个最接近的数字，然后您需要做的就是按照指向另一个数字的链接之一找到下一个最接近的数字。然后使用索引通过文件偏移量来跟踪数字的位置，因此当您需要查找附近的邻居时，您不必在图表中搜索 Y。
你还说你有 2^24 个数字，根据 wolfram alpha (http://www.wolframalpha.com/input/?i=2^24+*+32+bits) 只有 64MB。你能把它全部放在内存中以加快访问速度吗？也许这会在您的机器上缓存自动发生？