3

文字列を受け取り、0 から 1 までの数値を返す関数を作成したいと考えています。関数は、同じ文字列が与えられたときに一貫して同じ数値を返す必要がありますが、それ以外の結果には識別可能なパターンがあってはなりません。入力文字列の大規模なセットの出力数値は、均一な分布に従う必要があります。

さらに、そのような関数を複数生成する必要があります。つまり、文字列「abc」を指定すると、関数 A は一貫して 0.593927 を返し、関数 B は一貫して 0.0162524 を返す可能性があります。私はそれが高速である必要があり（数値シミュレーション用です）、適度に優れた統計が必要です。

私は Python を使用しており、「Python ライブラリを使用して簡単に実行する方法は次のとおりです」または「実装できるアルゴリズムは次のとおりです」という形式の回答で解決します。Python ですばやく実行する方法がない場合は、代わりに C に切り替えます。

次の 2 つの方法のどちらでも機能することはわかっていますが、それぞれに欠点があるため、より洗練されたソリューションを探したいと思います。

  1. 辞書
    を保存する 新しい文字列が与えられるたびに新しい乱数を計算し、それを辞書に保存して、同じ文字列を再度受け取ったときに取得できるようにします。ただし、私のアプリケーションは、1 回しか表示されない文字列を大量に生成する可能性が高く、最終的には非常に大きな辞書をメモリに格納する必要があります。また、同じシードを使用しても、同じ文字列を異なる順序で受け取ると、異なる関数を生成するため、再現性がより難しくなります。これらの理由から、「その場で」乱数を一貫して計算する方がはるかに優れています。

  2. ハッシュ関数を使用
    して、文字列に対してハッシュ関数を呼び出すだけで、結果を数値に変換できます。複数の関数を生成する問題は、たとえば、すべての入力文字列に「シード」文字列を追加することで解決できます。でも、その後、適切な速度と統計を持つハッシュ関数を見つけようとすることに固執しています。Python のビルトイン ハッシュは高速ですが、実装に依存します。また、この種の目的のために設計されていないため、統計がどれほど優れているかはわかりません。一方で、md5 などの安全なハッシュ アルゴリズムを使用することもできますが、これは優れた統計情報を提供しますが、これは私のアプリケーションには遅すぎます。通常、データ ストレージ アプリケーション向けのハッシュ関数は、md5 などの暗号的に安全な関数よりもはるかに高速ですが、均一に分散された出力を生成するのではなく、衝突を回避することを目的として設計されており、これらはすべての場合で必ずしも同じではありません。

ハッシュ関数に関する追加の注意事項

衝突を回避することと均一な結果を生成することは別物であることを説明するために、Python の組み込みハッシュ関数を使用した次の例を検討してください。

>>> hash("aaa") % 1000
340
>>> hash("aab") % 1000
343
>>> hash("aac") % 1000
342
>>> hash("aad") % 1000
337
>>> hash("aae") % 1000
336
>>> hash("aaf") % 1000
339
>>> hash("aag") % 1000
338
>>> hash("aah") % 1000
349
>>> hash("aai") % 1000
348
>>> hash("aaj") % 1000
351
>>> hash("aak") % 1000
350

上記の出力には衝突はありませんが、それらはすべて 336 から 351 の間にあり、3 桁目に明確なパターンがあるため、明らかに均一に分布していません。そうすれば、おそらくより良い統計を取得できると(hash("aaa")/HASH_MAX)*1000思いますが（どうあるべきかを理解できると仮定してHASH_MAX）、これは、優れたハッシュ関数の要件が探している関数の要件と同じではないことを示すのに役立つはずです.

問題に関するいくつかの関連情報

文字列はシミュレーションによって生成されるため、このアルゴリズムが機能する必要がある文字列が何であるかは正確にはわかりませんが、次のような場合が考えられます。

  1. それらの文字セットは非常に制限されています (おそらく 4 つまたは 5 つの異なる記号のみ)。

  2. さまざまな長さの、多くのユニークまたは珍しい文字列といくつかの非常に一般的な文字列があります。

  3. 文字列の長さに上限はありませんが、短いものは長いものよりもはるかに一般的です。100 文字を超えるものを見たことがなくても驚かないでしょうが、確かなことはわかりません。それらの多くは 1 ～ 3 文字しかないため、アルゴリズムが短い文字列に対して高速であることが重要です。（しかし、特定の長さ未満の文字列にはルックアップテーブルを使用できると思います。）

  4. 通常、文字列には共通の大きな部分文字列があります。多くの場合、2 つの文字列の違いは、最初または最後に追加された 1 文字だけです。文字列が類似している場合、アルゴリズムが類似した出力値を与える傾向がないことが重要です。

4

4 に答える 4

3

適切な乱数ジェネレーターを使用して、文字列をシードします。

于 2013-02-05T14:09:20.687 に答える
1

Rabin フィンガープリンティングなどのフィンガープリントを使用してみてください。
http://en.wikipedia.org/wiki/Fingerprint_(コンピューティング) .

N ビットの指紋を選択した場合は、結果を 2^N で割るだけです。

指紋は一種のハッシュ関数であり、通常はコンピューターにとって非常に高速ですが ( MD5 などの暗号化ハッシュ関数と比較して)、暗号化アプリケーションには適していません (鍵の値は指紋を使用して何らかの方法で回復できる場合があります)。

于 2013-02-05T07:05:35.987 に答える
1

ウィキペディアのユニバーサルハッシュに関する記事の「文字列のハッシュ」に関するセクションにアルゴリズムがあります。

または、組み込みのハッシュ関数を使用することもできます。各ランダム関数は、ハッシュする前に、ランダムな (ただし固定の) プレフィックスを文字列に付加します。

于 2013-02-05T06:45:54.503 に答える
1

Lookup3は非常に優れた衝突特性を持つと評判で、結果が均一に分散されることを意味し、高速でもあります。これを Python 拡張機能に入れるのは簡単なはずです。

より一般的には、ハッシュ テーブルの競合を最小限に抑え、必要な速度特性を備えた関数を見つけた場合、32 ビットまたは 64 ビットの整数から float への最終的な変換だけで十分です。Web やその他の場所には、文字列ハッシュ関数のソースが多数あります。まず、 Knuthを確認してください。

添加

試してみる価値のあるもう 1 つの方法は、最初に RC4 のような高速な 1-1 アルゴリズム (安全ではありませんが、疑似乱数に十分近い) を使用して文字列を暗号化し、次に自明なハッシュ (h = h + a * c[i ] + b) 暗号文の上。RC4 キーは一意化子です。

于 2013-02-05T06:46:23.263 に答える