Bloom-Filter und Trie

Kurz: Ein Bloom-Filter prüft platzsparend, ob ein Element „sicher nicht” oder „vielleicht” in einer Menge ist. Ein Trie (Präfixbaum) speichert Wörter nach ihren Anfangsbuchstaben.

Genauer: Der Bloom-Filter ist ein Bit-Array mit mehreren Hash-Funktionen. Ein „Nein” ist sicher, ein „Ja” kann ein Fehlalarm sein. Ein Trie hat für jedes Zeichen eine Verzweigung. Gemeinsame Anfänge werden nur einmal gespeichert, die Suche dauert O(Länge des Worts).

Im Detail

• Bloom-Filter: Spart teure Nachschlagen (z. B. „Ist diese URL bekannt schädlich?”), Datenbanken (LSM-Bäume), Caches. Löschen ist nicht möglich.
• Fehlerrate: Lässt sich über Größe und Zahl der Hashes einstellen.
• Trie: Autovervollständigung, Rechtschreibprüfung, Routing-Tabellen (IP-Präfixe), Wörterbuch-Spiele.
• Speicher: Tries brauchen bei vielen Wörtern viel Platz, komprimierte Varianten (Radix-Baum) helfen.

Siehe auch: Hashing, Baum-Datenstruktur