位掩码与布隆过滤器
Bitmasks vs bloom filters
我希望使用布隆过滤器或位掩码对搜索结果进行预过滤。举个具体的例子：
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）仅在一个字符？
- 是否有解决常见问题的建议方法 letters/words。例如，"a/an"、"the" 等似乎会出现在几乎所有具有自然文本的列中。
有关搜索要求的更多详细信息：
- 最大数据大小为 1GB。这将转换为 1M-10M 行之间的任何位置，具体取决于行的大小。
- 可用的额外空间非常非常少，所以像传统索引这样的东西是不可能的。作为参考，我们假设任何数据集都有 10% 的空间来存储辅助信息，例如 bitmask/filter/index/etc.
- 两个示例查询是
description like "%drink%"（完全内部搜索）或 description REGEXP '^|\sdrink'（"edge search"，在任何单词的开头搜索）。
如果不能容忍误报，则一定不要使用布隆过滤器，因为它是一种概率数据结构。
对于位掩码方法，显然，时间效率不高，而且该方法以后很难扩展。当您谈论大约 800 MB 的数据大小时，您正在进入 Search or Information Retrieval. The question now doesn't remain confined to 'Bitmasks vs Bloom Filters' Just have a read at the indexing related concepts in Search Engine Indexing 的范式，它们可能会对您有所帮助。
要解决常用词，请阅读stop words are and how to remove them. To go to a bit more next level, if you don't need to find the exact word, read about Stemming and Lemmatization。
这个问题很宽泛，所以我只是给出了一些阅读指南。希望你觉得它们有用。
您的位掩码是简单的布隆过滤器：假设您关心 26 个可能的字符，即带有 m = 26 * rowCount、k = 1 和以下哈希函数的 Bloom filter：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)。这样，它使用相同的 space，但位分布更均匀。对于频繁出现的字母，这会大大加快搜索速度，但代价是搜索不太频繁出现的字母会稍微慢一些。
更好的方法可能是合并多行，假设每行合并 8 行（行 0..7、8..15，...），然后设置布隆过滤器中需要的所有位.这样，您可以大大减少查找次数。
如果您的查询可以是 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`。所以你基本上检查某个字符对是否出现在某个行组中。这样，您甚至可以对 "like" 条件和正则表达式使用布隆过滤器。
我希望使用布隆过滤器或位掩码对搜索结果进行预过滤。举个具体的例子：
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）仅在一个字符？ - 是否有解决常见问题的建议方法 letters/words。例如，"a/an"、"the" 等似乎会出现在几乎所有具有自然文本的列中。
有关搜索要求的更多详细信息：
- 最大数据大小为 1GB。这将转换为 1M-10M 行之间的任何位置，具体取决于行的大小。
- 可用的额外空间非常非常少，所以像传统索引这样的东西是不可能的。作为参考，我们假设任何数据集都有 10% 的空间来存储辅助信息，例如 bitmask/filter/index/etc.
- 两个示例查询是
description like "%drink%"（完全内部搜索）或description REGEXP '^|\sdrink'（"edge search"，在任何单词的开头搜索）。
如果不能容忍误报，则一定不要使用布隆过滤器，因为它是一种概率数据结构。
对于位掩码方法，显然，时间效率不高，而且该方法以后很难扩展。当您谈论大约 800 MB 的数据大小时，您正在进入 Search or Information Retrieval. The question now doesn't remain confined to 'Bitmasks vs Bloom Filters' Just have a read at the indexing related concepts in Search Engine Indexing 的范式，它们可能会对您有所帮助。
要解决常用词，请阅读stop words are and how to remove them. To go to a bit more next level, if you don't need to find the exact word, read about Stemming and Lemmatization。
这个问题很宽泛，所以我只是给出了一些阅读指南。希望你觉得它们有用。
您的位掩码是简单的布隆过滤器：假设您关心 26 个可能的字符，即带有 m = 26 * rowCount、k = 1 和以下哈希函数的 Bloom filter：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)。这样，它使用相同的 space，但位分布更均匀。对于频繁出现的字母，这会大大加快搜索速度，但代价是搜索不太频繁出现的字母会稍微慢一些。
更好的方法可能是合并多行，假设每行合并 8 行（行 0..7、8..15，...），然后设置布隆过滤器中需要的所有位.这样，您可以大大减少查找次数。
如果您的查询可以是 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`。所以你基本上检查某个字符对是否出现在某个行组中。这样，您甚至可以对 "like" 条件和正则表达式使用布隆过滤器。