algorithm - 位掩码与布隆过滤器

Question

我希望使用布隆过滤器或位掩码对搜索结果进行预过滤。举个具体的例子:

id,product,description
1,"coke", "A popular soft drink since 1900"
2,"pepsi", "A popular soda, similar to coke"
3,"soda", "A word to describe various soft drinks"

如果用户搜索单词“coke”，我们将在 product="coke" 上匹配第 1 行和 description(has word)="coke"。

我们有内存限制，所以不能索引太多项目，但我正在考虑根据每行包含的第一个字母实现位掩码。这样，我们可以看到 c 包含在第 1 行和第 2 行中，但不包含在第 3 行中，因此我们根本不会将其包含在我们的搜索中。

如果我们取前三行，“word-starts-with”掩码看起来像(字母表的前 3 个字母)--

a  b  c  d
1  0  1  1 (row 1 -- coke)  -- has c? Y
1  0  1  0 (row 2 -- pepsi) -- has c? Y
1  0  0  1 (row 3 -- soda)  -- has c? NO -- SKIP

那么我的问题有两个方面:

• 对于上述场景，使用布隆过滤器优于位掩码是否有任何优势？为什么或者为什么不？ (我不太熟悉布隆过滤器，我自己也从未使用过)。
• 上面的单字母位掩码是否看起来很有用，或者看起来它并不能真正解决任何问题(例如，每一行都可以有 a=1) -仅限字符？
• 是否有解决常见字母/单词的建议方法。例如，“a/an”、“the”等似乎会出现在几乎所有具有自然文本的列中。

---

有关搜索要求的更多详细信息:

• 最大数据大小为 1GB。这将转化为 100 万到 1000 万行之间的任何位置，具体取决于行的大小。
• 可用的额外空间非常非常少，所以像传统索引这样的东西是不可能的。作为引用，我们假设任何数据集都有 10% 的空间来存储辅助信息，例如位掩码/过滤器/索引/等。
• 两个示例查询是description like "%drink%"(完全内部搜索)或description REGEXP '^|\sdrink'(“edge search”，search在任何单词的开头)。

Answer 1

如果您不能容忍误报，则一定不要使用布隆过滤器，因为它是一种概率数据结构。

对于位掩码方法，显然，时间效率不高，而且该方法以后很难扩展。当您谈论大约 800 MB 的数据大小时，您正在进入 Search or Information Retrieval 的范例。 .现在的问题不再局限于“位掩码与布隆过滤器”，只需阅读 Search Engine Indexing 中与索引相关的概念即可。 ，他们可能会帮助你。

要解决常用词，请阅读 stop words是以及如何删除它们。要更进一步，如果您不需要找到确切的词，请阅读 Stemming和 Lemmatization .

这个问题很宽泛，所以我只是给出了一些阅读建议。希望您觉得它们有用。