位掩码与布隆过滤器
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), with
rowGroup = 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), with
rowGroup = rowId / 8`。所以你基本上检查某个字符对是否出现在某个行组中。这样,您甚至可以对 "like" 条件和正则表达式使用布隆过滤器。