文章来源于网络收集而来，版权归原创者所有，如有侵权请及时联系！

11.6 概率数据结构

发布于 2024-01-25 21:44:08 字数 25881 浏览 0 评论 0 收藏 0

概率数据结构允许你以精度来换取大幅度的内存使用下降。除此之外，你能在它们之上所做的操作数量比set或者trie树要有限得多。例如，使用一个单独的耗费2.56KB的HyperLogLog++结构，你能够计数唯一项的数量一直到大约7900000000项，而具有1.625%的误差。

这意味着如果我们尝试计数唯一的汽车牌照数字，如果我们的HyperLogLog++计数器得出有654192028，我们就会置信实际的数目在643561407到664822648之间。而且，如果这个精度不够，你可以仅仅给结构增加更多的内存，它就会做得更好。给它40.96KB的资源就会让误差从1.625%降低到0.4%。无论如何，即使假设没有开销，把这数据存储到一个set中也会耗费3.925GB！

另一方面，HyperLogLog++结构将只能够对一个集合的牌照进行计数，并合并另一个集合的牌照。如此这般，我们就能够让每一个州有一个这样的结构，查找在那些州中有多少独立的牌照，然后再把它们合并起来得到整个国家的计数。如果给我们一个牌照，我们无法以非常优秀的准确度来告诉你我们以前是否见过它，而且我们无法给你一个我们曾经见过的牌照样本。

当你已经花费了时间去理解问题并且需要投入生产来能够回答关于一个非常巨大的数据集上的一个很小的问题集时，概率数据结构是奇妙的。每种不同的数据结构有它能够以不同的精度来回答的不同问题，所以找到合适的数据结构只和理解你的需求相关。

几乎在所有情况下，概率数据结构通过找到对数据的另一种表示形式来工作，这种表示更紧凑并且包含与回答某个问题集相关的信息。可以把这看成一种有损压缩的类型，我们可能丢失了数据的某些方面，但是却保留了必要的成分。既然我们允许数据丢失掉与我们所关心的特定问题集不一定相关的部分，这种有损压缩能够比我们之前使用trie树所看到的无损压缩高效得多。正因为如此，你选择使用哪种概率数据结构是相当重要的——你想要挑选为你的使用场景保留了合适信息的那一个！

在我们深入探索之前，应该澄清这里的“误差率”由标准差来定义。这个术语源自于描述高斯分布，说明函数围绕一个中心值的发散程度。当标准差增长时，值的数量就更偏离中心点。概率数据结构的误差率因此成名就是因为围绕着它们的所有分析都是基于概率的。如此这般，当我们说HyperLogLog++算法有一个err的误差时，我们意思是指有66%的机会误差会小于err，有95%的机会小于2*err，有99.7%的机会小于3*err。^[2]

11.6.1　使用1字节的Morris计数器来做近似计数

我们将介绍使用其中最早期的一种概率计数器——Morris计数器（以NSA和贝尔实验室的Robert Morris来命名）来做概率计数的主题。应用包括在RAM受限的环境中（例如，在一台嵌入式计算机上）对数百万个对象进行计数，理解大数据流，以及类似图像和语音识别之类的问题。

Morris计数器跟踪一个指数并以2^exponent来对计数状态建模（不是一个正确的计数）——它提供了一个数量级的估计。这个估计使用概率规则来更新。

我们开始把指数设为0。如果我们请求计数器的值，我们会给出pow(2,exponent) =1（敏锐的读者会注意到这偏差一个——我们的确说过这是近似计数器！）。如果我们让计数器自增，它将会产生一个随机数（使用均匀分布），并且它会测试是否random(0,1) <= 1 / pow(2, exponent)，对（pow(2, 0) == 1）始终为真。计数器自增，并把指数设为1。

我们让计数器第二次自增，它就会测试是否random(0, 1) <= 1 / pow(2, 1)。这将会有50%的机会为真。如果测试通过，那么指数就递增了。如果不通过，那么对于这次递增请求，指数不递增。

表格11-1显示了对于每一个首指数，递增发生的几率。

表11-1　　Morris计数器细节

exponent

pow(2, exponent)

P(increment)

0.5

0.25

0.125

0.0625

…

254

2.894802e+76

3.454467e-77

为指数使用一个单独的无符号字节，我们能够近似计数的最大值是math.pow(2, 255) == 5e76。当总数增大时，相对实际数量的误差就会变大，但是节省下来的RAM多得惊人，因为我们只使用了1字节，否则我们只好用32位的无符号多字节。例11-20展示了Morris计数器的一个简单实现。

