Planten un Bloomen

Wer sucht, der findet – sagt man. Leider trifft die Aussage in der IT-Welt eher selten zu. Vor allem, weil eine erfolglose Suche oft länger dauert als eine erfolgreiche. Um etwa festzustellen, ob sich ein bestimmter Schlüssel in einer unsortierten Liste befindet, muss ein Programm die gesamte Liste durchlaufen. Eine positive Antwort hingegen erhält es im Schnitt nach der Hälfte der Schritte.

In Bäumen oder sortierten Feldern lassen sich Daten schneller finden: Die Suchzeit wächst in der Regel logarithmisch mit der Zahl der gespeicherten Datensätze (O(log n)). Noch schneller sind Hashtabellen: Solange keine Kollisionen auftreten, bleibt die Suchzeit konstant. Andernfalls wächst sie je nach Implementierung linear oder logarithmisch.

Erheblichen Einfluss hat das verwendete Speichermedium. Auf der Festplatte etwa dauert eine Suche um Größenordnungen länger als im Hauptspeicher. Ein Index im RAM kann Abhilfe schaffen oder die Auswirkungen zumindest lindern – sofern der Platz dafür ausreicht.

Ja, nein und vielleicht

1970 entwickelte Burton H. Bloom für ein Rechtschreibprüfprogramm eine besonders kompakte Darstellung: den Bloomfilter. Statt eine Wortliste in seine Software einzubinden, berechnete er mehrere Hashwerte aller Wörter und notierte sie in einem Bitfeld (siehe Listing 1). Will man im Bloomfilter einen bestimmten Schlüssel finden, muss man dessen Hashwerte berechnen und die dazugehörigen Bits untersuchen. Hat eins den Wert 0, ist der Datensatz garantiert nicht vorhanden. Sind alle gesetzt, besteht eine gewisse Wahrscheinlichkeit, dass er gespeichert ist.

Darin besteht einer der Nachteile des Bloomfilters: Er gibt nicht immer eine exakte Antwort, sondern beschränkt sich auf „nein“ und „vielleicht“. Die Wahrscheinlichkeit P, dass das Vielleicht sich als Nein entpuppt (False Positive), hängt vom Füllgrad – dem Prozentsatz gesetzter Bits – und der Zahl der verwendeten Hashfunktionen ab:

P = Füllgrad Zahl der Hashes 

Ist zum Beispiel das Bitfeld zu 10 % gefüllt und kommen drei Hashfunktionen zum Einsatz, erweist sich von 1000 positiven Antworten durchschnittlich eine als falsch. Bei einem zur Hälfte gefüllten Bitfeld bedeutet jedoch bereits jedes achte Vielleicht tatsächlich Nein. Es empfiehlt sich daher, den Füllgrad niedrig zu halten. Formeln für die Berechnung sind unter anderem im englischen Wikipedia-Eintrag zu finden (siehe Kasten „Onlinequellen“). Wer mit Mathematik auf dem Kriegsfuß steht, kann sich die Parameter auch online ausrechnen lassen.

Ein weiterer Nachteil des klassischen Bloomfilters ist, dass sich Einträge nicht entfernen lassen. Nach dem Löschen von Datensätzen muss das Programm den Inhalt des Bitfelds neu berechnen. Alternativ kann es mitzählen, wie oft es ein bestimmtes Bit gesetzt hat. Fällt beim Entfernen der Zähler auf Null, muss es das Bit wieder löschen. Allerdings beanspruchen die Zähler erheblich mehr Speicherplatz als das Bitfeld. Kommen Einfüge- und Löschoperationen relativ selten vor, kann man die Zähler jedoch auf den Massenspeicher auslagern, ohne dass die Performance stark darunter leidet – beim Suchen benötigt man sie nicht.

Bloomfilter im Einsatz

In begrenztem Umfang unterstützen Bloomfilter auch die übrigen für Mengen (Sets) definierten Operationen. Vereinigungs- und Schnittmenge erhält man durch bitweise Oder- beziehungsweise Und-Verknüpfung der Bitfelder. Die müssen dazu natürlich gleich groß sein; außerdem müssen die Filter dieselben Hashfunktionen verwenden. Die Subtraktion zweier Mengen lässt sich leider nicht mit einfachen Bit-Operationen realisieren. In manchen Fällen hilft ein zweiter Bloomfilter, der die entfernten Elemente aufnimmt. Allerdings kann es vorkommen, dass beide Filter behaupten, ein bestimmtes Element zu enthalten. Welcher die Wahrheit sagt, lässt sich nur durch eine Analyse der Daten feststellen.

#define ANZAHL_BYTES    65536u
#define ANZAHL_BITS     (ANZAHL_BYTES / 8u)
unsigned char bitfeld[ANZAHL_BYTES];
void set_bit(unsigned x) {
    bitfeld[x / 8] |= 1u << x % 8;
}

int test_bit(unsigned x) {
    return bitfeld[x / 8] & (1u << x % 8);
}

void wort_hinzufuegen(const char *wort) {
    unsigned h;
    h = hash_1(wort) % ANZAHL_BITS; set_bit(h);
    h = hash_2(wort) % ANZAHL_BITS; set_bit(h);
    ...
    h = hash_k(wort) % ANZAHL_BITS; set_bit(h);
}

int wort_vorhanden(const char *wort) {
    unsigned h;
    h = hash_1(wort) % ANZAHL_BITS; if (!test_bit(h)) return 0;
    h = hash_2(wort) % ANZAHL_BITS; if (!test_bit(h)) return 0;
    ...
    h = hash_k(wort) % ANZAHL_BITS; if (!test_bit(h)) return 0;
    return 1;
}

(mr)