algorithm - 使用布隆过滤器查找文档中单词出现的可能性

Question

我有一个单词列表，比如-list1=[男孩，苹果，芒果，汽车]，我有两个文档，内容如下：

document1= The boy driving a car ate apple and mango.
document2= The boy ate an apple.

我只需要知道文档中是否存在给定的单词列表。
为了检查文档中是否存在List1中的单词，我可以为List1（Bloom List1）和Bloom过滤器创建Dopunt1（例如Bloom DoMeTun1）。然后我可以执行按位和运算，并检查结果是否与bloomlist1相同如果它是相同的，我可以说List1中的所有单词都存在于文档1中。所以，它会回到现实。
如果我对document2执行相同的方法，即按位进行运算，则结果将为false。但是，即使文档中包含了列表中的一个单词，我也需要得到正确的结果。
这是否可能与布鲁姆过滤器或我需要任何其他数据结构如果不是，那么什么是同时满足这两个条件的最佳数据结构。

Answer 1

我认为你使用布卢姆过滤器是不合适的。
你说两个过滤器需要
被构造，一个用于单词列表，另一个用于正在搜索的文档。那么你
按位和过滤器。如果结果与原始单词列表相同，则筛选
文档已被接受，否则您将拒绝它。
如果这是对流程的正确理解，那么很明显文档只能通过
如果它包含了列表中的所有单词（或者通过哈希冲突，有一些额外的位是
在文档Bloom筛选器中设置，这可能导致其接受-可能导致误报）。
如果要在列表中的一个单词匹配后立即选择文档，则只需要为单词列表使用一个Bloom筛选器（对于正在测试的文档则不需要）使用Bloom filter散列函数逐个散列文档中的每个单词一旦生成的哈希值与word list bloom过滤器中的所有对应位匹配，就接受文档（这是一次成功的尝试）。然后你需要确认袭击没有到期
假阳性。
布卢姆过滤器的“美”在于它不受假阴性的影响。也就是说，如果
文档中的单词在bloom过滤器中有一个“hit”，您可以百分之百确定
文档中的单词出现在关联的单词列表中。
你面临的一个问题是bloom过滤器容易出错
积极的。误报是指在bloom过滤器上找到一个不在关联列表中的单词。
因此，你必须
每当Bloom过滤器指示“命中”时，使用实际单词列表显式地验证每个命中的“真实性”。
这是不可能的。
构造一个好的bloom过滤器的“艺术”是找到一组哈希函数
执行并导致较低的假阳性命中率（通常这相当于
散列函数）快速开启
Bloom过滤器将为您提供大量关于散列函数数量和过滤器大小的指导
需要达到给定的假阳性率（假设哈希函数良好）。
如果你做了计算，你会发现对于任何重要大小的单词列表，你都需要在
至少7个哈希函数以达到可接受的假阳性率。对每个
不管你怎么做，一个大文档中的单词都会变得“昂贵”此外，如果你的文件
包含大量不同的单词在Bloom过滤器上遭受假阳性点击的可能性
可能变得很重要-降低了它的有用性。
这里的其他答案表明，更好的方法是为列表中的单词构造一个简单的哈希表，然后对每个单词进行哈希
从文档中查看它是否在列表中有命中项。如果是，请选择文档很简单。这种技术
最有可能对这种类型的应用程序执行Bloom filter方法，除非
你的问题中没有概述非常特殊的情况。
编辑-什么是最好的方法？
有很多方法可以对给定的文本进行多字符串搜索。它是
很难说哪一个是您的应用程序的最佳解决方案，因为大多数算法和
它们的实现对复杂的因素（如平均字长、
不同的单词、文档大小、搜索列表中的单词数、可用内存、命中概率等）这里没有一个正确的答案。
使用Bloom过滤器可能是一个非常合理的方法，但是，您至少应该看看
其他选择。举几个例子：
google search这对于中等大小的单词列表非常有效。
Suffix Trees用于多字符串匹配
Compact encoding schemes也可以非常有效
而且，如果你能做一些简化的假设，比如要匹配的模式具有相同的长度，那么Hybrid algorithms combining Bloom filters plus a Suffix Tree之类的东西可能会很有用
归根结底，在决定任何具体的解决方案之前，你应该考虑更广泛的策略。