嗨，habrozhiteli！ 算法是计算机科学的灵魂。 您无法没有它们，它们无处不在-从网络路由和基因组计算到密码学和机器学习。 “完美算法”将使您成为真正的专业人士，他们将在雇用任何IT公司时设定任务并在生活中和面试中熟练地解决任务。
在第二本书中，算法大师Tim Rafgarden讨论了图搜索及其应用，最短路径搜索算法以及某些数据结构的使用和实现：堆，搜索树，哈希表和Bloom过滤器。
这篇文章摘录自Bloom Filters：The Basics。
这本书是关于什么的
《 Perfect Algorithm》一书的第二部分是关于扫盲基础的入门课程，涉及以下三个主题。
图搜索和应用 。 图形为许多不同类型的网络建模，包括道路，通信，社交网络和任务之间的依存关系网络。 图可能很复杂，但是有一些令人难以置信的快速图元可以谈论图结构。 我们将从线性时间图搜索算法开始，从网络分析到构建一系列操作的应用开始。
最短的路径 。 在最短路径问题中，目标是计算网络中从点A到点B的最佳路由。此任务具有明显的应用，例如计算流量路由，并且在许多其他通用任务中也以变相的形式发生。 我们将概括我们的一种图搜索算法，并得出著名的Dijkstra最短路径搜索算法。
数据结构 。 本书将使您成为受过高等教育的用户，可以使用几种不同的数据结构，这些数据结构旨在支持一组不断发展的对象及其关联的键。 主要目标是就哪种数据结构适合您的应用程序开发一种直觉。 其他部分提供了从头开始实现这些数据结构的准则。
首先，我们讨论可以快速识别具有最小密钥的存储对象的堆，它们对于排序，实现优先级队列和实现Dijkstra的几乎线性时间算法也很有用。 搜索树可维护存储对象上键的完整顺序，并支持更大范围的操作。 哈希表针对超快速搜索操作进行了优化，并且在现代程序中得到了广泛应用。 我们还将查看Bloom过滤器，它是哈希表的近亲，由于随机错误而使用较少的空间。
您可以在“结论”部分中更详细地了解本书的内容，这些部分完成每一章并确定最重要的要点。 本书中标有星号的部分在所提供的信息水平方面是最先进的。 如果这本书是为使您对该主题有一个简单的了解而设计的，那么读者可以跳过它们而不会失去书面内容的完整性。
其他三个部分涵盖了主题 。 《完美算法》一书的第一部分。 基本原理“涵盖了渐近符号（O大和她的近亲符号），“分而治之”算法和主要递归关系定理-主要方法，随机快速排序及其分析以及线性时间选择算法。 第三部分涉及贪婪算法（规划，最小生成树，聚类，霍夫曼代码）和动态编程（背包问题，序列比对，最短路径，最佳搜索树）。 第四部分专门讨论NP完整性，这对算法设计者意味着什么，以及解决计算上不可解决的问题的策略，包括启发式分析和局部搜索。
12.5。 布隆过滤器：基础知识
布隆过滤器是哈希表的近亲。 它们非常紧凑，但是会定期出错。 本节介绍Bloom过滤器的性能以及如何实现，而第12.6节列出了过滤器使用的空间量及其错误率之间的折衷曲线。
12.5.1。 支持的运营
存在Bloom过滤器的原因与哈希表的原因基本相同：超快的插入和查看操作，借助这些操作，您可以快速记住看到的内容和没有看到的内容。 为什么我们要为具有相同操作集的不同数据结构所困扰？ 因为布隆过滤器比哈希表更适合应用程序，在这些应用程序中，空间应占黄金的重量，并且随机错误不会成为交易的障碍。
像具有开放式寻址的哈希表一样，布隆过滤器仅支持插入和查看操作（而没有删除操作），因此易于实现和构想。 我们将专注于这种情况。
布隆滤镜：支持的操作
查看：使用键k，如果k先前已插入布隆过滤器中，则返回“是”，否则返回“否”。
粘贴：将新的密钥k添加到Bloom过滤器。
布隆过滤器在空间上非常有效； 通常，每个插入可能只需要8位。 这真是令人难以置信，因为8位甚至不足以记住32位键或指向对象的指针！ 因此，Bloom过滤器中的View操作仅返回答案“是” /“否”，而在哈希表中，该操作返回指向所需对象的指针（如果找到）。 因此，Insert操作现在仅接受键，而不接受对象的（指针）。
与我们研究的所有其他数据结构不同，布隆过滤器可能是错误的。 错误有两种类型：错误的否定（即使先前已插入请求的键时，查看操作返回“ false”）和错误的陈述（或肯定的）（即使过去尚未插入请求的键时，则返回false）。 。 在第12.5.3节中，我们将看到基本的Bloom过滤器永远不会遭受假否定的影响，但是它们可以具有以假声明形式出现的“幻像元素”。 第12.6节表明，可以通过适当地调整空间的使用来控制虚假声明的发生频率。 布隆滤波器的典型实现可能具有约1％或0.1％的错误率。
插入和查看操作的执行时间与哈希表中的执行时间一样快。 甚至更好的是，无论布隆过滤器和数据集1的实现如何，这些操作都可以保证在恒定时间内执行。 但是，实现和数据集会影响滤波器的错误率。
总结Bloom过滤器相对于哈希表的优点和缺点：
反对哈希表的花朵过滤器
1.优点：在空间上更有效。
2.优点：保证每个数据集的永久性操作。
3.缺点：无法存储指向对象的指针。
4.缺点：与带有离合器的哈希表相比，删除操作更为复杂。
5.缺点：错误陈述的非零概率。
基本Bloom过滤器的指标列表如下。
表12.4。 基本Bloom过滤器：支持的操作及其执行时间。 匕首符号（†）表示查看操作具有可控但不为零的虚假声明概率
在应用程序中使用Bloom筛选器代替哈希表时，应优先考虑它们的优点，而缺点则不会阻碍事务处理。
使用花絮滤镜时
如果应用程序需要使用动态演化的对象集进行快速搜索，则其价值不菲，而且可以接受的错误声明数量也很少，那么Bloom过滤器通常是首选的数据结构。
12.5.2。 应用领域
接下来，重复扫描有三种用途，节省空间可能很重要，而虚假陈述也不是交易的障碍。
拼写检查器。 早在1970年代，Bloom过滤器用于实现拼写检查器-拼写检查器。 在预处理阶段，字典中的每个单词都将插入到Bloom过滤器中。 文档的拼写归结为一个操作，请查看文档中的单词，并标记此操作返回“ no”的所有单词。
在此附录中，错误的陈述对应于拼写检查器无意接受的无效单词。 这样的错误使拼写检查器不理想。 但是，在1970年代初，太空是值得的，因此，使用Bloom过滤器是双赢的策略。
禁止使用密码 。 至今仍有效的旧应用程序会跟踪禁止的密码-太常见或太容易猜到的密码。 最初，所有禁止的密码都插入到Bloom筛选器中； 以后可以根据需要插入其他禁止的密码。 当用户尝试设置或重置其密码时，系统会在Bloom过滤器中搜索建议的密码。 如果搜索返回“是”，则提示用户使用其他密码再次尝试。 在这里，一个错误的陈述被翻译成一个强密码，系统拒绝该密码。
假设错误率不太高，例如不超过1％或0.1％，那么这无关紧要。 有时，某些用户将需要进行另一种尝试来查找系统可接受的密码。
互联网路由器 。 如今，Bloom过滤器的许多惊人应用都发生在Internet的深处，在那里数据包以流速通过路由器。 路由器可能想快速回忆起过去所见的原因有很多。 例如，路由器可能希望在阻止的IP地址列表中找到数据包的源IP地址，跟踪高速缓存的内容，以避免出现虚假的高速缓存视图，或者保留有助于识别拒绝服务网络攻击的统计信息。 数据包的到达速度需要超快的视图，而路由器的有限内存使其价值不菲。 这些应用程序由Bloom Filter直接管理。
12.5.3。 实作
在Bloom过滤器内部，您可以看到一个优雅的实现。 数据结构支持一个n位字符串或长度为n的数组A，其中每个元素为0或1。（所有元素均初始化为零。）此结构还使用m个哈希函数h1，h2，...，hm ，而每个都将所有可能键的Universe U映射到数组中位置的集合{0，1，2，...，n-1}。 参数m与Bloom过滤器用于插入的位数成正比，并且通常是一个小的常数（例如5）。
每当将密钥插入到布隆过滤器中时，m个哈希函数中的每一个都会设置一个标志，将数组A的对应位设置为1。
布隆滤镜：插入（按键）
for i = 1 to m do A[hi(k)] := 1
例如，如果m = 3且h1（k）= 23，h2（k）= 17和h3（k）= 5，则插入k会使数组的第5位，第17位和第23位设置为相等1（图12.5）。
在“查看”操作中，布隆过滤器搜索可能保留在插入k上的指纹。
布隆滤镜：查看（关键）
for i = 1 to m do if A [hi (k)] = 0 then return «» return «»
现在我们可以看到为什么Bloom过滤器不会遭受假阴性。 当插入密钥k时，相应的m位被设置为1。在Bloom过滤器的生命周期内，这些位可以将其值从0更改为1，反之亦然。 因此，这m个比特永远保持1。 确保随后的每个View k操作都返回正确的yes答案。
我们还可以看到错误陈述是如何产生的。 假设m = 3，并且四个键k1，k2，k3，k4具有以下哈希值：
假设我们将k1，k2，k3和k4插入布隆过滤器中（图12.6）。 这三个插入导致将总共9位设置为1，其中包括密钥k1的指纹中的3位（5、17和23）。 此时，布隆过滤器无法再区分是否插入了密钥k1。 即使未将k1插入过滤器，搜索也将返回“是”，这是一个错误的语句。
凭直觉，我们可以假设，随着Bloom过滤器的大小n的增加，不同键的指纹之间的重叠数应该减少，从而导致更少的错误陈述。 但是，布隆过滤器的主要目标是节省空间。 是否有中间立场，使n和错误陈述的发生率同时变小？ 答案并不明显，需要在下一部分进行一些数学分析。
»这本书的更多信息可以
在出版商的网站上找到»
目录»
摘录对于Khabrozhiteley优惠券20％的折扣-
算法支付纸质版本的书后，就会通过电子邮件发送电子书。