Effizientes Programmieren - Kurs 4

Diesmal wollen wir auf eine weitere wichtige Anwendung von Bäumen eingehen: das Codieren. Hier können sie uns dabei helfen, Dateien zu packen und anschließend wieder zu entpacken. Anschließend beschäftigen wir uns mit dem Suchen in Textstrings. Zuerst wollen wir uns aber mit einer speziellen Baumspeicherung befassen.

Für das Sortieren mit Bäumen kommt eine Abart eines Baumes zum Einsatz, die auf den ersten Blick oft gar nicht als solcher erkannt wird. Der Heap (dt. Halde) läßt sich am besten als Binärbaum veranschaulichen, der eine spezielle Art der Sortierung aufweist. So muß für einen Heap immer gelten, daß der Wert eines jeden Knotens immer kleiner ist als der seiner Söhne. Der Grund, warum der Heap von vielen nicht mit Bäumen in Verbindung gebracht wird, ist, daß er selten in der für "normale" Bäume üblichen Standardspeicherung (Zeiger auf linken und rechten Sohn) vorkommt, sondern meist in einem Array gespeichert wird. Sie werden jedoch sehen, daß man auch alle anderen üblichen Binärbäume in Arrays abspeichern kann, was oft sogar von Vorteil ist.

Die Speicherung in einem Feld erfolgt beim Heap nach einem ganz bestimmten Schema. Das erste Element des Feldes enthält dabei immer die Wurzel. Die Söhne eines Knotens an der Position i stehen außerdem immer in den Feldelementen 2i und 2i+1. Ein Beispiel für einen Binärbaum und dessen Repräsentation in Form eines Feldes zeigt Abbildung 1. Dieser Baum bzw. das dazugehörige Feld stellen außerdem einen Heap dar, da alle Söhne größer sind als ihr Vater.

Abbildung 1: Ein Heap in beiden Speicherarten

Betrachtet man einen solchen Heap, bemerkt man sofort, daß der kleinste Knoten immer die Wurzel des Heaps darstellt. Will man nun das Feld aufsteigend sortiert ausgeben, braucht man immer nur das erste Element im Feld ausgeben und anschließend die restlichen Elemente wieder in einen Heap umwandeln. Das Verfahren, das nach dieser Methode funktioniert, heißt Heapsort.

Unser Problem bleibt nun noch einen geeigneten Algorithmus zu finden, der nach dem Entfernen der Wurzel den Rest wieder in einen Heap zurückverwandelt. Dazu geht man folgendermaßen vor: man zieht das allerletzte Element im Array an die erste Stelle (also an die Wurzel des Baumes). Danach vertauscht man es solange mit dem kleineren seiner Söhne bis entweder beide Söhne größer sind oder das Ende des Baumes erreicht wurde. Wenn wir nach dieser Vorschrift vorgehen, erhalten wir anschließend wieder einen Heap. In Listing 1 sehen Sie ein Beispielprogramm für Heapsort.

Diesen zuletzt besprochenen Algorithmus zur Bewahrung der Heapeigenschaften nach dem Entfernen der Wurzel können wir auch bei unserer nächsten Anwendung von Bäumen brauchen, dem schon anfangs angesprochenen Codieren. Was versteht man eigentlich unter "Codieren"? Nun, jeder von uns hat bestimmt schon einmal mit dem ASCII-Code zu tun gehabt. Dabei handelt es sich um eine standardisierte Darstellung von Buchstaben und Zeichen im Binärcode.

Obwohl vielen Computer-Besitzern der ASCII-Code heilig ist, stellt er nur eine mögliche Codierung von Zeichen als 7-bit-Zahl oder 8-bit-Zahl dar. Für normale Zwecke ist er durchaus ausreichend. Manchmal kann es jedoch nötig sein, ihn durch einen anderen, vielleicht platzsparenderen Code zu ersetzen. Beispiele dafür wären bei der Übertragung über Telefonnetze, bei denen kürzere Dateien billiger sind, oder wenn besonders viele Daten auf einer Diskette Platz finden sollen. Prinzipiell arbeiten auch alle bekannten Packer mit solchen Methoden.

