我希望使用布隆过滤器或位掩码预先过滤搜索结果。举个具体的例子：
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"
如果用户搜索"可乐"一词，我们将在product="coke"上匹配 row1 和description(has word)="coke".
我们有内存限制，因此不能索引太多项目，但我正在考虑根据每行包含的第一个字母实现位掩码。这样，我们可以看到c包含在第 1 行和第 2 行中，但不在第 3 行中，因此我们根本不会在搜索中包含它。
如果我们取前三行，"单词开头"掩码看起来像(对于字母表的前 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。这将转换为 1M-10M 行之间的任何行，具体取决于行的大小。
- 可用的额外空间非常非常少，因此像传统索引这样的东西是不可能的。作为参考，假设任何数据集都有 10% 的余量来存储辅助信息，例如位掩码/过滤器/索引/等。
- 两个示例查询是
description like "%drink%"(完整的内部搜索(或description REGEXP '^|sdrink'("边缘搜索"，在任何单词的开头搜索(。
如果不能容忍误报，则不得使用布隆过滤器，因为它是概率数据结构。
显然，对于位掩码方法来说，时间效率不高，以后很难扩展该方法。当您谈论大约 800 MB 的数据大小时，您正在进入搜索或信息检索的范式。现在的问题不仅限于"位掩码与布隆过滤器"，只需阅读搜索引擎索引中的索引相关概念，它们可能会对您有所帮助。
要解决常用词，请阅读什么是停用词以及如何删除它们。要进入更深的级别，如果您不需要找到确切的单词，请阅读词干提取和词形还原。
这个问题相当广泛，所以我只是给出了一些阅读的指示。希望您发现它们有用。
您的位掩码很简单 布隆过滤器：假设您关心 26 个可能的字符，那就是具有m = 26 * rowCount、k = 1和以下哈希函数的布隆过滤器：hash(firstLetter, rowId) = (firstLetter * rowCount + rowId)。这很容易实现，但可能效率不高，因为有些字母经常出现(例如字符"e"(。您的位掩码每行需要大约 4 个字节，这可能没问题。对于每一行，您执行布隆筛选器查找。
最好使用更复杂的布隆过滤器。它的外观完全取决于您拥有的数据。假设您使用m = 26 * rowCount、k = 1和hash(firstLetter, secondLetter, rowId) = ((11 * firstLetter + 113 * secondLetter) modulo 26) * rowCount + rowId)。这样，它使用相同的空间，但位分布更均匀。对于频繁的信件，这大大加快了搜索速度，但代价是搜索频率较低的字母的速度稍慢。
更好的可能是合并多行，假设每行合并 8 行(第 0..7、8..15,... 行(，然后在 Bloom 过滤器中设置所需的所有位。这样，您可以大大减少查找次数。
如果您的查询可以是like "%drink%"的形式，则仅查看第一个字符的过滤器没有用：您仍然必须进行完全扫描。相反，你可以有一个 Bloom 过滤器，它组合(比如(8 行，并设置每个字符对的所有位。也就是说，['dr', 'ri', 'in', 'nk']，并使用m = 26 * rowCount / 8、k = 1和hash(firstLetter, secondLetter, rowGroup) = ((11 * firstLetter + 113 * secondLetter) modulo 26) * rowCount / 8 + rowGroup), withrowGroup = rowId/8'。因此，您基本上检查字符对是否出现在某个行组中。这样，您甚至可以将布隆过滤器用于"喜欢"条件和正则表达式。