代写VC++布隆过滤器程序软件、代写代作程序

日期：2018-08-15 03:49

题目：布隆过滤器的实现和使用

（1）问题描述

    布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。假定需要存储一亿个电子邮件地址，首先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，可以用八个不同的散列函数（H1,H2,...,H8）产生八个从 1 到十六亿之间中的八个自然数 g1,g2,...,g8。然后将这八个自然数对应的八个位置的二进制全部设置为一。同样的方法对这一亿个 email 地址都进行处理后，一个针对这些 email 地址的布隆过滤器就建成了。如图所示：

现在看看如何用布隆过滤器来实现一个电子邮件地址过滤器，首先将那些放在黑名单上的电子邮件地址放在布隆过滤器中。当检测一个可疑的电子邮件地址Y 是否在黑名单中，仍用相同的八个随机数产生器（H1,H2,...,H8）对这个邮件地址产生八个自然数s1,s2,...,s8，这八个自然数对应的八个二进制位分别是t1,t2,...,t8。如果 Y 在黑名单中，显然， t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，都能准确地发现。

   布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。但这种可能性很小，此处将它称为误识概率。在上面的例子中，误识概率在万分

之一以下。

   因此布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

（2）课程设计目的

   学习 BloomFilter 结构，能应用该结构解决一些实际问题。

（3）基本要求

   ①定义 BloomFilter 结构的 ADT，该 ADT 应支持在 BloomFilter 中加入一个新的数据，查询数据是否在此过滤器中，并完成该结构的设计和实现。

   ②应用 BloomFilter 结构拼写检查，许多人都对 Word 的拼写检查功能非常了解，当用户拼错一个单词的时候， Word 会自动将这个单词用红线标注出来。 Word的具体工作原理不得而知，但另一个拼写检查器 UNIXspell-checkers 这个软件中就用到了 BloomFilter。 UNIXspell-checkers 将所有的字典单词存成 BloomFilter数据结构，而后直接在 BloomFilter 上进行查询。本课程设计要求针对 C 语言设计和实现上述拼写检查器，即当写了一个正确的关键词，如 int 时，给该词标上颜色，如蓝色。

   ③针对上述 C 语言关键词拼写检查器进行分析，如错误分析，设计散列函数个数分析，运行时间复杂性、空间复杂性的分析。

   ④上述 C 语言关键词拼写检查器最好是在 VC++或 Java 等可视化开发环境下实现。

   ⑤上述 C 语言关键词拼写检查器最好能支持所有的 C++关键词。

（4） 实现提示

BloomFilter 结构中的散列函数（包括散列函数的个数和散列函数的设计）是本题目中需要深入思考的一个环节。