我希望使用布隆过滤器或位掩码对搜索结果进行预过滤。举个具体的例子:
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在任何单词的开头)。
最佳答案
如果您不能容忍误报,则一定不要使用布隆过滤器,因为它是一种概率数据结构。
对于位掩码方法,显然,时间效率不高,而且该方法以后很难扩展。当您谈论大约 800 MB 的数据大小时,您正在进入 Search or Information Retrieval 的范例。 .现在的问题不再局限于“位掩码与布隆过滤器”,只需阅读 Search Engine Indexing 中与索引相关的概念即可。 ,他们可能会帮助你。
要解决常用词,请阅读 stop words是以及如何删除它们。要更进一步,如果您不需要找到确切的词,请阅读 Stemming和 Lemmatization .
这个问题很宽泛,所以我只是给出了一些阅读建议。希望您觉得它们有用。
关于algorithm - 位掩码与布隆过滤器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57667704/