Strings
- LZW-Komprimierung (Algorithmus 5.11)
Die LZW-Komprimierung aus Sedgewick/Wayne, Algorithmus 5.11 (Listing 5.41 und 5.42) – mit longestPrefixOf() im TST die längste bekannte Folge finden, ihr 12-Bit-Codewort schreiben und die Folge plus nächstes Zeichen neu eintragen; expand() baut die Tabelle beim Lesen wieder auf, samt der kniffligen Situation bei ABABABA.
- Huffman-Komprimierung (Algorithmus 5.10)
Die Huffman-Komprimierung aus Sedgewick/Wayne, Algorithmus 5.10 (Listing 5.33 bis 5.40) – Häufigkeiten zählen, mit einer Min-Vorrangwarteschlange den Trie bauen, Codewörter ablesen, Trie und Text als Bitfolge schreiben und mit expand() wieder lesen, am Beispiel ABRACADABRA! wie in Abbildung 5.65.
- Reguläre Ausdrücke mit NEA (Algorithmus 5.9)
Die musterbasierte Suche mit regulären Ausdrücken aus Sedgewick/Wayne, Algorithmus 5.9 (Listing 5.24 und 5.25) – den nichtdeterministischen Automaten mit einem Stapel aufbauen und dann alle möglichen Zustände gleichzeitig durch den Text schicken, am Beispiel ((A*B|AC)D) wie in Abbildung 5.51.
- Rabin-Karp (Algorithmus 5.8)
Die Rabin-Karp-Fingerprint-Suche aus Sedgewick/Wayne, Algorithmus 5.8 (Listing 5.21 und 5.22) – Hash des Musters nach dem Horner-Schema, dann ein rollender Hash über den Text, am Zahlenbeispiel 26535 in 3141592653589793 wie in Abbildung 5.47.
- Boyer-Moore (Algorithmus 5.7)
Die Teilstringsuche nach Boyer-Moore mit Vorkommensheuristik aus Sedgewick/Wayne, Algorithmus 5.7 (Listing 5.20) – das Muster von rechts nach links vergleichen und bei einer Abweichung weit springen, am Beispiel NEEDLE aus dem Buch.
- Knuth-Morris-Pratt (Algorithmus 5.6)
Die Knuth-Morris-Pratt-Teilstringsuche aus Sedgewick/Wayne, Algorithmus 5.6 (Listing 5.18) – erst den Automaten aus dem Muster bauen, dann den Text Zeichen für Zeichen hindurchschicken, ohne je zurückzulesen, am Testlauf AACAA aus dem Buch.
- TST-Symboltabelle (Algorithmus 5.5)
Der ternäre Suchtrie aus Sedgewick/Wayne, Algorithmus 5.5 (Listing 5.13) – pro Knoten ein Zeichen und drei Verweise statt R, put und get Zeichen für Zeichen, am TST aus Abbildung 5.29.
- Trie-Symboltabelle (Algorithmus 5.4)
Die Trie-Symboltabelle aus Sedgewick/Wayne, Algorithmus 5.4 (Listing 5.8 bis 5.10) – ein R-Wege-Trie mit put und get, dazu Schlüssel sammeln nach Präfix und nach Muster mit Platzhaltern, an „she sells sea shells by the sea shore“ wie in Abbildung 5.23.
- 3-Wege-Quicksort für Strings (Algorithmus 5.3)
Der 3-Wege-Quicksort für Strings aus Sedgewick/Wayne, Algorithmus 5.3 (Listing 5.6) – Partitionierung in kleiner, gleich und größer nach einem einzigen Zeichen, der Gleich-Teil geht mit dem nächsten Zeichen weiter, an „she sells seashells …“ wie in Abbildung 5.18.
- MSD-Sortierverfahren (Algorithmus 5.2)
Das MSD-Sortierverfahren aus Sedgewick/Wayne, Algorithmus 5.2 (Listing 5.4 und 5.5) – Strings beliebiger Länge vom ersten Zeichen aus sortiert, Gruppe für Gruppe rekursiv, mit Insertionsort für kleine Teilarrays, an „she sells seashells …“ wie in Abbildung 5.12 und 5.13.
- LSD-Sortierverfahren (Algorithmus 5.1)
Das LSD-Sortierverfahren aus Sedgewick/Wayne, Algorithmus 5.1 (Listing 5.3) – gleich lange Strings von der letzten Zeichenposition zur ersten sortiert, jeder Durchgang ein schlüsselindiziertes Zählen, an den 13 Kennzeichen aus dem Buch.