7

これは、私が C++ で書いている diff ユーティリティ用です。

n 個の文字セット {"a"、"abc"、"abcde"、"bcd"、"de"}のリストがあります ( k = 5 種類の文字のアルファベットから取得)。文字セット {"a"、"bc"、"d"、"e"} の論理和によってリスト全体を構築できることを確認する方法が必要です。つまり、「b」と「c」は線形従属であり、文字の 1 つおきのペアは独立しています。

ビットいじりバージョンでは、上記の文字セットは {10000, 11100, 11111, 01110, 00011} として表されます。小さいセット {10000 、01100、00010、00001}。

言い換えれば、 {0,1} kのn 個の異なるビットベクトルのセットの「離散基底」を探していると思います。この論文では、一般的な問題は NP 完全であると主張していますが、幸いなことに、私は小さなケース ( k < 32)の解決策しか探していません。

基底を生成するための本当にばかげたアルゴリズムを思いつくことができます。例: k 2個の文字ペアのそれぞれについて、それらが依存していることを (O( n ) 検索によって) 実証してみてください。しかし、まだ見つけていない効率的なビット操作アルゴリズムがあるように感じます。誰もそれを知っていますか？

編集:結局のところ、この問題の解決策は本当に必要ありませんでした。しかし、簡単なビットいじりの解決策があるかどうかはまだ知りたいです。

4

4 に答える 4

2

私は、union findが頭の上にあるように、ばらばらの集合データ構造を考えています (ノードを結合するのではなく、それらを分割します)。

アルゴリズム：

mainすべての位置を同じグループに割り当てる配列を作成してから、次のようにします。

for each bitstring curr
  for each position i
    if (curr[i] == 1)
      // max of main can be stored for constant time access
      main[i] += max of main from previous iteration

次に、すべての個別の数値mainが異なるセットになります (実際のユニオン検索アルゴリズムを使用する可能性があります)。

例：

だから、main = 22222。1(ビット文字列を使用するため、混乱を避けるためにグループとしては使用しませんcurr)。

curr = 10000
main = 42222 // first bit (=2) += max (=2)

curr = 11100
main = 86622 // first 3 bits (=422) += max (=4)

curr = 11111
main = 16-14-14-10-10

curr = 01110
main = 16-30-30-26-10

curr = 00011
main = 16-30-30-56-40

次に、個別の番号で分割します。

{10000, 01100, 00010, 00001}

改善：

増加する速度を下げるために、main置き換えることができます

main[i] += max of main from previous iteration

と

main[i] += 1 + (max - min) of main from previous iteration

編集: j_random_hacker のコメントに基づいて編集

于 2013-01-06T13:49:27.340 に答える
1

スペースを犠牲にして愚かなアルゴリズムのパスを組み合わせることができます。

と呼ばれるビット長のビット ベクトルをviolations作成し(k - 1) k / 2ます (したがって、. の場合は 496 k = 32)。文字セットを 1 回パスします。それぞれ、および文字の各ペアについて、違反を探します (つまりXOR、これらの文字のビットOR、結果は の対応する位置になりviolationsます。) 完了したら、否定して残りを読み取ります。

于 2012-07-18T03:25:05.293 に答える
0

誰かがそれを NP 完全として示したので、大きな語彙の場合、可能性のセット全体 O((2 k -1) * n)の総当たり検索 (さまざまな剪定が可能) よりもうまくいくとは思えません。少なくとも最悪のシナリオでは、リンクした論文で概説されているように、おそらくいくつかのヒューリスティックが多くの場合に役立ちます。これは、長さ 2 の基底だけでなく、考えられるすべての基底文字列に一般化された「愚かな」アプローチです。

ただし、小さな語彙の場合、次のようなアプローチの方がはるかに優れていると思います。

  1. あなたの言葉はバラバラですか？もしそうなら、あなたは終わりです（「abc」や「def」のような独立した単語の単純なケース）

  2. 可能な単語のペアごとにビットごとに実行します。これにより、候補ベース文字列の初期セットが得られます。

  3. ステップ1に進みますが、元の単語を使用する代わりに、現在の基底候補文字列を使用します

その後、最終的に受け入れられた候補のサブセットではない個々の手紙も含める必要があります. たぶん、未使用の文字のようなもののための他のマイナーな簿記 (ビット単位またはすべての可能な単語のようなものを使用)。

あなたの簡単な例を考えてみましょう：

最初のパスでは、a、abc、bc、bcd、de、d が得られます

2 番目のパスでは、a、bc、d が得られます

簿記はあなたにa、bc、d、eを与える

これが正しいという証拠はありませんが、直感的には少なくとも正しい方向にあると思います。利点は、可能性のある候補を使用する力ずくのアプローチの代わりに単語を使用することにあります。単語のセットが十分に大きい場合、このアプローチはひどいものになりますが、ボキャブラリーが数百または数千にまで及ぶ場合は、かなり迅速になるに違いありません。素晴らしい点は、k の値が大きい場合でも機能することです。

答えが気に入って報奨金があれば、喜んで 20 行のコードで解決してみます :) そして、より説得力のある証拠を考え出します。私には非常に実行可能に思えます。

于 2012-11-26T18:57:32.727 に答える
0

主成分分析を試してみてください。バイナリデータまたはより一般的にはカテゴリデータ用に設計された PCA にはいくつかの種類があります。

于 2012-08-30T20:05:25.093 に答える