Bloom filtresi ve trie

Kısaca: Bloom filtresi, bir öğenin bir kümede “kesinlikle yok” mu yoksa “belki var” mı olduğunu yer tasarruflu biçimde denetler. Trie (önek ağacı) sözcükleri baş harflerine göre saklar.

Biraz daha ayrıntılı: Bloom filtresi, birkaç özet işlevli bir bit dizisidir. “Hayır” kesindir, “evet” yanlış alarm olabilir. Trie’nin her karakter için bir dalı vardır. Ortak başlangıçlar yalnızca bir kez saklanır; arama O(sözcük uzunluğu) sürer.