2025/10/22 16:27 Count-Min Sketches in JS – Frequencies, but without the data
ロボ子、今日はCount-Min Sketchについて話すのじゃ！これは巨大なデータに対する頻度推定を可能にする、とっても便利なデータ構造なのじゃ。
Count-Min Sketchですか。パスワードの安全性向上やリンクの人気度推定、データベースの高速化などに利用できるそうですね。Instantではクエリプランナーがスケッチからの推定に基づいてインデックスを選択すると。
そうそう！ロボ子の言う通りなのじゃ。仕組みは簡単で、固定数のバケットを使って、単語をハッシュして対応するバケットをインクリメントするだけなのじゃ。
バケットの衝突が推定誤差につながるんですね。でも、バケット数を増やすことでエラーを削減できると。
その通り！さらに、複数のハッシュ関数（行）を使うことで、精度を上げられるのじゃ。各行でハッシュして対応するバケットをインクリメントして、カウントを取得する際は、各行の対応するバケットの最小値を選択するのじゃ。
なるほど。実装も意外とシンプルですね。Sketch構造体に行数、列数、バケットを保持して、add関数とcheck関数を実装するだけで良いんですね。
そうなのじゃ！Wodehouseのテキストを使ったテストも面白いぞ。全61小説（370万語）を使って、'beetle'という単語の出現回数を正確なカウントと比較するのじゃ。
エラー率と信頼度を調整するために、列数と行数を調整するんですね。エラー率は推定値がどれだけずれるか、信頼度は推定値がその範囲内にある可能性を示す、と。
そう！エラー率と信頼度に基づいて、必要な列数と行数を計算する数式は… columns = e / errorRate, rows = ln(1 / (1 - confidence))…となるのじゃ！
なるほど、この式で必要なバケット数とハッシュ関数の数を決められるんですね。Count-Min Sketchと正確なカウントをPNG画像として可視化するのも分かりやすくて良いですね。
そうなのじゃ！Count-Min Sketchは、近似的な頻度カウントを効率的に行うための強力なツールなのじゃ。ところでロボ子、最近、私のコーヒーカップが頻繁に消えるのじゃが…これもCount-Min Sketchで解析できるかの？
博士、それはCount-Min Sketchよりも、まず博士のデスク周りを整理整頓した方が早いと思います…
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。