例11-20　简单的Morris计数器实现

from random import random

class MorrisCounter(object):
  counter = 0
  def add(self, *args):
    if random() < 1.0 / (2 ** self.counter):
      self.counter += 1

  def __len__(self):
    return 2**self.counter

使用这个例中的实现，我们能够看到在例11-20中，第一个递增计数器的请求成功了，而第二个失败了。^[3]

例11-21　Morris计数器库的例子

In [2]: mc = MorrisCounter()
In [3]: print len(mc)
1.0
In [4]: mc.add() # P(1) of doing an add
In [5]: print len(mc)
2.0
In [6]: mc.add() # P(0.5) of doing an add
In [7]: print len(mc) # the add does not occur on this attempt
2.0

在图11-3中，粗黑线显示了一个通常的在每一次迭代中递增的整数。在一个64位的计算机上，这是一个8字节的整数。三个1字节的Morris计数器的演进以点线来显示；Y轴显示它们的值，近似表示了每次迭代中的真实的数量。展示了三个计数器来给你一个关于它们的不同轨迹以及总体趋势的概念。三个计数器完全相互独立。

图11-3　三个1字节的Morris计数器对比一个8字节的整数

这张图表给你一些使用Morris计数器时所要期望的误差概念。关于误差表现的进一步细节在线上有提供。

11.6.2　K最小值

在Morris计数器中，我们丢失了所插入的项目的任何类型的信息。那就是说，计数器的内部状态是相同，而不管我们是.add(“micha”)还是.add(“ian”)。额外的信息是有用的，如果使用得当，能够帮助我们的计数器只对唯一项进行计数。这样做的话，调用.add(“micha”)几千次将只会增加计数器一次。

为了实现这种行为，我们将探索散列函数的属性（请看4.1.4节来得到对散列函数的更深入的讨论）。

我们想要利用的主要属性就是基于这样一个事实：散列函数获取输入并且均匀地分配它。例如，让我们假设有一个散列函数获取一个字符串并输出一个0到1之间的数字。那个函数均匀分布意味着当我们给它输入一个字符串时，我们以与得到一个0.2的值相等的几率来得到一个0.5的值，或者任何一个其他的值。这也意味着如果我们给它输入很多字符串值，我们将期望这些值被相对均匀排布。记住，这是一个概率化的论点：值不是总会被均匀排布，但是如果我们有许多字符串，并且尝试了这个实验很多次，它们会趋向于均匀地排布。

假设我们获取了100项并存储了那些值的散列（散列从0到1数数）。知道均匀排布意味着与其说“我们有100项”，不如说“我们每一项之间的间隔是0.01”。这是K最小值算法^[4]最终的出处——如果我们保存了我们所见到的k个最小的唯一散列值，我们就能近似估算散列值的总体空间，并且推导出这些项的全部数量。在图11-4中，当越来越多的项加进来时，我们能看见一个K最小值结构（也叫作一个KMV）的状态。首先，既然我们没有很多散列值，我们保存的最大散列就是相当大的。当我们把越来越多项加进来时，我们所保存的最大的k个散列值就会变得越来越小。使用这个方法，我们能够得到O$\left( \frac{2}{\pi \left( k-2 \right)} \right)$的误差率。

k越大，我们就越能说明我们所使用的散列化函数对于我们的特定输入不是完全均匀的，而且还是造成不幸散列值的原因。一个不幸散列值的例子就是对[‘A’, ‘B’, ‘C’]做散列化，得到了值[0.01, 0.02, 0.03]。如果我们开始散列化越来越多的值，它们会聚合起来的可能性就越来越少。

而且，既然我们只保留最小的唯一散列值，数据结构只考虑唯一的输入。我们早就能看到这个，因为如果我们处在一个只存储了最小的三个散列并且当前[0.1, 0.2, 0.3]是最小的散列的状态中，如果我们增加了任何散列值是0.4的项，我们的状态将保持不变。同样，如果我们添加了散列值是0.3的更多项进来，我们的状态也不会改变。这是一个叫作幂等性的属性，它意味着如果我们对这个结构多次用相同的输入做相同的操作，状态将保持不变。这与某些结构相反，例如，在一个list的尾部添加总是会改变它的值。幂等性的概念贯穿于本小节中的所有数据结构，但是除了Morris计数器之外。

