Bloom过滤器闪耀的经典例子是连字符算法。它甚至是关于Bloom过滤器的原始论文中给出的例子。
我不明白在断字算法中如何使用Bloom过滤器。
断字算法被定义为接受输入单词并返回该单词断字的可能方式。
Bloom过滤器是否同时包含hyph-enation和hyphena-tion，并且客户端代码将向过滤器查询h-yphenation、hy-phenation、hyp-henation。。。？
原纸上写着：
断字样本应用程序分析
[…]让我们假设大约有500000个单词要由程序连字符，其中450000个单词可以通过应用一些简单规则进行连字符。另外50000个单词需要查字典。合理地估计，使用传统的散列编码方法来表示这50000个字中的每一个字平均需要至少19个比特。如果我们假设T＝4的时间因子是可接受的，则我们从等式(9(中发现哈希区域的大小将是2000000比特。对于实际的包含核心的哈希区域来说，这可能太大了。通过使用具有例如P=1/16的允许错误频率的方法2，并且通过具有T=2来使用最小的可能散列区域，我们从等式(22(中看出，该问题可以用小于300000比特的散列区域来解决，该大小很可能适合于核心散列区域。如果选择1/16的P，则需要访问驻留在磁盘上的字典，以便在500000个要连字符的单词中访问大约50000+450000/16~78000个单词，即大约16%的情况。这使得使用完全驻留在磁盘上的散列区和字典的典型传统方法所需的磁盘访问次数减少了84%。
对于这种情况，
- 字典存储在磁盘上，包含所有具有正确连字符的单词
- Bloom过滤器仅包含需要特殊连字符的密钥(例如可能
hyphenation本身( - Bloom过滤器以"可能"或"否"进行响应
然后找到单词可能的连字符的算法是：
word = "hyphenation"; (or some other word)
x = bloomFilter.probablyContains(word);
if (x == "probably") {
lookupInDictionary(word).getHypenation();
} else {
// x == "no" case
useSimpleRuleBasedHypenation(word);
}
如果Bloom过滤器的响应是"可能"，那么算法将不得不在字典中进行磁盘读取。
如果事实上没有特殊规则，Bloom过滤器有时会以"可能"作为响应，在这种情况下，磁盘I/O是不必要的。但这没关系，只要这种情况不经常发生(假阳性率很低，例如1/16(。
Bloom过滤器，因为它没有假阴性，对于有特殊连字符的情况，它永远不会以"否"回应。