Wie Sie sicherlich schon vermutet haben, werden uns auch hierbei die Bäume wertvolle Dienste erweisen. Sie werden in diesem Fall Code-Bäume genannt. Speziell wollen wir uns hier mit dem sogenannten Huffmann-Baum beschäftigen. Damit ist es möglich, einen stets optimalen Code für eine bestimmte Datei zu erhalten.

Veranschaulichen wir uns zuerst einmal die Methode der Huffmann-Codierung an einem Beispiel. Dabei gehen wir von dem Fall aus, daß unsere zu codierende Datei nur aus den ersten sechs Buchstaben des Alphabets besteht. Wir nehmen beispielweise an, daß sie 3 A, 4 B, 1 C, 2 D, 5 E und 2 F enthält. Nun müssen wir den einzelnen Buchstaben bestimmte Codes zuordnen. Im ASCII-Code hätte A den Code 65, B hätte 66 usw. Es hat natürlich keinen Sinn, den einzelnen Buchstaben einfach nur andere Codes zuzuordnen. Vielmehr geht man dabei so vor, daß den Zeichen Codes verschiedener Länge zugewiesen werden. Dabei liegt es nahe, den häufiger vorkommenden Buchstaben kürzere Codes zu geben auf Kosten der seltener auftretenden Buchstaben. Das wirft natürlich die berechtigte Frage auf, wie man erkennen soll, wo der Code des einen Zeichens endet und der des nächsten beginnt, wenn die Länge der Codes nicht eindeutig ist.

Dieses Problem umgeht die Idee des präfixfreien Codes. Ein Code ist dann präfixfrei, wenn kein Code ein Anfangsstück eines anderen darstellt. Der Codesatz 01, 110, 111 ist beispielsweise präfixfrei. Ist aber auch der Code 11 Teil des Codesatzes, geht die Präfixeigenschaft verloren, da 11 ein Anfangsstück der Codes 110 und 111 darstellt. Bei Benützung präfixfreier Codes ist eine codierte Datei wieder eindeutig zu dekodieren. Es bleibt das Problem, welche Codes man den einzelnen Buchstaben nun genau zuweist. Wie schon vorhin erwähnt, spielt die Häufigkeit des Auftretens eines Buchstabens eine große Rolle. Betrachten wir nocheinmal unser Beispiel von vorhin mit den ersten sechs Buchstaben. Um diese optimal zu codieren, schreiben wir sie nebeneinander und darunter vermerken wir, wie oft sie aufgetreten sind (s. Abbildung 2). Von diesen Zahlen wählen wir die beiden niedrigsten und zählen sie zusammen. Das Ergebnis notieren wir uns darunter und verbinden es mit den beiden addierten Zahlen durch zwei Striche. Anschließend streichen wir die eben addierten Zahlen durch.

In unserem Beispiel in Abbildung 2 werden also zuerst die Buchstaben C und D herangezogen und deren Häufigkeiten addiert. Die sich daraus ergebende Drei wird darunter notiert, die beiden Linien gezogen und die Eins und die Zwei unter dem C bzw. dem D durchgestrichen. Nun wird dasselbe auch auf die restlichen Zahlen, inklusive der eben erzeugten Drei angewandt. Wieder werden die kleinsten Zahlen addiert, verbunden und anschließend durchgestrichen bis nur mehr eine Zahl übrig ist. Wenn Sie nun das eben entstandene Kunstwerk umdrehen, können Sie vielleicht mit etwas Phantasie einen Baum erkennen.

Abbildung 2: Huffmann-Baum und seine Speicherung

Um diesen Binärbaum nun endgültig in einen Huffmann-Baum zu verwandeln, bleibt für uns nur mehr eine Kleinigkeit zu tun. Wir fügen zu allen linken Ästen eine 0 dazu und zu allen rechten Ästen eine 1. Schließlich brauchen wir nur den Code eines jeden Buchstabens abzulesen. Dazu gehen wir von der Wurzel unten aus und wandern den Pfad bis zu dem jeweiligen Buchstaben entlang. Dabei schreiben wir eine Null nieder, wenn wir uns auf einem mit 0 bezeichneten Ast bewegen, und eine Eins sonst. Der Buchstabe A aus Abbildung 2 erhält also den Code 00, B wird zu 01, C erhält entsprechend 1000 usw.

