使用Bloom Filters编写全文搜索引擎

几分钟前，我看到了一篇黑客新闻帖子，其中详细介绍了一种将搜索添加到静态站点的方法。您可能知道，将搜索添加到静态站点有点棘手，因为您不能只将查询发送到服务器，然后让服务器处理它并返回结果。如果您想要全文搜索，则必须实现类似于倒排索引的功能。

倒排索引是一种数据结构，它基本上将每个文档中的每个单词映射到它所在的文档的ID。例如，这样的索引可能类似于{"；python"；：[1，3，6]，"；raspberry"；：[3，7，19]}。要查找同时提到“python”和“raspberry”的文档，您可以在索引中查找这些术语，并找到共同的文档ID(在我们的示例中，这只是ID为3的文档)。

但是，当您有非常长的文档，其中包含不同的单词时，这可能会增长很多。它是一个庞大的数据结构，当您想要实现客户端搜索引擎时，您传输的每个字节都很重要。

客户端搜索引擎的问题在于，您(显然)必须在客户端执行所有搜索，因此您必须将所有可用的信息传输到客户端。静态站点生成器所做的是在生成站点时生成每个所需的文件，然后使这些文件可供客户端下载。通常，搜索引擎插件仅限于标签和标题，以减少需要传输的信息量。我们怎样才能缩小尺寸呢？轻松使用Bloom Filter！

Bloom filter是一种非常有趣的数据结构，它可以以固定位数存储元素，并在查询之前告诉您是否看到这些元素。对于我们的用例来说，这听起来很棒，但让我们看看它是否能胜任挑战。

实现使用Bloom过滤器的全文搜索引擎的简单方法如下：

为每个文档创建一个筛选器，并将该文档中的所有单词添加到筛选器中。

将(固定大小)过滤器序列化为某种字符串，并将其发送到客户端。

当客户端需要搜索时，遍历所有筛选器，查找与所有术语匹配的筛选器，并返回文档名称。

接下来，我们将使用我最喜欢的语言Python，使用pybloom非常快速地实现这一点。

首先，让我们阅读本博客中的一些帖子，并创建每个帖子中所有单词的列表：

从pybloom导入BloomFilter导入os导入重新#阅读我所有的帖子。POST={POST_NAME：OPEN(POST_DIR+POST_NAME)。操作系统中POST_NAME的Read()。listdir(Post_DIR)}#创建{"；帖子名称"；："；小写单词集"；}的字典。Split_Posts={名称：设置(重新。拆分("；\W+&34；，目录。较低的())为名称，帖子中的内容。项目()}。

在这一点上，我们有一本帖子词典，每个帖子中都有一组规范化的单词。我们可以做更多的事情，比如消除词干、删除常用词(a、the等)，但是我们太天真了，所以我们现在只创建过滤器：

FILTERS={}表示名称，SPLIT_POSTS中的单词。Items()：Filters[name]=BloomFilter(Capacity=len(Words)，Error_Rate=0.1)for Words in Words：Filters[Name]。添加(单词)。

您可以在上面看到，每个过滤器的容量正好是每个帖子中的字数，以减少表示它所需的位数。错误率是可以调整的，它是假阳性的概率。概率越低，过滤器越精确，但过滤时间越长。

现在我们已经准备好了所有的过滤器，我们可以使用任何我们喜欢的序列化方法将它们传输到客户端。让我们编写一个非常简单的搜索算法，根据一些搜索词查找帖子：

def search(Search_String)：search_term=re。Split("；\W+"；，search_string)返回[Name for Name，Filter in Filters。Items()if All(Search_Terms中的术语筛选器中的术语)]。

search()所做的全部工作就是遍历所有过滤器，并返回与每个给定词语匹配的过滤器。让我们试试看：

从标题来看，它找到了所有相关帖子，没有任何误报！一点也不差，只干了几分钟！让我们看看过滤器的平均大小是多少：

对于这样的事情，我觉得每个帖子298个字节是相当合理的大小。如果我们不介意更多的误报，我们可以进一步降低这一点，但是，考虑到上面的搜索结果，我认为对于这样一种天真的方法来说，这是相当好的。作为比较，本段也有298字节长。

另一种方法是使用单个过滤器，将帖子ID与搜索词(例如“3：Term”)连接起来，然后进行搜索。不幸的是，这会导致过滤器的大小与小的过滤器的大小完全相同，并且计算复杂度更高，因为您必须散列N次(其中N是帖子的数量)，而不是只散列一次。

使用Bloom过滤器有几个优点，使其适合在静态站点中使用：

它占用的空间与页数成正比，而不是与字数成正比，因此对于非常长的页面和对于非常短的页面，它占用的空间大致相同(这并不完全正确，因为我们根据字数调整筛选器的大小，但它比倒排索引紧凑得多)。

搜索复杂度与页面数量成正比，而不是与它们的长度成正比。当您最多只有几千页时，这并不重要，但如果您只有几页长的页，这仍然是很好的。

由于Bloom过滤器是概率的，这种方法可能会产生误报，但它不会产生漏报，这正是我们想要的搜索引擎(我们不介意搜索结果中有几个不相关的页面，但是如果缺少相关的页面，我们就会介意)。

你不能根据相关性对页面进行加权，因为你不知道一个单词在一个页面中出现了多少次，你只知道它是否出现。你可能会也可能不会关心这件事。

您需要在客户端实现Bloom Filter算法。这可能不会比倒排索引搜索算法长多少，但仍然可能稍微复杂一些。

当然，全文索引仍然很大，可能不适合加载到每个页面视图上，即使在使用这种方法时也是如此，但是这种方法可能适合在静态站点中的专用“搜索”页面中使用。

实际上，我并不提倡在你的静态站点上使用这种方法，但是，嘿，它让周六晚上的黑客攻击变得有趣了一个小时。现在，我们该出去喝一杯了。如果你在塞萨洛尼基，想要加入我，给我发一封电子邮件，或者让我上推特。