問題タブ [flajolet-martin]

このスケッチを理解しようとしていますが、理解できません。間違っている場合は修正してください。基本的に、テキスト データがあるとしましょう..単語..ハッシュ関数があります..単語を取得して整数ハッシュを作成し、そのハッシュをバイナリ ビット ベクトルに変換しますか?? 右..次に、左から見た最初の 1 を追跡します..そして、その 1 の位置 (たとえば、k)... このセットのカーディナリティは 2^k ですか?

http://ravi-bhide.blogspot.com/2011/04/flajolet-martin-algorithm.html

しかし... 一言だけ言っておきます。それのハッシュ関数は、それが生成するハッシュが2 ^ 5であるようなものであり、私は5つの(??)末尾の0があると推測しています?? 2^5 (??) カーディナリティを予測しますか? それは正しく聞こえませんか？何が足りないの

以下は、私が実装するために書いたコードです Flajolet and Martin’s Algorithm。私はデータのJenkins hash function生成に使用しました。32 bit hash valueプログラムはアルゴリズムに従っているように見えますが、約 20% ずれています。私のデータ セットは 200,000 を超える一意のレコードで構成されていますが、プログラムは約 160,000 の一意のレコードを出力します。私が犯した間違いを理解するのを手伝ってください。ハッシュ関数は、Bob Jerkins の Web サイトに従って実装されています。