Wie Sie sehen wird dadurch der Code für die häufiger vorkommenden Buchstaben A, B und E nur 2 Bits lang, während der Code für F schon 3 und jener für C und D gar 4 Bits benötigt. Wir wissen nun also, welchen Code wir welchem Buchstaben zuordnen sollen - der Codierung steht also nichts mehr im Wege. Nun wollen wir den Code aber anschließend auch wieder decodieren, um ihn in seiner ursprünglichen Form wieder verwenden zu können.

Dazu lesen wir von der codierten Datei immer nur ein Bit ein. Erhalten wir eine Null, dann steigen wir den linken Ast des Huffmann-Baumes rauf, ansonsten rechts. Erreichen wir dabei ein Blatt, dann haben wir einen Buchstaben fertig decodiert und beginnen für den nächsten abermals bei der Wurzel ganz unten. So können wir die Daten Zeichen für Zeichen wieder decodieren.

Wie immer gibt es auch zu den Huffmann-Bäumen ein kleines Programm zum Abtippen (Listing 2). Es erwartet das zu codierende Quellfile und das Zielfile als Parameter und führt anschließend eine Codierung durch. Danach wird das soeben codierte Listing wieder decodiert und das Ergebnis angezeigt.

Die Codierung erfolgt in zwei Durchläufen. Zuerst wird gezählt, wie oft jedes Zeichen in der zu codierenden Datei vorkommt. Die Anzahl wird dabei in einem Heap gespeichert. Anschließend werden immer die kleinsten Elemente des Heaps zusammengefaßt, wie oben beschrieben, bis der Heap nur mehr ein Element enthält. Anschließend ermittelt die Routine Code_erstellen die Codes für jedes einzelne Zeichen. Baum_aufbauen erzeugt schließlich daraus den dazugehörigen Huffmann-Baum. Danach nimmt die Routine Codierung die eigentliche Codierung vor. Dabei muß natürlich auch der erzeugte Huffmann- Baum mitgespeichert werden, um eine Decodierung zu ermöglichen. Das verringert natürlich den Platzgewinn einer Huffmann-Codierung wieder. Aus diesem Grund werden sehr kurze Dateien durch die Codierung länger als das Original. Bei längeren Dateien macht sie sich aber schon stark bemerkbar. Die Decodierung ist vergleichsweise einfach. Nachdem der Huffmann-Baum in ein Array eingelesen wurde, wird mit seiner Hilfe eine zeichenweise Decodierung durchgeführt und das Ergebnis auf das Zielfile geschrieben. Interessant ist lediglich noch die Art der Speicherung des Huffmann-Baumes in den Beispielprogrammen. Wie erwähnt wird er als Array gespeichert, die Art der darin enthaltenen Informationen unterscheidet sich aber von der beim Heap verwendeten Speicherweise. Prinzipiell gehören jeweils zwei und zwei Einträge zusammen. Dabei wird immer der erste von beiden der Null zugeordnet und der zweite der Eins.

Wir beginnen bei der Decodierarbeit am Anfang des Arrays und lesen das erste Bit vom File. Ist es eine Null, lesen wir das 0. Element des Feldes, bei einer Eins das 1. Element. Hier unterscheiden wir dann zwischen einem positiven und einem negativen Feldelement. Wurde eine postitive Zahl ausgelesen, gibt sie das Element im Feld an, an dem mit der Decodierung fortgefahren werden soll. War es ein negativer Wert, dann wissen wir, daß wir ein Blatt erreicht und somit ein Zeichen fertig decodiert haben. In diesem Fall beginnen wir für das nächste Zeichen wieder am Anfang des Feldes.