例11-22展示了一个非常基本的K最小值实现。值得注意的是我们使用了一个sortedset，它就像一个set，但是只包含唯一项。这种唯一性免费地把幂等性给了我们的KMinValues结构。为了看到它，请跟随代码：当相同的项被加入了超过一次，数据属性不发生改变。

图11-4　当更多的元素加进来时，值存储在一个KMV结构中

例11-22　简单的KMin值实现

import mmh3
from blist import sortedset

class KMinValues(object):
  def __init__(self, num_hashes):
    self.num_hashes = num_hashes
    self.data = sortedset()

  def add(self, item):
    item_hash = mmh3.hash(item)
    self.data.add(item_hash)
    if len(self.data) > self.num_hashes:
      self.data.pop()

  def __len__(self):
    if len(self.data) <= 2:
    return 0
  return (self.num_hashes - 1) * (2**32-1) / float(self.data[-2] + 2**31 - 1)

使用在Python的包countmemaybe（例11-23）中的KMinValues的实现，我们可以开始看看这个数据结构的用途。这个实现与例11-22中的非常类似，但是它完全实现了其他的集合操作，例如并集与交集。也要注意“大小”和“势”被交替使用（单词“势”来自于集合理论，更多的在分析概率数据结构中被用到）。在这里，我们能看见即使让k使用一个小得合理的值，我们也能够存储50000项，而且能够以相对低的误差计算许多集合操作的势。

例11-23　countmemaybe的KMinValue实现

>>> from countmemaybe import KMinValues

>>> kmv1 = KMinValues(k=1024)

>>> kmv2 = KMinValues(k=1024)

>>> for i in xrange(0,50000): # ❶
  kmv1.add(str(i))
   ...:

>>> for i in xrange(25000, 75000): # ❷
  kmv2.add(str(i))
   ...:

>>> print len(kmv1)
50416

>>> print len(kmv2)
52439

>>> print kmv1.cardinality_intersection(kmv2)
25900.2862992

>>> print kmv1.cardinality_union(kmv2)
75346.2874158

❶ 我们在kmv1中放入了50000个元素。

❷ 在kmv2中也放入50000个元素，其中25000个与在kmv1中的相同。

　备忘　

使用这些类型的算法，散列函数的选择对于估算的质量具有巨大的影响。这些实现都使用了mmh3，Python实现的mumurhash3对于散列化字符串具有良好的属性。无论如何，可以使用不同的散列函数，如果它们对你特定的数据集更方便的话。

11.6.3　布隆过滤器

有时我们需要能够做其他类型的集合操作，为此，我们需要引入新的概率数据结构类型。布隆过滤^[5]被创造出来用以回答我们是否在之前看到过一个条目的问题。

布隆过滤器通过多散列值的方式来工作，用于把一个值表示成多个整数。如果我们之后看到了相同的整数集，我们就能相当确信这就是相同的值。

为了以高效利用可用的资源的方式做到这一点，我们暗暗地把整数编码成一个列表的索引。这可能被看作一个初始化成False的布尔型的列表。如果我们被要求增加一个散列值为[10, 4, 7]的对象，那么我们设置列表的第十、第四和第七个索引为True。将来，如果我们被问到以前是否看见到一个特定的条目，我们仅仅查找它的散列值并检查布尔型列表中对应的点是否设置成了True。

这种方法不会给我们带来假阴性，而会给我们带来一个可控的假阳性率。这意味着如果布隆过滤器说我们以前没有看见过一个条目，那么我们100%确认我们的确以前没有见过该条目。另一方面，如果布隆过滤器说我们以前曾看见过一个条目，那么有一定的概率我们其实并没有看见过，并且我们只是看见了一个错误的结果。这个错误的结果来自于我们会有散列冲撞的事实，有时两个对象的散列值会是相同的，即使它们不是同一个对象。无论如何，在实践中，布隆过滤器被设置成具有不到0.5%的误差率，所以这种错误是可以被接受的。

　备忘　

我们可以仅凭两个相互独立的散列函数来模拟具有我们想要的数量的散列函数。这个方法被称作“双散列”。如果我们有一个给出两个相互独立的散列值的散列函数，我们可以这样做：

def multi_hash(key, num_hashes):
  hash1, hash2 = hashfunction(key)
  for i in xrange(num_hashes):
    yield (hash1 + i * hash2) % (2^32 - 1)

模数确保了作为结果的散列值是32比特的（我们可以通过2^64 – 1来为64比特的散列函数求摸）。

