基于C语言的布隆过滤器的实现和应用_一单项选择题(共26题) 1 在visual studionet的集成开发的环境中

完整资料进入【数字空间】查看——搜索"writebug"

第一章 理论基础
1.1 课题背景
在学习和工作中，时常需要使用到文本编辑器进行文档或者代码的编写。而文档和代码的编写中，常常会出现类似”true”和”ture”，”main”和”mian”等等的混淆，在程序排查错误和文档阅读中，造成不小的麻烦。因此，常用的文本编辑器例如Microsoft Word，Microsoft Visual Studio Code，Code::block等等通常都会附带有拼写检查和关键词高亮的功能。其原理是，通过引入默认的词典，记录该词典中的所有字符串，和当前文档进行比对，从而发现错误的代词或者代码关键字，并且采用下划线，文本高亮等形式来提醒用户。甚至于在用户输入某个关键词的前几个字符时，自动提示补全关键字。

然而，如果直接记录词典中的所有字符串并且用以遍历比对，会极大程度地加大空间和时间的复杂度。因此，在拼写检查器 UNIXspell-checkers 中，就采用了布隆过滤器（Bloom Filter, BF）数据结构的哈希表来判断某个字符串是否存在于词典中。

因此，本课程设计将使用 Qt 来设计文本编辑器，并建立以布隆过滤器作为词典存储的数据结构，以此实现拼写检查的功能。同时，该软件将支持添加关键字功能，以满足用户多变的需求。

本文将以如下顺序进行阐述：第一章将介绍该课程设计的理论基础，包括数据存储结构原理，程序设计框架等，第二章将介绍该课程设计的程序细节以及效果展示，第三章则将讨论和分析本次试验结果。

1.2 布隆过滤器
布隆过滤器是在1970年被巴顿布隆提出的，用来解决数据存储问题的哈希表。它将数据的存储形式由诸多字符串组成的数组，变为一个二进制向量序列，极大减小了检索和存储的难度。哈希表又称为散列表，是实现字典操作的一种有效数据结构。尽管在最坏情况下，散列表中查找一个元素的时间与在链表中查找的时间相同，达到了Θ(n)。然而在实际应用中，散列表查找的性能是极好的。在一些合理的假设下，在散列表中查找一个元素的平均时间是O(1)。

布隆过滤器的原理如下：初始化一个 n 字节二进制向量 Array 全部置为 0，对于每个希望存储的字符串 str1，通过 x 个哈希函数（又称散列函数）获取取值在[0, n)的哈希值序列 H，然后依次将 Array 中的第 Hi 个字节置为 1，则完成了对该字符串 str1 的存储。因此，同样地，对于希望检索的字符串 str2，通过相同的哈希函数获取得到哈希值序列 H’，显然，当该序列已被存储时，该哈希值序列在 Array 中对应的每一个字节都应该为 1。图 1.1 展示了该结构的原理。

​