Zipf齐夫分布及Java实现

Zipf分布

Zipf定律可以表述为在自然语言的语料库里，一个单词的出现次数与它在频率表里的排名成反比。Zip定律也叫二八定律，可以反映很多现象，比如互联网中的内容访问有20%的内容占有80%的访问量，20%的社会人士掌握有80%的财富，等等。Zipf定律是由美国语言学家Zipf发现的，他在1932年研究英文单词出现的频率时，发现如果把单词频率从高到低的次序排列，每个单词出现频率和它的访问排名存在简单反比关系，通过公式表述如下：

C=R∗F C = R ∗ F

这里C为一个常数，R为单词的在语料库中的Rank排名，F为单词在语料库中的出现频率。最简单的齐夫定律的例子是“1/f function”。给出一组齐夫分布的频率，按照从最常见到非常见排列，第二常见的频率是最常见频率的出现次数的½，第三常见的频率是最常见的频率的1/3，第n常见的频率是最常见频率出现次数的1/n。然而，这并不精确，因为所有的项必须出现一个整数次数，一个单词不可能出现2.5次。然而，在一个广域范围内并且做出适当的近似，许多自然现象都符合齐夫定律。

Zipf分布的特征非常适合模拟类似真实世界的一些数据倾斜场景。

Java实现

public class ZipfGenerator implements Serializable { private Random random = new Random(0); private NavigableMap<Double, Integer> map; private static final double Constant = 1.0; public ZipfGenerator(int R, double F) { // create the TreeMap map = computeMap(R, F); } //size为rank个数，skew为数据倾斜程度, 取值为0表示数据无倾斜，取值越大倾斜程度越高 private static NavigableMap<Double, Integer> computeMap( int size, double skew) { NavigableMap<Double, Integer> map = new TreeMap<Double, Integer>(); //总频率 double div = 0; //对每个rank，计算对应的词频，计算总词频 for (int i = 1; i <= size; i++) { //the frequency in position i div += (Constant / Math.pow(i, skew)); } //计算每个rank对应的y值，所以靠前rank的y值区间远比后面rank的y值区间大 double sum = 0; for (int i = 1; i <= size; i++) { double p = (Constant / Math.pow(i, skew)) / div; sum += p; map.put(sum, i - 1); } return map; } public int next() { // [1,n] double value = random.nextDouble(); //找最近y值对应的rank return map.ceilingEntry(value).getValue() + 1; } }

分布情况

N代表数据个数

k代表相应数据的排名

s代表描述数据分布的指数特征，我个人理解为数据倾斜程度，s越大表示数据倾斜的程度约大。

这里引用维基百科中的曲线描述不同s取值情况下的数据分布：