In Abbildung 2 sehen Sie ganz unten wie der darüber gezeichnete Huffmann- Baum in einem Array gespeichert aussieht. Wenn Sie nun die Bitfolge 101 decodieren wollen, dann wählen Sie erstmals das Element 1 aus dem Feld (wegen Bit 1 am Anfang des Codes 101). Dieses hat den Wert 4, also setzen Sie Ihre Arbeit beim 4. Feldelement fort. Wir lesen nun das nächste Bit, eine Null. Somit lesen wir Element 4+0=4 aus dem Feld. Hier finden wir eine 6 als nächste Ausgangsposition vor. Wir holen nun das nächste Bit und erhalten wieder eine Eins. Aus diesem Grund lesen wir das Element Nummer 6+1=7 aus. Hier zeigt die negative Zahl -71 an, das wir am Ende des Baumes angelangt sind. Wenn wir diesen Wert negieren, erhalten wir 71, den ASCII- Code für F. Die ursprüngliche Bitfolge 101 steht also für das F. So einfach ist das. Gehen wir nun aber zum letzten Thema der heutigen Folge über. Mit den Suchbäumen haben wir ja schon recht mächtige Datenstrukturen kennengelernt, die das Auffinden eines bestimmten Schlüssels in sehr kurzer Zeit ermöglichen. Leider sind sie jedoch auch nicht universell zum Suchen geeignet. Deshalb wollen wir uns einmal mit einem Suchproblem beschäftigen, bei dem wir mangels Flexibilität auf die Verwendung von Bäumen verzichten müssen: das Auffinden von Textbausteinen in einem größeren Text. Stellen Sie sich vor, Sie müßten eine Textverarbeitung oder auch nur einen einfachen Editor schreiben. Da gehört eine Suchfunktion schon zum Standardrepertoire. Natürlich gibt es auch hier eine triviale Lösung, auf die jeder leicht kommt, der nur ein bißchen programmieren kann. Listing 3 zeigt eine solche brutale Methode, bei der einfach der zu durchsuchende String ab jedem Zeichen mit dem Muster verglichen wird. Dieser Algorithmus ist jedoch sehr langsam, da viele Zeichen öfter als einmal inspiziert werden müssen. Wenn wir zum Beispiel im String "halihalo" das Muster "halo" suchen, dann wird das naive Verfahren beim Vergleich des ersten Teilstrings "hali" mit dem Muster "halo" erst beim vierten Zeichen eine Abweichung feststellen. Danach beginnt es den Textstring ab dem zweiten Zeichen mit dem Muster zu vergleichen. Hier stellt es schon beim ersten Buchstaben einen Unterschied fest. Also wird der Vergleich ab dem dritten Zeichen in "halihalo" fortgesetzt. Erst wenn sich der Algorithmus auf diese Weise bis zum fünften Buchstaben in "halihalo" durchgearbeitet hat, kann er eine Übereinstimmung feststellen und bricht ab. Wenn Sie sich jedoch die Vorgangsweise des Programmes genauer ansehen, dann werden Sie feststellen, daß sowohl das 'a', also auch das 'l' und das nachfolgende 'i' aus "halihalo" mehrfach zum Vergleich herangezogen wurden. Der primitive Algorithmus ist also insofern dumm, als er nicht merkt, welche Zeichen im gerade betrachteten Text mit dem Muster schon übereingestimmt haben. Wir wollen nun eine bessere Variante besprechen, die Knuth-Morris-Pratt- Methode. Wo dessen Stärken liegen, betrachten wir am besten anhand eines Beispiels. Es soll das Wort "halihalo" im String "halihalihalo" gesucht werden.

Text: halihalihalo Muster: halihalo -------

Hier wird erst beim achten Zeichen eine Abweichung festgestellt. Das naive Verfahren fährt dann so fort:

Text: halihalihalo Muster: halihalo ------- halihalo halihalo halihalo halihalo --------

Hier werden sehr viele Vergleiche umsonst gemacht, die eingespart werden könnten, wenn das Programm wüßte, wo es im Falle einer Nichtübereinstimmung (Mismatch) mit dem Vergleich fortfahren soll. Genau dies wird im Verfahren von Knuth-Morris-Pratt verbessert. Bevor nämlich mit dem Vergleich selbst begonnen wird, führt das Programm eine (einmalige) Analyse des Musterstrings durch. Dabei wird nach allfälligen Präfixstücken in dem Muster gesucht. Präfixstrings sind Strings, die Anfangsstücke der Muster selbst sind. In unserem Beispiel ist z.B. der Teilstring "hal" ab dem fünften Zeichen ein Präfixstring von "halihalo". Diese Information wird in einem Feld abgelegt. Dabei wird aus Geschwindigkeitsgründen jedem einzelnen Buchstaben ein Wert zugewiesen, der angibt, der wievielte Buchstabe er in einem (allfälligen) Präfixstring ist. Für unsere Beispielmuster gilt:

