このスケッチを理解しようとしていますが、理解できません。間違っている場合は修正してください。基本的に、テキスト データがあるとしましょう..単語..ハッシュ関数があります..単語を取得して整数ハッシュを作成し、そのハッシュをバイナリ ビット ベクトルに変換しますか?? 右..次に、左から見た最初の 1 を追跡します..そして、その 1 の位置 (たとえば、k)... このセットのカーディナリティは 2^k ですか?
http://ravi-bhide.blogspot.com/2011/04/flajolet-martin-algorithm.html
しかし... 一言だけ言っておきます。それのハッシュ関数は、それが生成するハッシュが2 ^ 5であるようなものであり、私は5つの(??)末尾の0があると推測しています?? 2^5 (??) カーディナリティを予測しますか? それは正しく聞こえませんか？何が足りないの
単一の単語の場合、R の分布は p = 1/2 の幾何分布であり、その標準偏差は sqrt(2) ≈ 1.41 です。
したがって、ハッシュが 100000 bで終わる単語の場合、アルゴリズムは実際に 2 5 /0.77351 = 41.37 を生成します。しかし、その確率はわずか 1/64 であり、これは R の標準偏差が 1 に近いという記述と一致しています。
覚えておくべき本当に重要なことは、Flajolet Martin アルゴリズムは、M が非常に大きいと予想される場合に、N 個の要素のセットから個別の要素 (たとえば、M 個の個別の要素) をカウントすることを目的としていることです。
N または M がメモリにすべての個別の要素を格納するのに十分小さい場合、アルゴリズムを使用しても意味がありません。
N と M が非常に大きい場合、推定値が 2^k に近い確率は実際には非常に妥当です。
これについての説明があります: http://infolab.stanford.edu/~ullman/mmds/ch4.pdf (143 ページ)