我们所需的布尔型列表的准确长度以及每一个条目的散列值的数量将基于我们所要求的容量和误差率而定。使用一些相当简单的统计参数^[6]，我们看到理想的值就是：

[\begin{align}

& num_bits=-capacity\cdot \frac{\log (error)}{\log {{(2)}^{2}}} \

& num_hashes=num_bits\cdot \frac{\log (2)}{capacity} \

\end{align}]

那就是说，如果我们希望以0.05%的假阳性（那就是说，当我们说曾经看到过一个对象时，有0.05%的几率其实我们并没有见过它）来存储50000个对象（不管对象自己有多大），那就需要791015比特的存储空间和11个散列函数。

为了进一步提高我们使用内存的效率，我们能够使用单个比特来表示布尔值（一个本地的布尔型实际上占用4比特位）。我们能够通过使用bitarray模块来轻易地做到。例11-24展示了一个简单的布隆过滤器的实现。

例11-24　简单的布隆过滤器实现

import bitarray
import math
import mmh3

class BloomFilter(object):
  def __init__(self, capacity, error=0.005):
    """
    Initialize a Bloom filter with given capacity and false positive rate
    """
    self.capacity = capacity
    self.error = error
    self.num_bits = int(-capacity * math.log(error) / math.log(2)**2) + 1
    self.num_hashes = int(self.num_bits * math.log(2) / float(capacity)) + 1
    self.data = bitarray.bitarray(self.num_bits)

  def _indexes(self, key):
    h1, h2 = mmh3.hash64(key)
    for i in xrange(self.num_hashes):
      yield (h1 + i * h2) % self.num_bits

  def add(self, key):
    for index in self._indexes(key):
      self.data[index] = True

  def __contains__(self, key):
    return all(self.data[index] for index in self._indexes(key))

  def __len__(self):
    num_bits_on = self.data.count(True)
    return -1.0 * self.num_bits *
          math.log(1.0 - num_bits_on / float(self.num_bits)) /
            float(self.num_hashes)

  @staticmethod
  def union(bloom_a, bloom_b):
    assert bloom_a.capacity == bloom_b.capacity, "Capacities must be equal"
    assert bloom_a.error == bloom_b.error, "Error rates must be equal"

    bloom_union = BloomFilter(bloom_a.capacity, bloom_a.error)
    bloom_union.data = bloom_a.data | bloom_b.data
    return bloom_union

如果我们插入的条目超过了我们对布隆过滤器所声明的容量，那么会发生什么呢？最终，布尔型列表中的所有条目都被设置成了True，在这种情况下，我们说我们已看见了每一个条目。这意味着布隆过滤器对所设置的初始容量很敏感，如果我们正在处理一个不知道大小的数据集（例如，数据流），情况就会相当恶劣。

处理这种情况的一种方法就是使用布隆过滤器的变体，被称作可扩展的布隆过滤器^[8]把误差率不同的多个布隆过滤器串联在一起来工作。通过这样做，我们能够保证一个总体的误差率，并且当需要更多容量时，仅仅增加一个新的布隆过滤器。为了检测我们之前是否曾经看到过一个条目，我们只是在所有的子布隆过滤器上进行遍历，直到我们找到该对象或者消耗完列表。这种结构的一个简单实现可以在例11-25中见到，我们使用了之前的布隆过滤器作为底层机能，并且有一个计数器来简化了解什么时候该增加一个新的布隆过滤器。

例11-25　简单的扩展布隆过滤器实现

from bloomfilter import BloomFilter

class ScalingBloomFilter(object):
  def __init__(self, capacity, error=0.005,
           max_fill=0.8, error_tightening_ratio=0.5):
    self.capacity = capacity
    self.base_error = error
    self.max_fill = max_fill
    self.items_until_scale = int(capacity * max_fill)
    self.error_tightening_ratio = error_tightening_ratio
    self.bloom_filters = []
    self.current_bloom = None
    self._add_bloom()

  def _add_bloom(self):
    new_error = self.base_error *
          self.error_tightening_ratio ** len(self.bloom_filters)
    new_bloom = BloomFilter(self.capacity, new_error)
    self.bloom_filters.append(new_bloom)
    self.current_bloom = new_bloom
    return new_bloom

  def add(self, key):
    if key in self:
      return True
    self.current_bloom.add(key)
    self.items_until_scale -= 1
    if self.items_until_scale == 0:
      bloom_size = len(self.current_bloom)
      bloom_max_capacity = int(self.current_bloom.capacity * self.max_fill)

      # We may have been adding many duplicate values into the Bloom, so
      # we need to check if we actually need to scale or if we still have
      # space
      if bloom_size >= bloom_max_capacity:
        self._add_bloom()
        self.items_until_scale = bloom_max_capacity
      else:
        self.items_until_scale = int(bloom_max_capacity - bloom_size)
    return False

