Hallo habrozhiteli! Algorithmen sind das Herz und die Seele der Informatik. Sie können nicht ohne sie auskommen, sie sind überall - von Netzwerkrouting und Genomikberechnungen bis hin zu Kryptographie und maschinellem Lernen. Der „perfekte Algorithmus“ macht Sie zu einem echten Profi, der Aufgaben festlegt und diese sowohl im Leben als auch bei einem Vorstellungsgespräch meisterhaft löst, wenn Sie ein IT-Unternehmen einstellen.
Im zweiten Buch spricht Tim Rafgarden, der Guru der Algorithmen, über die Graphensuche und ihre Anwendung, den Suchalgorithmus für kürzeste Wege sowie die Verwendung und Implementierung einiger Datenstrukturen: Heaps, Suchbäume, Hash-Tabellen und den Bloom-Filter.
Dieser Beitrag enthält einen Auszug aus Bloom Filters: The Basics.
Worum geht es in diesem Buch?
Der zweite Teil des Buches „Perfekter Algorithmus“ ist ein Einführungskurs in die Grundlagen der Alphabetisierung zu den folgenden drei Themen.
Diagrammsuche und Anwendungen . Diagramme modellieren eine Reihe verschiedener Arten von Netzwerken, einschließlich Straße, Kommunikation, soziale Netzwerke und Netzwerke von Abhängigkeiten zwischen Aufgaben. Diagramme können komplex sein, aber es gibt einige unglaublich schnelle Grundelemente, um über die Diagrammstruktur zu sprechen. Wir werden mit linearen Zeitgraphen-Suchalgorithmen beginnen, von Anwendungen, die von der Netzwerkanalyse bis zum Erstellen einer Abfolge von Operationen reichen.
Die kürzesten Wege . Bei dem Problem mit dem kürzesten Pfad besteht das Ziel darin, die beste Route im Netzwerk von Punkt A nach Punkt B zu berechnen. Diese Aufgabe hat offensichtliche Anwendungen, wie beispielsweise die Berechnung von Verkehrsrouten, und tritt auch in getarnter Form bei vielen anderen universellen Aufgaben auf. Wir werden einen unserer Graphensuchalgorithmen verallgemeinern und zum berühmten Dijkstra-Suchalgorithmus für kürzeste Wege kommen.
Datenstrukturen . Dieses Buch macht Sie zu einem hochqualifizierten Benutzer verschiedener Datenstrukturen, die eine sich entwickelnde Gruppe von Objekten mit den zugehörigen Schlüsseln unterstützen sollen. Das Hauptziel ist es, eine Vorstellung davon zu entwickeln, welche Datenstruktur für Ihre Anwendung geeignet ist. Zusätzliche Abschnitte enthalten Richtlinien für die Implementierung dieser Datenstrukturen von Grund auf neu.
Zunächst diskutieren wir Heaps, die das gespeicherte Objekt mit dem kleinsten Schlüssel schnell identifizieren können und auch zum Sortieren, Implementieren einer Prioritätswarteschlange und Implementieren des nahezu linear-zeitlichen Algorithmus von Dijkstra nützlich sind. Suchbäume behalten die vollständige Reihenfolge der Schlüssel für gespeicherte Objekte bei und unterstützen ein noch breiteres Spektrum von Vorgängen. Hash-Tabellen sind für ultraschnelle Suchvorgänge optimiert und in modernen Programmen weit verbreitet. Wir betrachten auch den Bloom-Filter, einen nahen Verwandten der Hash-Tabelle, der aufgrund zufälliger Fehler weniger Speicherplatz benötigt.
Sie können sich in den Abschnitten „Schlussfolgerungen“, die jedes Kapitel vervollständigen und die wichtigsten Punkte identifizieren, ausführlicher mit dem Inhalt des Buches vertraut machen. Die mit einem Sternchen gekennzeichneten Abschnitte des Buches sind in Bezug auf den Informationsstand am weitesten fortgeschritten. Wenn das Buch für eine oberflächliche Einarbeitung in das Thema konzipiert ist, kann der Leser sie überspringen, ohne die Integrität des Geschriebenen zu verlieren.
Themen in drei weiteren Teilen behandelt . Der erste Teil des Buches „Perfekter Algorithmus. Fundamentals “umfasst die asymptotische Notation (die O-Large-Notation und ihre nahen Verwandten), die Algorithmen zum Teilen und Erobern und den Hauptsatz der Wiederholungsrelation - die Hauptmethode, die randomisierte schnelle Sortierung und ihre Analyse sowie linear-zeitliche Auswahlalgorithmen. Der dritte Teil befasst sich mit gierigen Algorithmen (Planung, minimale Spannbäume, Clustering, Huffman-Codes) und dynamischer Programmierung (Rucksackproblem, Sequenzausrichtung, kürzeste Wege, optimale Suchbäume). Der vierte Teil befasst sich mit der NP-Vollständigkeit, was dies für einen Algorithmusdesigner bedeutet, und Strategien zur Lösung rechnerisch unlösbarer Probleme, einschließlich heuristischer Analyse und lokaler Suche.
12.5. Bloom-Filter: Die Grundlagen
Bloom-Filter sind nahe Verwandte von Hash-Tabellen. Sie sind sehr kompakt, machen aber regelmäßig Fehler. In diesem Abschnitt wird beschrieben, wie gut Bloom-Filter sind und wie sie implementiert werden. In Abschnitt 12.6 wird eine Kompromisskurve zwischen dem vom Filter verwendeten Speicherplatz und seiner Fehlerrate dargestellt.
12.5.1. Unterstützte Operationen
Der Grund für die Existenz von Bloom-Filtern ist im Wesentlichen der gleiche wie bei einer Hash-Tabelle: superschnelle Einfüge- und Ansichtsvorgänge, mit denen Sie sich schnell daran erinnern können, was Sie gesehen haben und was nicht. Warum sollte uns eine andere Datenstruktur mit denselben Operationen stören? Weil Bloom-Filter Hash-Tabellen in Anwendungen vorzuziehen sind, in denen Speicherplatz Gold wert ist und ein zufälliger Fehler kein Hindernis für die Transaktion darstellt.
Wie Hash-Tabellen mit offener Adressierung sind Bloom-Filter viel einfacher zu implementieren und vorzustellen, wenn sie nur Einfüge- und Ansichtsvorgänge (und ohne den Löschvorgang) unterstützen. Wir werden uns auf diesen Fall konzentrieren.
BLÜTENFILTER: UNTERSTÜTZTE FUNKTIONEN
Ansicht: Geben Sie mit der Taste k "Ja" zurück, wenn k zuvor in den Bloom-Filter eingefügt wurde, andernfalls "Nein".
Einfügen: Fügen Sie dem Bloom-Filter einen neuen Schlüssel k hinzu.
Bloom-Filter sind räumlich sehr effizient; Typischerweise benötigen sie möglicherweise nur 8 Bits pro Einfügung. Das ist unglaublich, da 8 Bit nicht ausreichen, um sich auch nur einen 32-Bit-Schlüssel oder Zeiger auf ein Objekt zu merken! Aus diesem Grund gibt die Ansichtsoperation im Bloom-Filter nur die Antwort "Ja" / "Nein" zurück, während diese Operation in der Hash-Tabelle einen Zeiger auf das gewünschte Objekt zurückgibt (falls es gefunden wird). Aus diesem Grund akzeptiert die Einfügeoperation jetzt nur den Schlüssel und nicht den (Zeiger auf) das Objekt.
Im Gegensatz zu allen anderen von uns untersuchten Datenstrukturen können Bloom-Filter falsch sein. Es gibt zwei Arten von Fehlern: falsch negative Ergebnisse, wenn die View-Operation "false" zurückgibt, auch wenn der angeforderte Schlüssel bereits früher eingefügt wurde, und falsche Anweisungen (oder positive), wenn die View-Operation "true" zurückgibt, obwohl der angeforderte Schlüssel in der Vergangenheit noch nicht eingefügt wurde . In Abschnitt 12.5.3 werden wir sehen, dass die grundlegenden Bloom-Filter niemals unter falsch negativen Ergebnissen leiden, sondern „Phantomelemente“ in Form falscher Aussagen enthalten können. Abschnitt 12.6 zeigt, dass die Häufigkeit falscher Behauptungen durch entsprechende Anpassung der Raumnutzung kontrolliert werden kann. Eine typische Implementierung eines Bloom-Filters kann eine Fehlerrate von etwa 1% oder 0,1% aufweisen.
Die Ausführungszeiten für die Einfüge- und Ansichtsvorgänge sind so schnell wie in der Hash-Tabelle. Und noch besser ist, dass diese Vorgänge unabhängig von der Implementierung des Bloom-Filters und des Datensatzes1 garantiert in konstanter Zeit ausgeführt werden. Die Implementierung und der Datensatz wirken sich jedoch auf die Filterfehlerrate aus.
Um die Vor- und Nachteile von Bloom-Filtern gegenüber Hash-Tabellen zusammenzufassen:
BLÜTENFILTER GEGEN HASH TABLES
1. Vorteile: räumlich effektiver.
2. Vorteile: Garantierte Dauerbetriebe für jeden Datensatz.
3. Nachteile: Zeiger auf Objekte können nicht gespeichert werden.
4. Nachteile: komplexere Löschungen im Vergleich zu einer Hash-Tabelle mit Kupplung.
5. Nachteile: Nicht-Null-Wahrscheinlichkeit einer falschen Aussage.
Die Liste der Indikatoren für die grundlegenden Bloom-Filter lautet wie folgt.
Tabelle 12.4. Grundlegende Bloom-Filter: Unterstützte Vorgänge und deren Ausführungszeit. Das Dolchzeichen (†) zeigt an, dass die Ansichtsoperation eine steuerbare Wahrscheinlichkeit für falsche Behauptungen aufweist, die jedoch nicht Null ist
Bloom-Filter sollten anstelle von Hash-Tabellen in Anwendungen verwendet werden, in denen ihre Vor- und Nachteile keine Rolle für die Transaktion spielen.
WANN MAN DEN BLÜTENFILTER VERWENDET
Wenn eine Anwendung eine schnelle Suche mit einem sich dynamisch entwickelnden Satz von Objekten erfordert, der Platz Gold wert ist und eine akzeptable geringe Anzahl falscher Behauptungen vorliegt, ist der Bloom-Filter normalerweise die bevorzugte Datenstruktur.
12.5.2. Anwendungen
Als nächstes gibt es drei Verwendungszwecke bei wiederholten Scans, bei denen Platzersparnis wichtig sein kann und falsche Aussagen kein Hindernis für die Transaktion darstellen.
Rechtschreibprüfung. In den 1970er Jahren wurden Bloom-Filter verwendet, um Rechtschreibprüfungen zu implementieren. In der Vorverarbeitungsphase wird jedes Wort im Wörterbuch in den Bloom-Filter eingefügt. Die Schreibweise eines Dokuments hängt von einer Operation ab. Sehen Sie sich ein Wort in einem Dokument an und markieren Sie alle Wörter, für die diese Operation "Nein" zurückgibt.
In diesem Anhang entspricht eine falsche Aussage einem ungültigen Wort, das die Rechtschreibprüfung versehentlich akzeptiert. Solche Fehler machten die Rechtschreibprüfung nicht ideal. In den frühen 1970er Jahren war der Weltraum Gold wert, daher war die Verwendung von Bloom-Filtern zu dieser Zeit eine Win-Win-Strategie.
Verbotene Passwörter . Eine alte Anwendung, die bis heute gültig ist, verfolgt verbotene Passwörter - Passwörter, die zu häufig oder zu leicht zu erraten sind. Zunächst werden alle verbotenen Passwörter in den Bloom-Filter eingefügt. Zusätzliche verbotene Passwörter können später nach Bedarf eingefügt werden. Wenn ein Benutzer versucht, sein Kennwort festzulegen oder zurückzusetzen, sucht das System im Bloom-Filter nach dem vorgeschlagenen Kennwort. Wenn die Suche "Ja" zurückgibt, wird der Benutzer aufgefordert, es erneut mit einem anderen Kennwort zu versuchen. Hier wird eine falsche Aussage in ein sicheres Passwort übersetzt, das das System ablehnt.
Vorausgesetzt, die Fehlerrate ist nicht zu hoch, beispielsweise nicht mehr als 1% oder 0,1%, spielt dies keine große Rolle. Von Zeit zu Zeit benötigen einige Benutzer einen zusätzlichen Versuch, ein für das System akzeptables Kennwort zu finden.
Internet-Router . Eine Reihe der heutigen atemberaubenden Anwendungen von Bloom-Filtern findet tief im Internet statt, wo Datenpakete Router mit Streaming-Geschwindigkeit passieren. Es gibt viele Gründe, warum ein Router sich schnell daran erinnern möchte, was er in der Vergangenheit gesehen hat. Beispielsweise möchte ein Router möglicherweise die Quell-IP-Adresse eines Pakets in der Liste der blockierten IP-Adressen finden, den Inhalt des Caches verfolgen, um falsche Cache-Ansichten zu vermeiden, oder Statistiken führen, mit denen ein Denial-of-Service-Netzwerkangriff identifiziert werden kann. Die Paketankunftsrate erfordert superschnelle Ansichten, und der begrenzte Speicher des Routers macht Speicherplatz Gold wert. Diese Anwendungen werden direkt vom Bloom-Filter verwaltet.
12.5.3. Implementierung
Wenn Sie in den Bloom-Filter schauen, sehen Sie eine elegante Implementierung. Die Datenstruktur unterstützt eine n-Bit-Zeichenfolge oder ebenfalls ein Array A der Länge n, in dem jedes Element 0 oder 1 ist. (Alle Elemente werden auf Null initialisiert.) Diese Struktur verwendet auch m Hash-Funktionen h1, h2, ..., hm , während jeder das Universum U aller möglichen Schlüssel auf die Menge {0, 1, 2, ..., n - 1} von Positionen im Array abbildet. Der Parameter m ist proportional zur Anzahl der Bits, die vom Bloom-Filter zum Einfügen verwendet werden, und ist in der Regel eine kleine Konstante (z. B. 5).
Immer wenn ein Schlüssel in einen Bloom-Filter eingefügt wird, setzt jede der m Hash-Funktionen ein Flag und setzt das entsprechende Bit von Array A auf 1.
BLÜTENFILTER: EINFÜGEN (AUF SCHLÜSSEL)
for i = 1 to m do A[hi(k)] := 1
Wenn beispielsweise m = 3 und h1 (k) = 23, h2 (k) = 17 und h3 (k) = 5 sind, bewirkt das Einfügen von k, dass das 5., 17. und 23. Bit des Arrays gleich gesetzt werden 1 (Abb. 12.5).
In der Ansichtsoperation sucht der Bloom-Filter nach dem Fingerabdruck, der möglicherweise beim Einfügen k verblieben ist.
BLÜTENFILTER: ANSICHT (SCHLÜSSELSCHLÜSSEL)
for i = 1 to m do if A [hi (k)] = 0 then return «» return «»
Jetzt können wir sehen, warum Bloom-Filter nicht unter falsch negativen Ergebnissen leiden können. Wenn der Schlüssel k eingefügt wird, werden die entsprechenden m Bits auf 1 gesetzt. Während der Lebensdauer des Bloom-Filters können die Bits ihren Wert von 0 auf 1 ändern, jedoch nicht umgekehrt. Somit bleiben diese m Bits für immer 1. Bei jeder nachfolgenden View k-Operation wird garantiert die richtige Ja-Antwort zurückgegeben.
Wir können auch sehen, wie falsche Aussagen entstehen. Angenommen, m = 3 und die vier Schlüssel k1, k2, k3, k4 haben die folgenden Hashwerte:
Angenommen, wir fügen k1, k2, k3 und k4 in einen Bloom-Filter ein (Abbildung 12.6). Diese drei Einfügungen führen dazu, dass insgesamt neun Bits gleich 1 gesetzt werden, einschließlich drei Bits im Fingerabdruck des Schlüssels k1 (5, 17 und 23). Zu diesem Zeitpunkt kann der Bloom-Filter nicht mehr unterscheiden, ob der Schlüssel k1 eingefügt wurde oder nicht. Selbst wenn k1 nicht in den Filter eingefügt wurde, gibt die Suche "Ja" zurück, was eine falsche Aussage ist.
Intuitiv können wir davon ausgehen, dass mit zunehmender Größe n des Bloom-Filters die Anzahl der Überlagerungen zwischen den Fingerabdrücken verschiedener Tasten abnehmen sollte, was wiederum zu einer geringeren Anzahl falscher Aussagen führt. Das Hauptziel des Bloom-Filters ist jedoch die Platzersparnis. Gibt es einen Mittelweg, auf dem sowohl n als auch die Häufigkeit falscher Aussagen gleichzeitig gering sind? Die Antwort ist nicht offensichtlich und erfordert eine mathematische Analyse im nächsten Abschnitt.
»Weitere Informationen zum Buch finden Sie auf
der Website des Herausgebers»
Inhalt»
AuszugFür Khabrozhiteley 20% Rabatt auf den Gutschein -
AlgorithmenNach Bezahlung der Papierversion des Buches wird ein elektronisches Buch per E-Mail verschickt.