解释计数草图算法

  • Z时代
  • 2024-01-10
  • 分类：问答

有人可以解释计数草图算法的工作原理吗？例如，我仍然不知道如何使用哈希。我很难理解这篇论文。

回答：

此流算法实例化以下框架。

  1. 查找一种随机流算法，其输出（作为随机变量）具有期望的期望，但通常具有较高的方差（即噪声）。

  2. 为了减少方差/噪声，请并行运行许多独立副本，然后组合其输出。

通常1比2更有趣。该算法的2实际上有点不合标准，但我只讲1。

假设我们正在处理输入

a b c a b a .

有了三个计数器，就无需哈希。

a: 3, b: 2, c: 1

但是，让我们假设我们只有一个。有八种可能的功能h : {a, b, c} -> {+1, -1}。这是结果表。

 h  |
abc |  X = counter
----+--------------
+++ | +3 +2 +1 =  6
++- | +3 +2 -1 =  4
+-- | +3 -2 -1 =  0
+-+ | +3 -2 +1 =  2
--+ | -3 -2 +1 = -4
--- | -3 -2 -1 = -6
-+- | -3 +2 -1 = -2
-++ | -3 +2 +1 =  0

现在我们可以计算期望值

            (6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0)
E[h(a) X] = ------------------------------------ = 24/8 = 3
                             8
            (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6)
E[h(b) X] = ------------------------------------ = 16/8 = 2
                             8
            (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2)
E[h(c) X] = ------------------------------------ =  8/8 = 1 .
                             8

这里发生了什么？对于a，例如，我们可以分解X = Y + Z，其中s Y的总和的变化是，as

Z的总和a的变化。通过期望的线性，我们有

E[h(a) X] = E[h(a) Y] + E[h(a) Z] .

E[h(a) Y]是具有用于每次出现的项的总和a就是h(a)^2 = 1，所以E[h(a) Y]是出现的次数a。其他项E[h(a)

Z]为零；即使给定h(a)，彼此的哈希值也同样可能为正负1，因此期望值为零。

实际上，哈希函数不需要是统一的随机数，这是件好事：没有办法存储它。哈希函数必须成对独立（两个特定的哈希值是独立的）就足够了。对于我们的简单示例，以下四个函数的随机选择就足够了。

abc
+++
+--
-+-
--+

我将把新的计算留给您。

以上是 解释计数草图算法 的全部内容， 来源链接： utcz.com/qa/419959.html

回到顶部