java - ランダムに並べられた入力の変化を検出する (ハッシュ関数?)

Question

任意の順序で入力できるテキスト行を読んでいます。問題は、出力が実際には前の出力と同じになる可能性があることです。最初に出力をソートせずに、どうすればこれを検出できますか?

同一の入力を任意の順序で取り、それでも同じ結果を生成できるある種のハッシュ関数はありますか?

score 3 · Accepted Answer

最も簡単な方法は、途中で各行をハッシュし、ハッシュと元のデータを保存してから、新しいハッシュを既存のハッシュのコレクションと比較することです。陽性の場合は、実際のデータを比較して、誤検知ではないことを確認できます。これは非常にまれですが、MD5 や CRC などのより高速なハッシュアルゴリズムを使用できます (SHA などの代わりに)。は遅くなりますが、衝突する可能性は低くなります)、ただ速いので、ヒットしたときに実際のデータを比較します。

score 0 · Accepted Answer

問題の仕様は少し限られています。

私が理解しているように、順序に関係なく、複数の文字列に同じ要素が含まれているかどうかを確認したいと考えています。

例えば：

A B C
C B A

同じだ。

これを行う方法は、値のセットを作成してからセットを比較することです。セットを作成するには、次のようにします。

HashSet set = new HashSet();
foreach (item : string) {
   set.add(item);
}

次に、セットの1つを実行し、それを他のセットと比較して、セットの内容を比較します。実行時間は、ソートの例のO(N)代わりになります。O(NlogN)

score 0 · Accepted Answer

したがって、次のような入力があります

A B C D
D E F G
C B A D

1 行目と 3 行目が同一であることを検出する必要がありますか?

score 0 · Accepted Answer

2 つのファイルに同じ行のセットが含まれているが、順序が異なるかどうかを調べたい場合は、各行に通常のハッシュ関数を個別に使用してから、順序が問題にならない関数 (加算など) と組み合わせることができます。

score 0 · Accepted Answer

行がかなり長い場合は、各行のハッシュのリストを保持し、それらを並べ替えて以前の出力と比較することができます。

100% 絶対確実なソリューションが必要ない場合は、各行のハッシュをブルームフィルターに格納し (ウィキペディアで調べてください)、処理の最後にブルームフィルターを比較できます。これにより、誤検知が発生する可能性があります (つまり、出力が同じであると考えているが、実際には同じではない) が、ブルームフィルターのサイズを調整することでエラー率を微調整できます...

score 0 · Accepted Answer

各文字の ASCII 値を合計すると、順序に関係なく同じ結果が得られます。

(これは少し単純化しすぎているかもしれませんが、ひょっとしたらあなたにアイデアをひらめかせるかもしれません。興味深いバックストーリーについては、真珠のプログラミング、セクション 2.8 を参照してください。)

score 0 · Accepted Answer

複数の文字列が同じハッシュを生成する可能性があるため、ハッシュベースの方法はいずれも悪い結果をもたらす可能性があります。(可能性は低いですが、可能です。)これは、ハッシュ値の特に悪いハッシュを本質的に取得することになるため、ハッシュを追加するという提案に特に当てはまります。

ハッシュメソッドは、変更を見逃したり、存在しない変更を見つけたりすることが重要でない場合にのみ試行する必要があります。

最も正確な方法は、線の文字列をキーとして使用し、それぞれのカウントを値として格納する Map を保持することです。(各文字列が 1 回しか表示されない場合、カウントは必要ありません。) 予想される行セットについてこれを計算します。このコレクションを複製して着信行を調べ、表示される各行の数を減らします。

カウントがゼロの行 (またはマップエントリがまったくない行) に遭遇した場合は、予期しない行を見たことになります。
マップにゼロ以外のエントリが残っている状態でこれを終了すると、期待したものは表示されません。

java - ランダムに並べられた入力の変化を検出する (ハッシュ関数?)

7 に答える 7

Related

Reference