Muster: halihalo next: 00001230

Das Feld trägt (analog zum Beispielprogramm in Listing 4) den Namen next, da es für die Berechnung der nächsten zu vergleichenden Position verwendet wird.

Wenn nun beim zeichenweisen Durchsuchen eines Textes ein Mismatch auftritt, gibt die entsprechende Zahl davor an, beim wievielten Zeichen im Muster mit dem Vergleich fortgesetzt werden soll. Betrachten wir dieses Verhalten wieder anhand unseres Beispieltextes:

Text: halihalihalo Muster: halihalo ------- next: 00001230

Der Mismatch tritt beim achten Buchstaben auf, da hier ein 'i' anstatt des geforderten 'o' gefunden wurde. Das Programm untersucht nun das next-Element davor und findet dort eine Drei. Diese Drei bedeutet, daß die letzten drei Buchstaben vor dem 'i' mit den ersten drei im Muster übereinstimmen. Wir haben also einen neuen Vergleichsanfang gefunden und fahren mit der Suche fort, indem wir den achten Buchstaben des Textes (wo ja der Mismatch auftrat) mit dem vierten im Muster vergleichen.

Text: halihalihalo Muster: halihalo --------

Auf diese Weise konnte eine Übereinstimmung festgestellt werden und der Algorithmus bricht ab. Wäre auch hier wieder ein Mismatch aufgetreten, müßten wir nocheinmal nach eben derselben Methode verfahren. Betrachten wir dazu einen etwas modifizierten Text:

Text: halihalohalihalihalohalihalo Muster: halihalohalihalo --------------- next: 0000123012345678 halihalohalihalo ------- 0000123012345678 halihalohalihalo ----------------

Beim ersten Vergleich tritt ein Mismatch im letzten Zeichen des Musters mit dem 16. Zeichen im Text auf. Eine Untersuchung des next-Feldes davor ergibt eine Sieben. Das bedeutet, die sieben Zeichen vor dem Mismatch stellen wieder einen Musteranfang dar ("halihal"). Wir wissen nun, daß wir beim nächsten Vergleich mit dem achten Zeichen im Muster fortfahren müssen. Wie aus obiger Darstellung aber leicht ersichtlich, kommt es aber auch hier zu einem Mismatch, und zwar gleich beim achten Zeichen im Muster. Das next- Feld davor ergibt hier eine Drei. Aus diesem Grund versuchen wir das Muster ab dem vierten Zeichen mit dem Text zu vergleichen, und siehe da, es klappt! Im Falle eines Mismatches muß also das next-Feld sooft ausgelesen werden, bis entweder eine Übereinstimmung festgestellt werden kann oder der Anfang des next-Feldes erreicht wird.

Beachten Sie bitte, daß die unterstrichenen Texte in der obigen Darstellung nicht nocheinmal mit dem vorgegebenen Text verglichen werden müssen, da das next-Feld schon angibt, daß sie übereinstimmen. Sie sehen also, daß beim Knuth-Morris-Pratt-Verfahren übereinstimmende Zeichen im Text niemals öfter als einmal untersucht werden müssen. Hier besteht auch der Geschwindigkeitsvoteil gegenüber der in Listing 3 verwendeten Methode. In Listing 4 finden Sie nun die bisher besprochene Theorie in ein Programm umgesetzt. Nehmen Sie es ruhig in ihre Bibliothekssammlung auf. Natürlich können Sie die Routinen auch in ihren Programmen verwenden, wenn Sie nicht wissen, wie der Algorithmus nun im Detail arbeitet. Wie man mit den einzelnen Funktionen umgeht, zeigt das Beispielprogramm. Damit wären wir am Ende des heutigen Kursteiles. Das nächste mal kommen wir zu einem völlig neuen Suchverfahren, den Hashtabellen.

Markus Öllinger ...........

Workshop Teil 1

Workshop Teil 3

Listing 4-1

Listing 4-2

Workshop Teil 2

Abb. 1

Abb. 2

Listing 4-3

Listing 4-4

....