6

各文字列が

  • 正確に4文字の長さと
  • リスト内で一意。

これらの文字列のそれぞれについて、文字列を一意にする文字列内の文字の位置を特定したいと思います。

したがって、3つの文字列のリストについては

abcd
abcc
bbcb

最初の文字列については、 dが他の文字列の4番目の位置に表示されないため、4番目の位置dにある文字を識別します。

2番目の文字列では、4番目の位置cにある文字を識別します。

3番目の文字列については、1番目の位置bにある文字と、4番目の位置にある文字bも識別します。

これは簡潔に次のように表すことができます

abcd -> ...d
abcc -> ...c
bbcb -> b..b

同じ問題を検討しているが、2進数のリストがある場合

0101
0011
1111

次に、私が望む結果は

0101 -> ..0.
0011 -> .0..
1111 -> 1...

2進数のテーマにとどまり、XORを使用して、2つの2進数内でどのビットが一意であるかを識別できます。

0101 ^ 0011 = 0110

これは、この場合、2番目と3番目のビット（左から右に読み取る）がこれら2つの2進数の間で一意であることを意味すると解釈できます。どういうわけかそれをより大きなリストに拡張することができない限り、このテクニックは赤いニシンかもしれません。

ブルートフォースアプローチは、各文字列を順番に調べ、各文字列について、リスト内の残りの文字列の垂直スライスを反復処理することです。

だからリストのために

abcd
abcc
bbcb

私はから始めます

abcd

の垂直スライスを反復処理します

abcc
bbcb

これらの垂直スライスはどこにありますか

a | b | c | c
b | b | c | b

またはリスト形式で、「ab」、「bb」、「cc」、「cb」。

これにより、4つの比較が行われます。

a : ab -> . (a is not unique)
b : bb -> . (b is not unique)
c : cc -> . (c is not unique)
d : cb -> d (d is unique)

または簡潔に

abcd -> ...d

希望に満ちた考えかもしれませんが、任意の数の文字列（または2進数）のリストに適用できる、エレガントで一般的な解決策があるはずだと感じています。しかし、もしあれば、私はまだそれを見ることができませんでした。

このアルゴリズムを使用して、一意の画像（ビットマップ）のコレクションから最小限の署名を導き出し、将来それらの画像を効率的に識別できるようにしたいと考えています。将来の効率が問題にならない場合は、各画像の単純なハッシュを使用します。

ブルートフォースを改善できますか？

編集 私が温めているアプローチは、ピクセルから画像へのマップを作成することです

sprawl[Tuple<x=10, y=33,color=f1fefd>] => {
     image17,
     image23,
     ...
}

sprawl[Tuple<x=10, y=34,color=f1fef0>] => {
     image11
     ...
}

次に、そのマップを使用して、各画像の署名ピクセルの最小セットを識別します。

ピクセル（x、y、色で識別される）が1つの画像のみを参照している場合、その画像の完全な（最小限の）署名を見つけました。

画像に一意のピクセルがない場合はさらに複雑になりますが、リスト内ですべての画像が一意であることがわかっているため、2つ以上のピクセル参照（ただし可能な限り少ない）を組み合わせて画像を推定できるはずです。

アップデート

私はこのためのアルゴリズムに取り組んできました。私の問題はこれと非常によく似ており、その質問に対する答えとしてアルゴリズムを作成しました。このアップデートは、まだフォローしている人の注意を喚起するためのものです（5つのブックマークが表示されます）。私はこれに単独で取り組んでいるので、自分自身を明確にしていないことを観察するだけでも、あらゆるフィードバックを歓迎します！

4

3 に答える 3

9

各文字が各位置（0〜3）に出現する回数を含む2次元配列を生成できます。たとえば、数字/文字が最後の位置に表示されるarr[1,3]回数が含まれます。1

次に、文字列ごとsに、文字列内のすべての文字を調べます。配列に従ってその位置に1回だけ表示されるのは、その文字列の一意の文字です。つまり、arr[s[i], i]==1Then文字列sの位置が一意である場合i。

これにより、線形時間で解が得られますが、与えたアルゴリズムでは2次時間がかかります。

于 2010-05-18T17:57:42.830 に答える
1

後で画像を識別することが目標である場合は、IDピクセルとして機能する事前定義されたポイントを選択することにより、画像の非常に高速なハッシュを作成できます。

たとえば、次のような構造体（class、struct、どの言語でもかまいません）を持つことができます。

structure ImageHash {
    int x_pixels, y_pixels;
    u_long hash;
    void createHash(Image img) {
        x_pixels = img.x_pixels;
        y_pixels = img.y_pixels;
        for(int i = 1; i < 5; i++) {
            int x = x_pixels / i;
            for(int j = 1; j < 5; j++) {
                int y = y_pixels / j;
                int r = img.getPixelRed(x,y);
                int g = img.getPixelGreen(x,y);
                int b = img.getPixelBlue(x,y);
                hash = (hash * 31) ^ (r^g^b);
            }
        }
    }
}

この種の「不完全なハッシュ」を使用すると、考えられるIDを識別でき、必要に応じて、費用のかかる完全な比較を控えめに行うことができます。

必要に応じて、不完全なハッシュを展開します。

于 2010-05-18T18:03:30.910 に答える
0

この問題は、トライまたはプレフィックスツリーによって解決できます。

Trie-Wikipedia、無料の百科事典を参照してください

例の3つの文字列の場合：

abcd
abcc
bbcb

トライツリーに変換されます（^はツリーのルートを示します）：

^--a-b-c-d
 \      \
  \      c
   \
    b-b-c-b

分岐するノードへのパスは、一般的なプレフィックスです。最後の分岐点の後のノードは、特定の文字列を一意にするものです。この場合、それらはd、c、bです。

文字列の順序は重要ではないと思います。つまり、隣接する文字列だけでなく、すべての文字列を比較して一意性を見つけます。

複雑さはO（nxm）である必要があります。ただし、これはおそらく文字列内の文字のドメインの影響を受けます。

于 2010-05-18T19:37:32.993 に答える