def __contains__(self, key):
    return any(key in bloom for bloom in self.bloom_filters)

def __len__(self):
    return sum(len(bloom) for bloom in self.bloom_filters)

处理这种情况的另一种方式就是使用一种称作计时布隆过滤器的方法。这种变体允许元素超时而被移出数据结构，这样就为更多的元素腾出了空间。对流处理尤其有效，因为我们能够让元素超时，比如说一小时之后，而且把容量设置得足够大以便能处理我们每小时看到的数据量。以这种方式使用布隆过滤器将会带给我们对最近一小时内发生的事情的良好视图。

使用这种数据结构感觉和使用一个集合对象很像。在下面的交互中，我们使用可扩展的布隆过滤器来增加几个对象，测试下是否曾经见到过它们，接着尝试以实验的方法找到假阳性率：

>>> bloom = BloomFilter(100)

>>> for i in xrange(50):
   ....:   bloom.add(str(i))
   ....:

>>> "20" in bloom
True

>>> "25" in bloom
True

>>> "51" in bloom
False

>>> num_false_positives = 0

>>> num_true_negatives = 0

>>> # None of the following numbers should be in the Bloom.
>>> # If one is found in the Bloom, it is a false positive.
>>> for i in xrange(51,10000):
   ....:   if str(i) in bloom:
   ....:     num_false_positives += 1
   ....:   else:
   ....:     num_true_negatives += 1
   ....:

>>> num_false_positives
54

>>> num_true_negatives
9895

>>> false_positive_rate = num_false_positives / float(10000 - 51)

>>> false_positive_rate
0.005427681173987335

>>> bloom.error
0.005

为了联合多个条目组，我们也可以用布隆过滤器做并集：

>>> bloom_a = BloomFilter(200)

>>> bloom_b = BloomFilter(200)

>>> for i in xrange(50):
   ...:   bloom_a.add(str(i))
   ...:

>>> for i in xrange(25,75):
   ...:   bloom_b.add(str(i))
   ...:

>>> bloom = BloomFilter.union(bloom_a, bloom_b)

>>> "51" in bloom_a # ❶
Out[9]: False

>>> "24" in bloom_b # ❷
Out[10]: False

>>> "55" in bloom # ❸
Out[11]: True

>>> "25" in bloom
Out[12]: True

❶ 值“51”不在bloom_a中。

❷ 同样，值“24”不在bloom_b中。

❸ 无论如何，bloom对象包含了在bloom_a和bloom_b中的所有对象！

使用它的一个警告就是你只能对两个具有相同容量和误差率的布隆过滤器做并集。而且，最终的布隆过滤器所使用的容量能够与组成它的两个做并集的布隆过滤器所使用的容量之和一样大。这意味着你可能从两个布隆过滤器开始，它们各自填满了不到一半容量，当你把它们做并集联合起来时，就会得到一个新的超过容量并且不可靠的布隆过滤器！

11.6.4　LogLog计数器

LogLog类型的计数器基于散列函数的单个比特位也能被看作是随机的事实。那就是说，一个散列的第一个比特是1的概率是50%，前两个比特是01的概率是25%，而前三个比特是001的概率是是12.5%。知道了这些概率，让散列在开始处保持最多的0（例如，最不可能的散列值），我们就能估算出我们曾经见到了多少项条目。

一个对这种方法很好的类比就是投掷硬币。想象一下我们将要投掷一枚硬币32次，而且每次都是正面朝上。32这个数字来源于我们使用32比特的散列函数的事实。如果我们投掷一次，它反面朝上，我们就存储数字0，因为我们的最佳尝试接连产生了0次正面。既然我们知道在这枚硬币投掷背后的概率，我们也能够告诉你我们最长的序列就是0长度的，你能估算出我们尝试实验了2^0 = 1次。如果我们继续投掷硬币而且能够在得到一次反面之前得到10次正面，那么我们就能存储数字10。使用相同的逻辑，你就能估算出我们尝试实验了2^10 = 1024次。使用这个系统，我们所能计数的最大值就是我们所考虑投掷的最大次数（对于32次投掷来说，这就是2 ^ 32 = 4294967296）。

