查找最接近的汉明距离

我有N个< 2^N随机生成的n位存储在一个文件中查找用于这是昂贵的数字。给定一个数字Y，我必须在最多khamming 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) for all i from 0 to n-1.

但它并没有太大的帮助，因为N是太大，在每一个比特位的1/0大致相当。有没有办法可以更有效地完成这件事。现在，你可以假设n = 32，N = 2^24。

来源

2011-02-15 user352951

......作业？ – zengr 2011-02-15 00:56:17

不，我希望你对你的评论更有用。 – user352951 2011-02-15 02:23:10

是啊，也许这是一个更有用的注释：你在计算器8个月前注册，问6个问题，只接受2回答，只投一次，从来没有回答的问题。也许你应该阅读常见问题。 – 2011-02-15 03:23:59

也许你可以将它作为一个图形存储起来，并且链接到集合中下一个最接近的数字，通过海明距离，然后你需要做的就是沿着其中一个链接到另一个数字找到下一个最接近的数字。然后使用索引通过文件偏移来跟踪数字的位置，因此当您需要查找附近的邻居时，您不必在图表中搜索Y.

你也会说你有2^24的数字，它根据wolfram alpha（http://www.wolframalpha.com/input/?i=2,24+++32+bits）只有64MB。你能不能把所有内容都放在内存中以使访问速度更快？也许这会在你的机器上缓存时自动发生？

来源

2011-02-15 01:12:37 riri

如果您的应用程序可以承担一些大量的预处理工作，那么您可以在生成n位数字时计算与该数字最多相距k的所有其他数字，并将其存储在查找表中。它会像一个地图>。 riri声称你可以将它放在内存中，所以哈希表可能工作得很好，但否则，你可能需要一个B +树作为Map。当然，如前所述，这很昂贵，但是如果您事先可以做到这一点，那么稍后您可以快速查找O（1）或O（log（N）+ log（2^k））。

来源

2011-02-15 01:28:12 muddybruin

如果通过“查找”，你的意思是搜索整个文件中指定的号码，然后重复“查找”为每一个可能的匹配，那么它应该是更快的，只是在整个文件中读取一次，检查每个条目当你离开汉明距离到指定的数字。这样，您只能读取一次文件而不是C（n 1）+ C（n 2）+ C（n 3）... + C（n，k）次。

来源

2011-02-15 01:36:24 Adukra

可以使用量子计算为加快你的搜索过程，并同时减少所需的步数。我认为，Grover的搜索算法将有助于全给你，因为它提供的二次加速的搜索问题.....

来源

2011-06-13 08:50:01 Tisu

谷歌给出了一个解决这个问题对于k = 3，N = 64，N = 2 ^在this paper中有34个（更大的语料库，更少的位翻转，更大的指纹）。基本思想是，对于小的k，n/k非常大，因此如果用排列的位顺序形成几个表格，则预计附近的指纹应该有相对较长的通用前缀。我不确定它会对你有用，但是，因为你的n/k比较小。作业？

来源

2011-06-14 02:29:48

查找最接近的汉明距离

回答

相关问题