4

問題

N (~100k-1m) 個の整数/ビット文字列がそれぞれ K (例: 256) ビットの長さであるとします。アルゴリズムは、ペアごとのハミング距離が最小の k ペアを返す必要があります。

例

N = 4
K = 8
i1 = 00010011
i2 = 01010101
i3 = 11000000
i4 = 11000011


HammingDistance(i1,i2) = 3
HammingDistance(i1,i3) = 5
HammingDistance(i1,i4) = 3
HammingDistance(i2,i3) = 4
HammingDistance(i2,i4) = 4
HammingDistance(i3,i4) = 2

k=1 の場合、ペアリスト {(i3,i4)} を返す必要があります。k=3 の場合、{(i1,i2), (i1,i4), (i3,i4)} を返す必要があります。等々。

アルゴリズム

単純な実装では、すべてのペアごとの距離を計算し、ペアを並べ替えて、距離が最小の k を返します: O(N^2)。より良いデータ構造またはアルゴリズムはありますか? 単一のクエリ整数がないため、大きなセットでハミング距離が低いバイナリ文字列を効率的に見つけるのアイデアは使用できないようです。

4

1 に答える 1

6

最近の論文 " The Closest Pair Problem under the Hamming Metric " には、n^2 係数を含むアルゴリズムしかありません (K が非常に大きい場合を除く)。それは、1 つのペアだけを見つける場合でも同じです。したがって、インスタンスの構造についてさらに想定を加えない限り、これを改善するのは難しいようです。たとえば、ハミング距離がそれほど大きくないと仮定すると、いくつかの列をサンプリングし、これらの列が正確に一致するという仮定の下で、これらに従って文字列をバケットにハッシュし、各バケットで個別にペアワイズ比較を行うことができます。いくつかのペアを見逃す可能性を最小限に抑えるために、ランダムな列の別のセットに対してこれを繰り返します。

于 2011-08-17T07:07:05.510 に答える