查找最接近的漢明距離

我有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

查找最接近的漢明距離

回答

相關問題