前言

大数据特征可从三个基本维度来刻画，体量（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对相应章节进行了精准的审阅，提出了有见地的问题和许多有益的意见。

最后，感谢所有提供反馈并帮助本书成功出版的各位。