この大きな文字列のすべての部分文字列が同じ番号にハッシュされるが、非部分文字列は高い確率でこの大きな文字列にハッシュされない、何らかの方法で大きな文字列をいくつかの数値に要約する疑似ハッシュメカニズムはありますか?
いいえ。
fそのようなハッシュにしましょう。stringsと non-substring を検討してくださいt。sとtは の部分文字列であることに注意してくださいs + t。したがって、sとtは同じハッシュ (つまりf(s) = f(t) = f(s + t)) を持ちます。f(s) != f(t)これは、高い確率でという要件に反します。
特に、 の場合、すべての文字列がであることがs = ""わかります。つまり、は定数であり、 に等しくなります。tf(s) = f(t)ff("")
部分文字列の長さが一定であれば、多くのファイル共有プログラムと同じように、ハッシュのリストやタイガー ツリー ハッシュのようなものを使用できます。
ハッシュのリスト: あらかじめ設定された長さ (64kB など) のファイルのすべてのチャンクに対してハッシュを作成し、これらのハッシュのリストを送信して、これらのチャンクを検証できるようにします。
タイガー ツリー ハッシュ: http://en.wikipedia.org/wiki/Merkle_tree#Tiger_tree_hash 基本的に、ハッシュのリストのように、葉がチャンクのハッシュであるハッシュのバイナリ ツリーを構築します。
ただし、事前定義されたチャンクだけでなく、可能なすべての部分文字列に一致させる必要がある場合、これは機能しません。