4

n ノードのグラフで各ノード間のハミング距離を計算しようとしています。このグラフの各ノードには同じ長さ (k) のラベルがあり、ラベルに使用されるアルファベットは {0, 1, *} です。「*」はドントケア記号として機能します。たとえば、ラベル 101*01 と 1001*1 の間のハミング距離は 1 です (これらは 3 番目のインデックスでのみ異なると言います)。

私がしなければならないことは、各ノードのハミング距離が 1 のすべての隣接ノードを見つけて、これら 2 つのラベルがどのインデックスで異なるかを正確に報告することです。

次のように、各ノードのラベルを他のすべてのラベルと文字ごとに比較しています。

    // Given two strings s1, s2
    // returns the index of the change if hd(s1,s2)=1, -1 otherwise.

    int count = 0;
    char c1, c2;
    int index = -1;

    for (int i = 0; i < k; i++)
    {
        // do not compute anything for *
        c1 = s1.charAt(i);
        if (c1 == '*')
            continue;

        c2 = s2.charAt(i);
        if (c2 == '*')
            continue;

        if (c1 != c2)
        {
            index = i;
            count++;

            // if hamming distance is greater than 1, immediately stop
            if (count > 1)
            {
                index = -1;
                break;
            }
        }
    }
    return index;

数百万のノードがあるかもしれません。k は通常 50 前後です。私は Java を使用しています。この比較には n*n*k 時間がかかり、動作も遅くなります。試行と VP ツリーを使用することを検討しましたが、この場合にどのデータ構造が機能するかわかりませんでした。Simmetrics ライブラリも調べましたが、何も頭に浮かびませんでした。提案があれば本当に感謝します。

4

3 に答える 3

1

このアプローチを試してください：

キーを 3 進数 (基数 3) に変換します。つまり、0=0、1=1、*=2 10 桁の 3 進数では、16 ビットに収まる 0..59049 の範囲が得られます。

つまり、そのうちの 2 つが 32 ビット ワードを形成します。これら 2 つの 10 桁の 3 進数の単語間の距離を返す 40 億のエントリを含むルックアップ テーブルを作成します。

ルックアップ テーブルを使用して、1 回のルックアップでキーの 10 文字をチェックできるようになりました。5 文字を使用する場合、3^5 は 1 バイトに収まる 243 個の値を与えるため、ルックアップ テーブルは 64 KB しかありません。

シフト操作を使用すると、さまざまなサイズのルックアップ テーブルを作成して、メモリと速度のバランスを取ることができます。

そうすれば、ループを最適化して、より迅速に中止することができます。

最初の相違点の位置を取得するには、2 つのキー部分文字列の最初の相違点のインデックスを含む 2 番目のルックアップ テーブルを使用できます。

何百万ものノードがある場合、同じ部分文字列で始まるノードが多数あることになります。1 つのバケットに同じキーで始まるノードが含まれるバケットにそれらをソートしてみてください。ここでの目標は、バケットをできるだけ小さくすることです (n*n を減らすため)。

于 2015-04-09T16:05:36.657 に答える
0

興味深い問題です。ワイルドカード記号がなければ簡単です。

ワイルドカードがアルファベットの通常の文字である場合、特定の文字列に対して、k 個のハミング距離 1 の文字列をすべて列挙できます。次に、これらの文字列をマルチマップで調べます。たとえば、101 の場合、001、111、および 100 を検索します。

don't care シンボルにより、そのルックアップを実行できなくなります。ただし、各ノードが可能なすべてのキーによって格納されるようにマルチマップが構築されている場合は、そのルックアップを再度実行できます。たとえば、1*1 は 111 および 101 として保存されます。したがって、10* を検索すると、000,010,011,001,111 が検索され、111 によって保存された 1*1 が見つかります。

これの利点は、すべてのラベルを 3 項構造ではなく整数として格納できるため、int[3] をキー値として任意の k < 96 を使用できることです。

パフォーマンスは、マルチマップのバッキング実装に依存します。理想的には、キー サイズが 32 未満の場合はハッシュ実装を使用し、それ以上の場合はツリー実装を使用します。ツリーの実装では、すべてのノードが距離 1 の隣接ノードに接続されO(n*k*log(n))ます。マルチマップ テイクの構築O(n * 2 ^ z)でzは、任意の文字列のワイルドカード文字の最大数を指定します。ワイルドカードの平均数が少ない場合、パフォーマンスの低下は許容範囲内です。

編集:O(n*log(n))ハミング距離 1 の隣接ノードもマルチマップに挿入することで、すべてのノードの検索パフォーマンスを向上させますが、そのサイズが爆発する可能性があります。

注: 昼休みにこれを入力しています。詳細はまだ確認していません。

于 2015-07-10T06:39:37.823 に答える