为了使用LogLog类型计数器对这个逻辑进行编码，我们对输入的散列值采用了二进制的表示，并且观察在我们看到第一个1之前有多少个0。散列值能够被视作一个32次硬币投掷的序列，0意味着投掷出了一次正面朝上，1意味着投掷出了一次反面朝上（例如，000010101101意味着我们在得到第一次反面之前投掷出了4次正面，010101101意味着我们在第一次投掷出反面之前投掷出了一次正面）。这带给我们一个在得到这个散列值前尝试过几次的想法。在这个系统背后的数学问题几乎等价于Morris计数器，除了一个主要的例外：我们是通过查看实际的输入而不是使用一个随机数生成器来获得“随机”值的。这意味着如果我们继续给一个LogLog计数器增加相同的值，它的内部状态将不会改变。例11-26展示了一个LogLog计数器的简单实现。

例11-26　LogLog计数器的简单实现

import mmh3

def trailing_zeros(number):
  """
  Returns the index of the first bit set to 1 from the right side of a 32-bit
  integer
  >>> trailing_zeros(0)
  32
  >>> trailing_zeros(0b1000)
  3
  >>> trailing_zeros(0b10000000)
  7
  """
  if not number:
    return 32
  index = 0
  while (number >> index) & 1 == 0:
    index += 1
  return index

class LogLogRegister(object):
  counter = 0
  def add(self, item):
    item_hash = mmh3.hash(str(item))
    return self._add(item_hash)

  def _add(self, item_hash):
    bit_index = trailing_zeros(item_hash)
    if bit_index > self.counter:
      self.counter = bit_index

  def __len__(self):
    return 2**self.counter

这个方法的最大缺点就是我们可能得到一个一开始就增加计数器的散列值，这会歪曲我们的估算。这就类似于在第一次尝试时投掷出了32次反面。为了弥补，我们应该让许多人同时投掷硬币并且组合他们的结果。大数定律告诉我们当增加越来越多的投掷者时，总体统计量越少受到单独的投掷者的异常样本的影响。我们组合多个结果的确切方式就是LogLog类型方法的根本性差异（经典的LogLog、SuperLogLog、HyperLogLog、HyperLogLog++等）。

我们能够完成这个“多个投掷者”方法，通过采用散列值的首对比特位来指定我们的投掷者中哪一位投掷者具有特定的结果。如果我们采用散列值的前4个比特，这意味着我们有2^4=16个投掷者。既然我们这次选择了使用前4个比特，我们只剩下了28个比特（对应于每一个硬币投掷者独立地投掷28次硬币），这意味着每一个计数器只能计数到2^28 = 268435456。此外，有一个依赖于投掷者数量的常数（alpha）对估算做正则化^[9]。所有这些一起带给我们一个具有的准确度的算法，m是所用寄存器的数量（或者说投掷者）。例11-27展示了一个简单的LogLog算法的实现。

例11-27　简单的LogLog实现

from llregister import LLRegister
import mmh3

class LL(object):
  def __init__(self, p):
    self.p = p
    self.num_registers = 2**p
    self.registers = [LLRegister() for i in xrange(int(2**p))]
    self.alpha = 0.7213 / (1.0 + 1.079 / self.num_registers)

  def add(self, item):
    item_hash = mmh3.hash(str(item))
    register_index = item_hash & (self.num_registers - 1)
    register_hash = item_hash >> self.p
    self.registers[register_index]._add(register_hash)

  def __len__(self):
    register_sum = sum(h.counter for h in self.registers)
    return self.num_registers * self.alpha *
              2 ** (float(register_sum) / self.num_registers)

这个算法除了使用散列值作为一个指示器来把相似的条目去重之外，还有一个可调制的参数，能够用来在要达到哪种类型的准确度相对于你想要做出的空间妥协之间进行调拨。

在__len__方法中，我们对来自于所有单个LogLog寄存器的估算值求它们的平均值。无论如何，这不是我们组合数据的最高效的方式！这是因为我们可能得到一些不幸的散列值使得某个特定的寄存器有孤峰值，而其他的则还处于低值。正因为如此，我们只能达到O$\left( \frac{1.30}{\sqrt{m}} \right)$的误差率，m是所使用的寄存器的数量。

