Bevor ich meine Frage stelle, möchte ich mit meinem Verständnis der Definitionen beginnen, um mich vor weiterer Verwirrung zu schützen und Hintergrundinformationen zu geben.
Huffman-Code ist der Binärcode, der aus einem durch den Huffman-Algorithmus konstruierten Binärbaum induziert wird.
Hu-Tucker-Code ist der Binärcode, der aus einem alphabetischen Suchbaum induziert wird.
Laut Wikipedia (siehe Abschnitt Optimale alphabetische Binärbäume (Hu-Tucker-Codierung)):
Beim Standard-Huffman-Codierungsproblem wird angenommen, dass jedes Codewort einem beliebigen Eingabesymbol entsprechen kann. In der alphabetischen Version muss die alphabetische Reihenfolge der Ein- und Ausgänge identisch sein. So konnte beispielsweise kein Code werden. Stattdessen sollte entweder oder . Dies ist auch als Hu-Tucker-Problem bekannt, nachdem TC Hu und Alan Tucker, die Autoren der Arbeit, die erste linearithmische Lösung für dieses optimale binäre alphabetische Problem vorgestellt haben, das einige Ähnlichkeiten mit dem Huffman-Algorithmus aufweist, jedoch keine Variation davon darstellt Algorithmus. Diese optimalen alphabetischen Binärbäume werden häufig als binäre Suchbäume verwendet.
Meine Frage ist, was sind die Anwendungen solcher Bäume? (alphabetischer Binärbaum)
Ich habe versucht, online zu suchen, konnte aber keine zufriedenstellende Antwort finden.
Ich habe auch die Einleitung in Hu & Tuckers Artikel zu diesem Thema gelesen: Optimale Computersuchbäume und alphabetischer Code variabler Länge , aber ich konnte anhand
ihres Beispiels nicht genau herausfinden, wie ein solcher Baum verwendet wird.
Ich kann die Notwendigkeit eines kompakten, optimalen Präfixcodes, der durch einen optimalen Baum (dh Huffman-Code) induziert wird, sehr gut verstehen. Dies kann zur Komprimierung verwendet werden. Wozu werden jedoch alphabetische Binärbäume verwendet?
quelle
Antworten:
Lassen Sie mich Ihnen ein Beispiel aus der Praxis geben, das etwas sehr ähnlich ist, das ich einmal geschrieben habe.
Angenommen, Sie implementieren ein Bibliothekskatalogsystem. Ein Bibliothekskatalog ist konzeptionell eine Sammlung von Dokumenten (möglicherweise im MARC- Format). Ein Benutzer dieses Systems kann wie in jeder Suchmaschine eine Abfrage eingeben und im Gegenzug eine Reihe von Dokumenten erhalten. Der Benutzer möchte in der Lage sein, die Ergebnismenge nach einem Feld (z. B. Titel oder Autor) zu sortieren und die Ergebnismenge bildschirmweise anzuzeigen.
Das Sortieren ist ein bekanntes Problem. Angenommen, dies ist eine große Bibliothek, und eine Suche gibt 100.000 relevante Dokumente zurück. Es ist klar, dass der Benutzer nicht alle durchsehen wird! Tatsächlich kann der Benutzer nur die ersten paar Ergebnisbildschirme (z. B. 50 bis 100 Dokumente) betrachten und feststellen, dass seine Abfrage zu umfangreich war, und sie daher weiter verfeinern.
Darüber hinaus muss für den Zugriff auf den Sortierschlüssel für ein Dokument das Dokument analysiert werden. Richtig, Sie könnten die möglichen Sortierschlüssel in ein Formular extrahieren, in dem Sie MARC (oder noch schlimmer SGML / XML) nicht analysieren mussten, obwohl dies Daten duplizieren würde. Und außerdem sind dies Saiten, über die wir sprechen. Sie haben eine variable Länge, was die Speicher- und Festplattenverwaltung erschwert.
Sie können also ein Format mit fester Größe ausprobieren. Sie können beispielsweise die ersten K Zeichen aus jedem Titel für ein vorbestimmtes K nehmen und in einem Array auf der Festplatte speichern, das nach Dokumentnummer indiziert ist. Dann könnten Sie zuerst die Dokumente nach diesen Zeichenfolgenpräfixen sortieren (dh so etwas wie eine Bucket / Radix-Sortierung), und alle Dokumente, die in denselben Bucket fallen, könnten dann sortiert werden, indem der "echte" Sortierschlüssel aus den Dokumenten extrahiert wird.
Das Schöne daran ist, dass Sie die Ergebnismenge nicht vollständig sortieren müssen. Da der Benutzer durch das Set blättert, müssen Sie nur die ersten paar Screenfuls vollständig sortieren und nur genügend Bucket-Informationen aufbewahren, um die anderen zu sortieren, wenn der Benutzer beschließt, so weit zu blättern.
Das ist also eine Verbesserung, aber wie setzt man K? Viele Titel beginnen mit den Buchstaben "The", und das verwendet 32 Informationsbits für sehr wenig Unterscheidungskraft. In der Tat wären Sie wahrscheinlich überrascht, wie viele Zeitschriften als "The International Journal of X" oder ähnliches bezeichnet werden, und bei einigen Suchanfragen werden wahrscheinlich viele Dokumente mit ähnlichen Titeln zurückgegeben.
Eine mögliche Lösung ist die Verwendung eines auftragserhaltenden Codes. Komprimieren Sie alle Titel mit diesem Code und speichern Sie die ersten 64 Bit (oder einen anderen festen Betrag) des komprimierten Titels in einem Array auf der Festplatte. Dies hat einige praktische Vorteile: Teile des Titels, die nur eine sehr geringe Unterscheidungskraft haben, erhalten sehr kurze Codewörter (damit Sie keinen Platz für irrelevante Details verschwenden). Sie können danach sortieren, da die Reihenfolge erhalten bleibt und die Schlüssel sind von fester Länge (so dass sie einfach und effizient zu verwalten sind).
quelle