Bounter -- 大型数据集计数器

Bounter 是一个用 C 语言编写的 Python 库，用于在大型数据集中进行极快的概率性计数。与 Counter 不同，它仅使用一个很小的固定内存占用。

为什么选择 Bounter？

Bounter 允许您计数项目出现的次数，类似于 Python 内置的 dict 或 Counter

from bounter import bounter

counts = bounter(size_mb=1024)  # use at most 1 GB of RAM
counts.update([u'a', 'few', u'words', u'a', u'few', u'times'])  # count item frequencies

print(counts[u'few'])  # query the counts
2

然而，与 dict 或 Counter 不同，Bounter 可以处理巨大的集合，其中项目甚至无法适应 RAM。这在机器学习和自然语言处理中很常见，例如在构建字典或进行搭配检测等任务中，需要估计数十亿个项（标记 n-gram）的计数，以进行统计评分和后续过滤。

Bounter通过使用优化的底层C结构实现近似算法，以避免Python对象的额外开销。它允许您指定想要使用的最大RAM量。在下面的维基百科示例中，与Counter相比，Bounter使用了31倍的内存。

Bounter也比内置的dict和Counter略微快一些，因此只要您可以将您的项目表示为字符串（既可以是字节字符串，也可以是unicode，Bounter在Python2和Python3中都能使用），就没有理由不使用Bounter，除非

何时不使用Bounter？

请注意，Bounter仅是一个概率频率计数器，不能保证精确计数。（您不能期望一个具有有限大小的数据结构能容纳无限数据。）Bounter失败的例子

from bounter import bounter
bounts = bounter(size_mb=1)
bounts.update(str(i) for i in range(10000000))
bounts['100']
0

当需要精确计数时，请使用Counter或dict。当它们不重要时，比如在大多数NLP和ML应用中，尤其是具有大量数据集的应用，Bounter是一个非常好的替代品。

安装

Bounter除了Python >= 2.7或Python >= 3.3和C编译器之外没有依赖项

pip install bounter  # install from PyPI

或者，如果您想从源码tar.gz安装

python setup.py test  # run unit tests
python setup.py install

它是如何工作的？

没有魔法，只是巧妙地使用近似算法和扎实的工程。

特别是，Bounter根据您所需的“计数”类型，在内部实现了三种不同的算法

1. 基数估计：“有多少个唯一项目？”

from bounter import bounter

counts = bounter(need_counts=False)
counts.update(['a', 'b', 'c', 'a', 'b'])

print(counts.cardinality())  # cardinality estimation
3
print(counts.total())  # efficiently accumulates counts across all items
5

这是最简单的用例，使用最少的内存，通过使用HyperLogLog算法（建立在Joshua Andersen的HLL代码之上）。

2. 项目频率：“这个项目出现了多少次？”

from bounter import bounter

counts = bounter(need_iteration=False, size_mb=200)
counts.update(['a', 'b', 'c', 'a', 'b'])
print(counts.total(), counts.cardinality())  # total and cardinality still work
(5L, 3L)

print(counts['a'])  # supports asking for counts of individual items
2

这使用Count-min Sketch算法来高效地估计项目计数，在固定数量的内存中。有关详细信息，请参阅API文档。

作为进一步优化的选项，Count-min Sketch支持对数概率计数器

• bounter(need_iteration=False)：默认选项。精确计数器，没有概率计数。每个桶占用4字节（最大值2^32）。
• bounter(need_iteration=False, log_counting=1024)：一个占用2字节的整数计数器。值高达2048是精确的；更大的值可能会偏离±2%。最大可表示的值约为2^71。
• bounter(need_iteration=False, log_counting=8)：一个更激进的概率计数器，只需1个字节即可容纳。值高达8是精确的，更大的值可能会偏离±30%。最大可表示的值约为2^33。

在NLP中，这种内存与准确度之间的权衡有时是可取的，在NLP中，能够处理非常大的集合比一个事件是否恰好发生55,482次或55,519次更重要。

3. 完整的项目迭代：“项目及其频率是什么？”

from bounter import bounter

counts = bounter(size_mb=200)  # default version, unless you specify need_items or need_counts
counts.update(['a', 'b', 'c', 'a', 'b'])
print(counts.total(), counts.cardinality())  # total and cardinality still work
(5L, 3)
print(counts['a'])  # individual item frequency still works
2

print(list(counts))  # iterator returns keys, just like Counter
[u'b', u'a', u'c']
print(list(counts.iteritems()))  # supports iterating over key-count pairs, etc.
[(u'b', 2L), (u'a', 2L), (u'c', 1L)]

除了总基数和个别项目频率（8字节）外，还存储键（字符串）。使用最多的内存，但支持最广泛的功能。

此选项使用底层的自定义C哈希表，具有优化的字符串存储。当接近最大分配内存时，它会移除低计数对象，而不是扩展表。

有关更多详细信息，请参阅API文档字符串或阅读博客。

在英语维基百科上的示例

让我们计算英语维基百科语料库中所有双词组的频率

with smart_open('wikipedia_tokens.txt.gz') as wiki:
    for line in wiki:
        words = line.decode().split()
        bigrams = zip(words, words[1:])
        counter.update(u' '.join(pair) for pair in bigrams)

print(counter[u'czech republic'])
42099

维基百科数据集包含7,661,318个不同的单词，总共有1,860,927,726个单词，以及179,413,989个不同的二元组，总共有1,857,420,106个二元组。将它们存储在简单的内置dict中会消耗超过31GB的RAM。

为了测试Bounter的准确性，我们自动从这些二元组计数中提取了搭配（常见的多词表达式，例如“纽约”、“网络许可证”、“最高法院”或“小学”）。

我们比较了从Counter（精确计数，需要大量内存）中提取的搭配集与Bounter（近似计数，内存有限）的搭配集，并在这里展示了精确度和召回率。

Bounter在内存减少了31倍（1GB vs 31GB）的情况下，与内置的Counter或dict相比，实现了完美的F1分数100%。它的速度也快了61%。

即使在只有128MB（减少了250倍内存）的情况下，其F1分数仍然是96.04%。

支持

使用Github issues来报告错误，并通过我们的邮件列表进行一般讨论和功能想法。

Bounter是在MIT许可证下发布的开源软件。

版权所有 (c) 2017 RaRe Technologies