SuperLogLog^[10]被设计用来修正这个问题。使用这个算法，只有最低的 70%的寄存器用来做大小估算，它们的值被一个由限制规则给出的最大值所束缚。这个附加特性把误差率减少到了O$\left( \frac{1.05}{\sqrt{m}} \right)$。

我们通过忽略信息的方式来得到一个更好的估算值，这是违反直觉的！

最后，HyperLogLog^[11]在2007年出现，并且给我们带来了进一步的准确度收益。它仅仅通过改变对单个寄存器做平均的方法就做到了：我们使用了球状平均方案，对结构可能所处的不同的边缘情况都做了特殊的考虑，而不是仅仅做平均值。这带给我们当前最好的误差率O$\left( \frac{1.04}{\sqrt{m}} \right)$。此外，这个公式移除了对SuperLogLog来说是必须的排序操作。当你设法插入大量条目时，这能大大提升数据结构的性能。例11-28展示了HyperLogLog的一个简单实现。

例11-28　简单的HyperLogLog实现

from ll import LL
import math

class HyperLogLog(LL):
  def __len__(self):
    indicator = sum(2**-m.counter for m in self.registers)
    E = self.alpha * (self.num_registers**2) / float(indicator)

    if E <= 5.0 / 2.0 * self.num_registers:
      V = sum(1 for m in self.registers if m.counter == 0)
      if V != 0:
        Estar = self.num_registers *
            math.log(self.num_registers / (1.0 * V), 2)
      else:
        Estar = E
    else:
      if E <= 2**32 / 30.0:
        Estar = E
      else:
        Estar = -2**32 * math.log(1 - E / 2**32, 2)
    return Estar

if __name__ == "__main__":
  import mmh3
  hll = HyperLogLog(8)
  for i in xrange(100000):
    hll.add(mmh3.hash(str(i)))
  print len(hll)

HyperLogLog++是唯一的进一步增加了准确度的算法，当数据结构相对空时，增加了它的准确度。当更多的条蜜插入时，这个方案转向于标准的HyperLogLog。其实这是相当有用的，因为LogLog类型计数器的统计量需要许多准确的数据——有一种允许使用更少量的条目来获取更高的准确度的方案大大提高了这种方法的可用性。这种额外的准确度通过一个更小的但是更准确的HyperLogLog结构来达到，它以后能够被转换成一个原先所请求的更大的结构。也有一些根据经验得出的常数被用在大小估算中来消除偏差。

11.6.5　真实世界的例子

为了更好理解数据结构，我们首先创建了一个具有很多唯一键的数据集，接着创建一个具有重复条目的数据集。当我们把这些键输入这些数据结构后，只是观察它们并周期性地询问：“已经有多少唯一条目了？”，图11-5和图11-6展示了结果。我们能看到包含更多有状态的变量（例如HyperLogLog和KMinValues）的数据结构做得更好，因为它们更健壮地处理了糟糕的统计量。另一方面，如果产生了一个不幸随机数或者不幸散列值，Morris计数器和单个LogLog寄存器就可能快速发生很高的误差率。无论如何，对于大多数算法而言，我们知道有状态变量的数量直接和所能确保的错误相关，所以这就是有意义的。

图11-5　各种不同的概率数据结构对于重复数据的对比

只看具有最佳性能（实际上，你可能会使用的那些）的概率数据结构，我们可以总结出它们的效用和大概的内存使用（参见表11-2）。我们可以看到内存使用的巨大变化取决于我们所关心的问题。这仅仅强调了这样一个事实：当使用一个概率数据结构时，你必须首先考虑在继续进行之前，有关数据集的什么问题是你真正需要回答的。也要注意只有布隆过滤器的大小取决于元素的数量。HyperLogLog和KMinValue的大小只取决于误差率。

作为另一个更为真实的测试，我们选择使用了一个派生自维基百科文本的数据集。我们运行了一个很简单的脚本来从所有的文章中抽取出具有5个字符的所有单词符号，并把它们存储在一个用换行符分隔的文件中。那么问题就是：“有多少唯一的符号？”在表11-3中能看到结果。此外，我们企图使用来自于11.4节中的datrie树来回答相同的问题（这个trie树被选来与其他数据结构做对比，因为它提供了良好的压缩性，然而却还是足够鲁棒来处理完整的数据集）。

来自于这个实验的主要副品就是如果你能够特殊化你的代码，你就能得到令人惊叹的速度和内存收益。贯穿于整本书，这都是真实的：当你对6.4.2节中的代码进行特殊化处理时，我们就同样能得到速度提升。

