本书共6章。每章都专门针对大数据应用中的一个特定问题，首先对该问题进行深入的解释，然后介绍可用于有效解决该问题的数据结构和算法。
第1章简要概述了概率数据结构中广泛使用的散列函数和散列表。第2章专门介绍近似成员查询，这是概率数据结构最著名的用例之一。第3章讨论了用来辅助估算元素基数的概率数据结构。第4章和第5章讨论流式场景下与频数和排序相关的重要指标的计算。第6章包含用于解决相似性问题的数据结构和算法，尤其是近邻搜索问题。

本书重点介绍大数据概率数据结构与算法的核心思想和重要的应用领域

大数据特征可从三个基本维度来刻画，体量（volume）、速度（velocity）和多样性（variety），即大数据的三个v。其中，体量表示数据的总量，速度描述数据到达和被处理的速度，多样性指数据类型的个数。
数据无处不在，包括社交媒体、各种传感器、金融交易等。IBM曾声称人们每天创造的数据总量达2.5 EB（2.5 quintillion byte）。这一数字仍然在持续增长，而且大部分数据不能被存储，这些数据经常未经处理就被丢弃。现如今，需要处理TB或PB数量级的语料库以及千兆位速率的数据流的应用场景并不罕见。
另一方面，当下每个公司都想要完全理解所拥有的数据，以便发现其中的价值并做出相应决策。这导致了大数据软件市场的迅猛发展。然而，包含数据结构和算法在内的传统技术在处理大数据时是低效的。因此，许多软件从业人员不断地在计算机科学中寻找合适的解决方案。其中一种可选的解决方案就是使用概率数据结构和算法。
概率数据结构是一类主要基于不同散列技巧的数据结构的统称。不同于常规数据结构（又称确定性数据结构），概率数据结构总是提供近似的答案，但通过可靠的方式估计可能存在的误差。幸运的是，这些潜在的损失和误差可以被极低的内存需求、恒定的查询时间和良好的可扩展性充分弥补。这些因素在大数据应用中是至关重要的。
关于本书
本书面向技术从业人员，包括软件架构师、开发人员以及技术决策者，介绍概率数据结构和算法。通过阅读本书，你将能够对概率数据结构有理论和实践级别的了解，同时了解它们常见的使用场景。
本书不面向科学家，但是要想充分使用本书，你需要具备基本的数学知识，并且需要对数据结构和算法的一般理论有一定的了解。如果你没有任何“计算机科学”的经验，我们强烈推荐你阅读由Thomas H. Cormen，Charles E. Leiserson，Ronald L.Rivest和Clifford Stein（MIT）所撰写的《算法导论》，其中有对计算机算法现代研究的全面介绍。
本书虽然不可能涵盖当前所有的出色解决方案，但将重点介绍它们的共同思想和重要的应用领域，包括成员查询、基数估计、流挖掘和相似性估计。
全书组织结构
本书共6章。每章前面都有引言，后面都有一个简短的总结和参考文献，以供读者进一步阅读与该章有关的内容。每章都专门针对大数据应用中的一个特定问题，首先对该问题进行深入的解释，然后介绍可用于有效解决该问题的数据结构和算法。
第1章简要概述概率数据结构中广泛使用的散列函数和散列表。第2章专门介绍近似成员查询，这是概率数据结构最著名的用例之一。第3章讨论用来辅助估算元素基数的概率数据结构。第4章和第5章讨论流式场景下与频数和排序相关的重要指标的计算。第6章包含用于解决相似性问题的数据结构和算法，尤其是近邻搜索问题。
网络上的本书
你可以在https://pdsa.gakhov.com上找到本书的勘误、示例和其他信息。如果你对本书有任何评论与技术问题，想报告发现的错误或任何其他问题，请发送电子邮件至pdsa@gakhov.com。
如果你对本书中很多数据结构和算法的Cython实现感兴趣，请在https://github.com/gakhov/pdsa上查看我们的免费开放源代码Python库PDSA。欢迎大家随时做出贡献。
关于作者
Andrii Gakhov是一名数学家和软件工程师，拥有数学建模和数值方法方向的博士学位。他曾在乌克兰的哈尔科夫国立大学计算机科学学院任教多年，目前是Ferret go GmbH的软件从业人员，后者是德国领先的社区审核、自动化和分析公司。他的研究兴趣包括机器学习、流挖掘和数据分析。
与作者联系的最佳方式是通过推特账户@gakhov或访问他的个人主页https://www.gakhov.com。
致谢
感谢Asmir Mustafic、Jean Vancoppenolle和Eugen Martynov为审阅本书做出的贡献以及他们的有益建议。感谢学术评论家Kateryna Nesvit博士和Dharavath Ramesh博士的宝贵建议和意见。
特别感谢t-摘要算法的作者Ted Dunning。Ted Dunning对相应章节进行了精准的审阅，提出了有见地的问题和许多有益的意见。
最后，感谢所有提供反馈并帮助本书成功出版的各位。

