当字符串相似时,布隆过滤器发生冲突的可能性更高

数据挖掘 相似 散列
2021-09-29 12:35:02

因为如果是这样的话,这真的很适合我的需要。

我正在尝试发现网站上的热门搜索。为此,我使用了基于 Bloom Filter 散列的 TopK 算法。

我不希望“Hello world”和“hello world”被计算两次。因此,如果是碰撞,那将非常适合我的用例。

实际上,我正在使用这个实现

实际上,我可以在添加到 TopK 存储桶之前运行字符串相似性,就像对于任何新的字符串项目一样,如果它与存储桶中的至少一个字符串相似,则在添加之前将其转换为存储桶中的一个。但这将堆叠相同的逻辑(以防它可以直接使用 Bloom 过滤器实现)。

1个回答

它取决于散列函数,但通常不会,因为标准散列函数旨在避免相似的对象具有相似的散列码。[编辑,见评论]

对于您的用例,您可能应该使用自定义哈希函数,这使得两个字符串更有可能具有相同的代码。字符串中的字符或字符二元组的一次性编码可能会起作用。