表11-2　　主要概率数据结构的比较

误差率

并集^a

交集

是否包含

大小^b

HyerLogLog

是（O）

是

不^c

不

2.704MB

KMinValues

是（O）

是

不

20.372MB

布隆过滤器

是（O）

是

不^c

是

192.8MB

a．并集操作不会增加误差率。

b．数据结构大小，具有0.05%的误差率，100000000个唯一元素，使用一个64比特的散列函数。

c．这些操作能够做，但是对准确度有一个不可忽视的惩罚。

图11-6　各种不同的概率数据结构对于唯一数据的对比

概率数据结构是一种对你的代码做特殊化处理的算法。我们只存储所需的数据来以给定的错误上界回答特定的问题。通过只处理所给信息的子集，我们不仅能够让内存占用空间减少很多，而且也能够在这些结构上更快地执行大部分操作（就如在表11-3中所能见到的那样，插入datrie树的时间比任何一种概率数据结构要来得多）。

表11-3　　对维基百科中的唯一单词的数量的估计

元素

相对误差

处理时间^a

结构大小^b

Morris计数器^c

1 073 741 824

6.52%

751秒

5bit

LogLog寄存器

1 048 576

78.84%

1 690秒

5bit

LogLog

4 522 232

8.76%

2 112秒

5bit

HyperLogLog

4 983 171

-0.54%

2 907秒

40KB

KMinValues

4 912 818

0.88%

3 503秒

256KB

可扩展布隆过滤器

4 949 358

0.14%

10 392秒

11509KB

datrie树

4 505 514d

0.00%

14 620秒

114068KB

真值

4 956 262

0.00%

-----

49558KB^e

a．处理时间已经被调整过，移除了从磁盘读取数据集的时间。我们也使用之前所提供的简单实现来做测试。

b．结构大小是在给出数据量前提下的理论值，因为所用的实现没有去优化。

c．因为Morris计数器不会对输入去重，结构体大小和相对误差按照值的总数量给出。

d．因为一些编码问题，datrie树不能加载所有的键。

e．只考虑唯一的符号，数据集是49558KB，考虑所有的符号，则是8.742GB。

作为结果，无论你是否使用概率数据结构，你应该总是记住你打算要问你的数据哪些问题，以及你如何能够最高效地存储数据以便去问那些特别的问题。这可能归结于使用一种特定类型的列表，使用一种特定类型的数据库索引，或者甚至可能使用一个概率数据结构来抛弃掉除了相关数据以外的所有数据！

[1]　这个例子取自关于确定性无环有限状态机（DAFSA）的维基文章。DAFSA是DAWG的另一个名称。附随的图片来自于维基共享资源。

[2]　这些数字来自于高斯分布的66-95-99规则。更多的信息能够在维基百科条目中找到。

[3]　一个更加完全崭新的使用了一个字节数组来创建多计数器的实现在https://github.com/ianozsvald/morris_counter中可用。

[4]　Beyer,K.,Haas, P.J., Reinwald, B., Sismanis, Y.,和Gemulla, R.“在多集和操作下，有关对独立值估算的概要”。2007年ACM SIGMOD数据管理国际会议进展——SIGMOD ’07, (2007): 199–210. doi:10.1145/1247480.1247504。

[5]　Bloom,B.H. “以允许的误差使用hash编码做空间/时间的权衡。”ACM通信。13:7（1970）：422-426 doi:10.1145/362686.362692

[6]　维基关于布隆过滤器的页面上有一个非常简单的对布隆过滤器属性的证明。

[7]　Almeida, P. S., Baquero, C., Preguica, N., and Hutchison, D.“可扩展布隆过滤器”。信息处理信件 101: 255–261. doi:10.1016/j.ipl.2006.10.007。

[8]　错误值实际上会降低，类似于几何级数。这样，当你采用所有误差率的乘积时，它就趋近于所期望的误差率。

[9]　一个对基础LogLog和SuperLogLog算法的完整描述可以在http://bit.ly/algo rithm_desc中找到。

[10]　Durand, M., and Flajolet, P. “大基数的LogLog计数”。会刊：ESA 2003, 2832 (2003): 605–617. doi:10.1007/978-3-540-39658-1_55。

[11]　Flajolet, P., Fusy, E., Gandouet, O., et al. “HyperLogLog：对近似最优的基数估计算法的分析”。2007年算法分析国际会议会刊，（2007）：127-146。

分享到QQ

分享到微博