9

これらの2つの文字列シーケンスがあるとしましょう

abc cba bc

bc abc cba

上記の 2 つのシーケンスが同じバケットにマップされるように、そのようなシーケンス (シーケンスも文字列) のマッピングを作成しようとしています。

私の最初の考えは、各文字列に個別に適用されるハッシュ関数の結果を追加することです。このように、それらの順序は重要ではありません。シーケンス文字列全体にハッシュ関数を適用すると、もちろんハッシュ結果は異なります。

ただし、私は文字列ハッシュ関数の世界に非常に慣れていないため、このアプローチが効率的かどうかはわかりません。

このウェブサイトhttp://www.partow.net/programming/hashfunctions/index.html

文字列ハッシュのさまざまな実装を見つけましたが、どれが私のニーズに「最適」かはわかりません。

シーケンス内の各文字列に関する技術的な詳細は、それぞれが 25 文字を超えないことです。また、各シーケンスには 3 つを超える文字列はありません。

質問

1.文字列ハッシュ関数の結果をシーケンスの各文字列に追加するこのアプローチは機能しますか?

2.はいの場合、どの文字列ハッシュ関数を使用すれば、衝突が少なく、時間効率が高くなりますか?

前もって感謝します

4

3 に答える 3

0

各要素を個別にハッシュします。

次に、それらのハッシュを並べ替えます。ソート 3size_tは高速です。

次に、それらのハッシュをチェーンします。ライブラリにハッシュ チェーン関数が含まれている場合やhash( a+b+c )、オーバーフロー ラップを使用している場合もあります。

xor 2 つの同一のハッシュ値はゼロであるため、xor は避けてください。そして、同一の文字列のハッシュは同一です。そのため、素朴な xor が同じハッシュ出力につながる可能性が( a,a,b )あり、これは最悪です。( c,c,b )

于 2013-04-01T12:15:37.020 に答える
0

どのハッシュ関数を選択しても、次のような個々のハッシュの最終的な組み合わせの演算子が必要です。

  • 交換可能な
  • 連想

整数値の候補として、合計、積、および排他的 or が思い浮かびます。はい、追加するとうまくいきます。ただし、解決する必要がある無関係なシーケンスにはまだ衝突があるため、文字列比較関数が必要になりますが、同じ文字列セットの順列は同じバケットになります。

操作の順序を逆にすることもできます。最初に文字列を文字単位で追加します (たとえば、"ab" と "cba" を追加すると、('a' + 'c')('b' + 'b')('\0 ' + 'a') を sum または product のキャリー伝搬を使用するため、ここではおそらく xor が興味深い候補です)、次にハッシュ関数を適用します。これらの 2 つの操作を実行中に組み合わせることもできます (疑似コードは次のとおりです)。

int hash(string a, string b, string c){
    int r = 0, k;
    int m = max(a.length(), max(b.length(), c.length()));
    for (int i = 0; i < m; i++) {
        k = ( i < a.length()? a[i] : 0) ^
              (i < b.length()? b[i] : 0) ^
              (i < c.length()? c[i] : 0);
        r = hash(r,k);
    }
    return r;
}

hashインクリメンタルハッシュ機能付き。通常の目的では、十分に大きい (つまり、バケット配列の予想サイズよりも大きい) 素数に対する単純なモジュロで問題ありません。

完全に異なる (そしてより良い?) 解決策は、単純にシーケンスを並べ替え (3 つのエントリは準定数時間を意味します)、文字列を 3 桁の数字の「桁」と見なして比較関数を使用して順序付きマップを作成することです。しかし、これは問題の範囲外です。

于 2013-04-01T11:02:57.330 に答える