计算机/大数据

在信息时代，经济和技术的发展催生了大数据。有效地对大数据进行处理则能进一步推动社会的发展。概率数据结构是解决大数据计算和存储问题的有效手段，被广泛应用于网络测量、数据库管理、人工智能模型优化等领域。本书重点介绍了典型的数据挖掘问题，并详细描述了相关的概率数据结构，对于科研人员和IT从业者了解概率数据结构具有重要的参考价值。
—— 西安交通大学 苏洲 教授

大数据以数据规模大、产生速度快、具有丰富的多样性等特点，为大数据的高效计算和存储提出了新的挑战。设计概率数据结构和算法来处理大数据是解决这些挑战的必然选择和研究热点。本书通俗易懂地对大数据概率数据结构和算法进行介绍，可以帮助入门研究者以及相关从业人员开拓视野，启发思路。
—— 北京理工大学 袁野 教授

概率数据结构是一类主要基于不同散列技术的数据结构的统称。与常规的（或确定性的）数据结构不同的是，概率数据结构总是提供近似的答案，但也提供了可靠的方法来估计可能产生的误差。幸运的是，这些潜在的损失和误差可以通过极低的内存需求、恒定的查询时间和可扩展性得到充分的补偿，而这些因素在大数据应用中十分重要。
本书不可能涵盖所有现有的出色解决方法，而是重点介绍它们的共同思想和重要的应用领域，包括成员查询、计数、流数据挖掘和相似度估计。阅读本书，你将
学会解决海量数据处理的实际问题
掌握概率数据结构的理论知识
为特定问题确定正确的数据结构
本书的目的是向包括软件架构师、开发人员以及技术决策者在内的技术从业者介绍概率数据结构与算法。通过阅读本书，你将对概率数据结构有理论和实践层面的理解，同时了解它们的常见用途。

随着信息技术与互联网技术的快速发展，因特网、社交网络、移动互联网、物联网等众多应用催生出了大规模的数据。针对大数据技术的国际竞争日趋激烈，面向大数据分析算法与系统软件的研究成为当前国内外学术前沿的热点。
面对大规模数据的分析，现实中常存在计算和存储的限制，导致无法完全对大数据进行准确计算。例如在面向计算机网络流量的测量分析中，海量高速的网络数据包和网络路由器有限的硬件资源之间的矛盾导致网络数据包难以实现全量实时的捕获和存储。网络路由器有限的硬件资源决定了其可缓存的网络数据包数量有限，面对主干网高速的网络流量，路由器处理每个数据包的时间非常有限。因而，针对每个数据包仅限于简单的运算和操作，否则会影响后续数据包的正常转发，导致出现网络丢包、网络拥塞等现象，从而造成网络性能的急剧下降。除此之外，大规模的网络流量数据也难以全量存储，40 Gbit/s网络链路满负荷运行每天产生的网络流量约为432 TB，实时存储和分析如此大规模的数据面临巨大的挑战和高昂的成本。因此，目前基于软件定义的网络路由器采用基于概率统计的近似估计方法来实现对网络流量态势的测量。
本书介绍的概率数据结构是针对大规模数据近似计算专门设计的。不同于常规确定性数据结构，概率数据结构总是提供近似的答案以及估计结果的误差范围。本书的作者Andrii Gakhov博士曾在哈尔科夫国立大学计算机科学学院任教多年，目前在产业界从事软件研发，具有丰富的产学研经验。本书详细介绍的概率数据结构和算法包括集合成员查询、集合基数计算、数据流频数统计、相似性快速查找等众多实际应用中面临的典型问题，并提供了相关的免费开放源代码Python库。本书涉及的基础知识与众多理工科大学生必修的课程“数据结构与算法”和“概率论”有关，因此本书可以作为相关课程的课外读物。同时，本书也为软件架构师、开发人员等技术从业人员提供了良好的理论和实践材料。

译者序
前言
第1章 散列1
1.1 加密散列函数2
1.2 非加密散列函数5
1.3 散列表7
1.4 总结13
本章参考文献13
第2章 成员查询15
2.1 布隆过滤器16
2.2 计数布隆过滤器24
2.3 商数过滤器27
2.4 布谷过滤器38
2.5 总结46
本章参考文献46
第3章 基数49
3.1 线性计数51
3.2 概率计数55
3.3 LogLog和HyperLogLog63
3.4 总结74
本章参考文献74
第4章 频数77
4.1 多数投票算法80
4.2 频繁算法82
4.3 Count Sketch86
4.4 CountMin Sketch96
4.5 总结105
本章参考文献105
第5章 排序107
5.1 随机采样109
5.2 q-摘要116
5.3 t-摘要125
5.4 总结135
本章参考文献136
第6章 相似性139
6.1 局部敏感散列149
6.2 MinHash153
6.3 SimHash165
6.4 总结174
本章参考文献174