17

Zipf 確率分布は、P2P システム内のアイテムのファイル サイズ分布またはアイテム アクセス分布をモデル化するためによく使用されます。たとえば、「Web キャッシングと Zip のような分布の証拠と影響」ですが、BoostもGSL (Gnu Scientific Library)も、この分布を使用して乱数を生成する実装を提供していません。一般的な検索エンジンを使用した (信頼できる) 実装は見つかりませんでした。

メルセンヌ ツイスターなどの U(0,1) 乱数発生器を使用して Zipf 分布に従って分布する乱数をどのように作成できますか?

4

5 に答える 5

12

n以下は、パラメータ を持つ項目の Python Zipf のような分布ジェネレータですalpha >= 0。

import random 
import bisect 
import math 

class ZipfGenerator: 

    def __init__(self, n, alpha): 
        # Calculate Zeta values from 1 to n: 
        tmp = [1. / (math.pow(float(i), alpha)) for i in range(1, n+1)] 
        zeta = reduce(lambda sums, x: sums + [sums[-1] + x], tmp, [0]) 

        # Store the translation map: 
        self.distMap = [x / zeta[-1] for x in zeta] 

    def next(self): 
        # Take a uniform 0-1 pseudo-random value: 
        u = random.random()  

        # Translate the Zipf variable: 
        return bisect.bisect(self.distMap, u) - 1
于 2012-01-09T12:48:16.150 に答える
11

zipfRは、R で実装された無料のオープン ソース ライブラリです。VGAMも Zipf を実装する別の R パッケージです。

また、 Gnu Scientific Libraryには、実質的に離散 Zipf 分布の連続アナログであるPareto分布が実装されていることも注目に値します。

また、ゼータ分布は、無限Nの Zipf と同等です。GSL にはリーマン ゼータ関数が実装されているため、それを使用して自分で分布を構築できます。

于 2009-09-02T11:05:45.263 に答える
10

numpy.random.zipfは、Python を使用して Zipf サンプルを生成します。

于 2009-09-02T11:15:47.393 に答える
4

最近、Apache Commons Math ライブラリの次のバージョン (>= 3.6) 向けに、Zipf 分布確率変量を生成する非常に効率的なアルゴリズムが開発されました (コードはこちらを参照)。これは、棄却反転サンプリングを利用し、指数が 1 未満の場合にも機能します。CDF を事前に計算してメモリに保持する必要はありません。さらに、1 つのサンプルを生成するためのコストは一定であり、アイテムの数によって増加することはありません。

于 2015-10-18T16:38:26.067 に答える
0

このスレッドで @stanga の回答について話し合っていました。彼のアルゴリズムには、いくつかの優れた最適化が提案されています。

于 2015-06-24T20:20:25.173 に答える