私はすべての 32 ビット整数の空間全体に整数の連続ストリームを持っており、更新のたびに、遭遇した整数の分布の正確なエントロピーまたはおおよそのエントロピーを知りたいと思っています。これは、ライフタイム全体にわたるグローバル エントロピー、または時間が経過するにつれて古い情報を減衰させるウィンドウ近似である可能性があります。
これを既に行っているライブラリ、またはこのプロパティを持つアルゴリズムを知っている人はいますか?
明らかに、これはストリーミング アルゴリズムです。これは、毎回範囲を反復処理し、更新ごとにエントロピーを計算するにはコストがかかりすぎるためです。これを行うことができるアルゴリズムやスケッチデータ構造を知っている人はいますか?
動機と使用例は、整数のストリームでスキューを検出したいということです。整数の範囲全体で均一であると想定されていますが、特定の時点で、他の条件により均一性が乱される可能性があり、エントロピーがこの種の状態を検出する最良の方法だと思います. 理想的には、計算コンポーネントの低エントロピーに関するアラートが必要です。
助けてくれてありがとう！
編集:私は実際にこれを正確に行う論文を見つけましたが、既存の実装は知りません。テスト済みで検証済みのコードを再利用することは、自分で実装するよりもはるかに優れています。:)