Kapitel 6: Strings in Algorithmen

Strings sind ein grundlegender Datentyp in der Informatik und stellen Zeichenfolgen dar. Das Studium von Algorithmen und Datenstrukturen für die Verarbeitung von Strings ist ein entscheidender Teil jedes Informatik-Curriculums. In diesem Kapitel untersuchen wir mehrere wichtige String-Verarbeitungs-Algorithmen, darunter String-Sortierung, Tries, Substring-Suche, reguläre Ausdrücke und Datenkompression. Diese Algorithmen haben zahlreiche praktische Anwendungen, von der Textbearbeitung und Dokumentensuche bis hin zur Bioinformatik und Verarbeitung natürlicher Sprachen.

String-Sortierung

Das Sortieren ist eine grundlegende Operation in der Informatik, und das Sortieren von Strings ist eine häufige Aufgabe in vielen Anwendungen. Während allgemeine Sortieralgorithmen wie Quicksort und Mergesort verwendet werden können, um Strings zu sortieren, gibt es effizientere Algorithmen, die die besonderen Eigenschaften von Strings ausnutzen.

Key-Indexed Counting

Key-Indexed Counting ist ein einfacher und effizienter Algorithmus zum Sortieren von Strings, die aus einem kleinen Satz von unterschiedlichen Zeichen bestehen. Die Grundidee ist, die Anzahl der Vorkommen jedes Zeichens zu zählen und dann diese Zählungen zu verwenden, um die Position jedes Strings in der sortierten Reihenfolge zu bestimmen.

Hier ist ein Beispiel für Key-Indexed Counting in Aktion:

Eingabe:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Ausgabe: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Der Algorithmus funktioniert wie folgt:

Zähle die Häufigkeit jedes Zeichens in den Strings.
Berechne den Startindex für jedes Zeichen im sortierten Array.
Kopiere die Strings in das sortierte Array, wobei die Zählungen verwendet werden, um die Positionen zu bestimmen.

Key-Indexed Counting läuft in O(n + R) Zeit ab, wobei n die Gesamtzahl der Zeichen in den Strings und R die Größe des Alphabets (die Anzahl der unterschiedlichen Zeichen) ist. Dies macht es zu einem sehr effizienten Algorithmus zum Sortieren von Strings mit einer kleinen Alphabetgröße.

LSD Radix Sort

Least-Significant-Digit-First (LSD) Radix Sort ist eine Erweiterung von Key-IndexedHier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst blieb unverändert.

Zählen, das Zeichenketten gleicher Länge über einem großen Alphabet sortieren kann. Die grundlegende Idee ist, die Zeichenketten von hinten nach vorne, also vom letzten Zeichen zum ersten, zeichenweise zu sortieren.

Hier ist ein Beispiel für die LSD-Radixsortierung:

Eingabe:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Ausgabe: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Der Algorithmus funktioniert wie folgt:

Sortiere die Zeichenketten nach dem letzten Zeichen mit Hilfe der schlüsselindexierten Zählung.
Wiederhole Schritt 1 für jedes Zeichen, wobei du dich zum ersten Zeichen bewegst.

Die LSD-Radixsortierung läuft in O(w * n) Zeit, wobei w die Länge der Zeichenketten und n die Anzahl der Zeichenketten ist. Dies macht sie zu einer effizienten Wahl für das Sortieren von Zeichenketten mit fester Länge.

MSD-Radixsortierung

Die Radixsortierung von links nach rechts (MSD, Most-Significant-Digit-first) ist eine rekursive Variante der Radixsortierung, die auch Zeichenketten unterschiedlicher Länge verarbeiten kann. Ähnlich wie beim Quicksort teilt die MSD-Radixsortierung das Array in Teilarrays auf, die unabhängig voneinander sortiert werden können.

Hier ist ein Beispiel für die MSD-Radixsortierung:

Eingabe:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Ausgabe: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

Der Algorithmus funktioniert wie folgt:

Teile das Array in Teilarrays auf, basierend auf dem ersten Zeichen jeder Zeichenkette.
Sortiere jedes Teilarray rekursiv.

Die MSD-Radixsortierung hat eine Worst-Case-Laufzeit von O(n * w), ist in der Praxis aber oft schneller als die LSD-Radixsortierung für Zeichenketten unterschiedlicher Länge.

Tries

Ein Trie (ausgesprochen "try") ist eine baumähnliche Datenstruktur zum Speichern von Zeichenketten, die eine effiziente Präfixsuche und Zeichenkettensuche ermöglicht. Jeder Knoten in einem Trie repräsentiert ein Zeichen, und der Pfad vom Wurzelknoten zu einem Knoten stellt einen Präfix derHier ist die deutsche Übersetzung der Markdown-Datei mit den Zeichenketten, die in dem Trie gespeichert sind:

Hier ist ein Beispiel für einen Trie, der die Zeichenketten "sea", "sells", "she", "shells" und "shore" speichert:

     (Wurzel)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

Tries unterstützen die folgenden Operationen:

Einfügen einer Zeichenkette in den Trie.
Suchen nach einer Zeichenkette im Trie.
Löschen einer Zeichenkette aus dem Trie.
Finden aller Zeichenketten mit einem bestimmten Präfix.

Die Zeitkomplexität dieser Operationen ist O(w), wobei w die Länge der Zeichenkette ist, die eingefügt, gesucht oder gelöscht wird. Dies macht Tries zu einer sehr effizienten Datenstruktur für zeichenkettenbasierte Aufgaben.

Teilstringsuche

Die Teilstringsuche ist das Problem, alle Vorkommen eines Musterstrings innerhalb eines größeren Textstrings zu finden. Dies ist ein grundlegendes Problem in der Zeichenkettenverarbeitung mit Anwendungen in der Textbearbeitung, Bioinformatik und vielen anderen Bereichen.

Brute-Force-Suche

Der einfachste Ansatz für die Teilstringsuche ist der Brute-Force-Algorithmus, der jede mögliche Position im Text auf eine Übereinstimmung mit dem Muster überprüft.

Hier ist ein Beispiel für die Brute-Force-Suche:

Text:    "abacadabrabracabracadabrabrabracad"
Muster: "abracadabra"
Ausgabe: [13]

Der Brute-Force-Algorithmus hat eine Worst-Case-Laufzeit von O(n * m), wobei n die Länge des Texts und m die Länge des Musters ist. Obwohl einfach zu implementieren, kann dies für große Texte und Muster ineffizient sein.

Knuth-Morris-Pratt-Algorithmus

Der Knuth-Morris-Pratt-Algorithmus (KMP) ist ein effizienter Teilstringsuche-Algorithmus, der eine vorkompilierte "Fehlerfunktion" verwendet, um unnötige Vergleiche zu vermeiden.

Die Fehlerfunktion sagt uns die Länge des längsten richtigen Präfixes des Musters, das auch ein Suffix des Teilstrings des Musters ist, den wir bisher abgeglichen haben. Dies ermöglicht es uns, beim Finden einer Nichtübereinstimmung "im Text vorwärts zu springen", anstatt zurückzugehen.

Hier ist ein Beispiel für den KMP-Algorithmus:

Text:    "abacadabrabrHier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst blieb unverändert.

acabracadabrabrabracad"
Muster: "abracadabra"
Ausgabe: [13]

Der KMP-Algorithmus hat eine Laufzeit von O(n + m), was ihn viel effizienter macht als der brute-force-Ansatz für große Texte und Muster.

Boyer-Moore-Algorithmus

Der Boyer-Moore-Algorithmus ist ein weiterer effizienter Teilzeichenketten-Suchalgorithmus, der durch Vorverarbeitung der Musterzeichenkette funktioniert. Im Gegensatz zum KMP, der die Vergleiche vom Anfang des Musters aus beginnt, startet Boyer-Moore vom Ende und arbeitet rückwärts.

Die Schlüsselidee hinter Boyer-Moore sind zwei vorberechnete Funktionen: die "gute Suffix"-Funktion und die "schlechte Zeichen"-Funktion. Diese Funktionen ermöglichen es uns, ähnlich wie beim KMP, bei einem Mismatch im Text vorwärts zu springen.

Hier ist ein Beispiel für den Boyer-Moore-Algorithmus:

Text:    "abacadabrabracabracadabrabrabracad"
Muster: "abracadabra"
Ausgabe: [13]

Boyer-Moore hat eine beste Laufzeit von O(n/m) und eine schlechteste Laufzeit von O(n * m), in der Praxis ist er jedoch oft der schnellste Teilzeichenketten-Suchalgorithmus für große Alphabete.

Reguläre Ausdrücke

Reguläre Ausdrücke sind ein leistungsfähiges Werkzeug, um Muster in Zeichenketten zu beschreiben. Sie bieten eine prägnante und flexible Notation zum Abgleichen, Suchen und Manipulieren von Text.

Ein regulärer Ausdruck ist eine Folge von Zeichen, die ein Suchmuster definieren. Die einfachste Form eines regulären Ausdrucks ist eine wörtliche Zeichenkette wie "hallo", die genau die Zeichenkette "hallo" abgleicht. Reguläre Ausdrücke umfassen jedoch auch Sonderzeichen und Konstrukte, die komplexere Muster ermöglichen:

. (Punkt) stimmt mit jedem einzelnen Zeichen überein.
* (Stern) stimmt mit null oder mehr Vorkommen des vorhergehenden Zeichens oder der Gruppe überein.
+ (Plus) stimmt mit einem oder mehr Vorkommen des vorhergehenden Zeichens oder der Gruppe überein.
? (Fragezeichen) stimmt mit null oder einem Vorkommen des vorhergehenden Zeichens oder der Gruppe überein.
^ (Dach) stimmt mit dem Beginn einer Zeile überein.
$ (Dollar) stimmt mit dem Ende einer Zeile überein.
[] (eckige Klammern) definieren eine Zeichenklasse, die mit einem einzelnen Zeichen übereinstimmt.Hier sind einige Beispiele für reguläre Ausdrücke und die Muster, die sie abgleichen:
a.b entspricht jeder Zeichenkette mit drei Zeichen, die mit "a" beginnt und mit "b" endet, wie z.B. "acb", "a5b" oder "a b".
a*b entspricht jeder Zeichenkette, die aus null oder mehr "a"-Zeichen gefolgt von einem einzelnen "b"-Zeichen besteht, wie z.B. "b", "ab", "aab" oder "aaab".
a+b entspricht jeder Zeichenkette, die aus einem oder mehr "a"-Zeichen gefolgt von einem einzelnen "b"-Zeichen besteht, wie z.B. "ab", "aab" oder "aaab", aber nicht "b".
a?b entspricht entweder "ab" oder "b".
^a entspricht jeder Zeichenkette, die mit "a" beginnt.
a$ entspricht jeder Zeichenkette, die mit "a" endet.
[aeiou] entspricht einem einzelnen Vokalzeichen.

Reguläre Ausdrücke werden von vielen Programmiersprachen und Tools unterstützt, darunter Java, Python und Unix-Dienstprogramme wie grep und sed. Sie werden häufig für Aufgaben wie Dateneingabevalidierung, Textverarbeitung und Protokollanalyse verwendet.

Datenkompression

Datenkompression ist der Prozess der Codierung von Informationen unter Verwendung von weniger Bits als die ursprüngliche Darstellung. Dies ist nützlich, um Speicheranforderungen und Übertragungszeiten zu reduzieren. Es gibt zwei Hauptarten der Kompression: verlustfrei und verlustbehaftet. Verlustfreie Kompression ermöglicht es, die ursprünglichen Daten perfekt aus den komprimierten Daten zu rekonstruieren, während verlustbehaftete Kompression einen gewissen Informationsverlust gegen höhere Kompressionsraten zulässt.

Laufzeitcodierung

Laufzeitcodierung (RLE) ist eine einfache verlustfreie Kompressionstechnik, die wiederholte Sequenzen identischer Symbole (Läufe) durch eine einzelne Instanz des Symbols und eine Zählung der Anzahl der Wiederholungen ersetzt.

Hier ist ein Beispiel für RLE:

Eingabe:  "AAAABBBCCCDDDEEE"
Ausgabe: "4A3B3C3D3E"

RLE ist effektiv für Daten mit vielen langen Läufen, wie einfache Grafikbilder. Es kann jedoch tatsächlich die Größe der Daten erhöhen, wenn es nur wenige oder keine Läufe gibt.

Huffman-Codierung

Huffman-Codierung ist ein verlustfreier Kompressionsalgorithmus, der variabel lange Codes an Symbole basierend auf ihrer Häufigkeit zuweist.Hier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst wurde nicht übersetzt.

Häufigkeiten in den Eingabedaten. Häufigere Symbole werden kürzeren Codes zugewiesen, während weniger häufige Symbole längeren Codes zugewiesen werden.

Der Algorithmus funktioniert, indem er von unten nach oben einen binären Baum, genannt Huffman-Baum, aufbaut. Jeder Blattknoten repräsentiert ein Symbol und seine Häufigkeit, während jeder innere Knoten die Summe der Häufigkeiten seiner Kinder darstellt. Der Baum wird konstruiert, indem wiederholt die beiden Knoten mit den niedrigsten Häufigkeiten zusammengeführt werden, bis nur noch ein Knoten übrig bleibt.

Sobald der Baum erstellt ist, wird der Code für jedes Symbol durch den Pfad von der Wurzel zum entsprechenden Blattknoten bestimmt, wobei ein linker Zweig für eine "0" und ein rechter Zweig für eine "1" steht.

Hier ist ein Beispiel für Huffman-Codierung:

Eingabe:  "AAAABBBCCCDDDEEE"
Ausgabe: "000010011001011100101"

Huffman-Baum:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

In diesem Beispiel wird "A" der Code "00", "B" der Code "01", "C" der Code "10", "D" der Code "110" und "E" der Code "111" zugewiesen. Die komprimierte Ausgabe wird erhalten, indem jedes Symbol in der Eingabe durch seinen entsprechenden Code ersetzt wird.

Huffman-Codierung ist ein optimaler Präfixcode, d.h. kein Code ist Präfix eines anderen Codes. Dies ermöglicht eine eindeutige Dekodierung der komprimierten Daten. Huffman-Codierung wird in verschiedenen Dateiformaten und Kompressionstools wie JPEG, MP3 und ZIP weit verbreitet eingesetzt.

LZW-Kompression

Lempel-Ziv-Welch (LZW) Kompression ist ein wörterbuchbasierter Kompressionsalgorithmus, der während der Kompression ein Wörterbuch (oder Codebuch) von Zeichenketten aufbaut. LZW wird in Dateikompressionsprogrammen weit verbreitet eingesetzt und wurde im GIF-Bildformat verwendet.

Die Schlüsselidee hinter LZW ist es, Zeichenketten durch einzelne Codes zu ersetzen. Es liest die Eingabezeichenkette Zeichen für Zeichen und codiert die Zeichenkette in eine kompakte Darstellung, indem es jeden festlängencode durch einen variabellängencode ersetzt. Je länger die Zeichenkette, desto mehr Platz wird durch die Codierung als einzelne Zahl gespart.

Hier ist einHier ist die deutsche Übersetzung der Markdown-Datei mit Kommentarübersetzung für den Code:

Schrittweise Beschreibung, wie die LZW-Kompression funktioniert:

Initialisiere das Wörterbuch, um alle Zeichenketten mit einem einzigen Zeichen zu enthalten.
Finde die längste Zeichenkette W im Wörterbuch, die mit der aktuellen Eingabe übereinstimmt.
Gib den Wörterbuchindex für W als Ausgabe aus und entferne W aus der Eingabe.
Füge W gefolgt vom nächsten Symbol in der Eingabe zum Wörterbuch hinzu.
Gehe zu Schritt 2.

Betrachten wir ein Beispiel. Angenommen, wir möchten die Zeichenkette "ABABABABA" mit LZW komprimieren.

Initialisiere das Wörterbuch mit "A" und "B".
Die längste Übereinstimmung ist "A". Gib ihren Index (0) aus und entferne sie aus der Eingabe. Das Wörterbuch enthält nun "A", "B" und "AB".
Die längste Übereinstimmung ist "B". Gib ihren Index (1) aus und entferne sie aus der Eingabe. Das Wörterbuch enthält nun "A", "B", "AB" und "BA".
Die längste Übereinstimmung ist "AB". Gib ihren Index (2) aus und entferne sie aus der Eingabe. Das Wörterbuch enthält nun "A", "B", "AB", "BA" und "ABA".
Die längste Übereinstimmung ist "ABA". Gib ihren Index (4) aus und entferne sie aus der Eingabe. Das Wörterbuch enthält nun "A", "B", "AB", "BA", "ABA" und "ABAB".
Die längste Übereinstimmung ist "BA". Gib ihren Index (3) aus. Die Eingabe ist nun leer.

Die komprimierte Darstellung von "ABABABABA" ist somit die Folge der Indizes [1], die weniger Bits zur Darstellung benötigt als die ursprüngliche ASCII-Darstellung.

Die Dekompression funktioniert ähnlich, aber in umgekehrter Reihenfolge:

Initialisiere das Wörterbuch mit allen Zeichenketten mit einem einzigen Zeichen.
Lies einen Code X aus der Eingabe.
Gib die Zeichenkette für X aus dem Wörterbuch aus.
Wenn der vorherige Code vorhanden ist, füge die vorherige Zeichenkette, gefolgt vom ersten Zeichen der Zeichenkette für X, zum Wörterbuch hinzu.
Gehe zu Schritt 2.

Die LZW-Kompression ist einfach und schnell, was sie für viele Anwendungen zu einer guten Wahl macht. Sie hat jedoch auch einige Einschränkungen. Die Größe des Wörterbuchs kann recht groß werden und einen erheblichen Speicherverbrauch verursachen. Außerdem wird das Wörterbuch nach jedem Eingabeblock zurückgesetzt, was das KompressionsverHier ist die deutsche Übersetzung der Markdown-Datei. Für den Code wurden nur die Kommentare übersetzt, der Code selbst blieb unverändert.

Zusammenfassung

In diesem Kapitel haben wir mehrere wichtige String-Verarbeitungsalgorithmen untersucht, darunter String-Sortierung, Tries, Substring-Suche, reguläre Ausdrücke und Datenkompression. Diese Algorithmen bilden die Grundlage für viele reale Anwendungen und sind unerlässliche Werkzeuge für jeden Programmierer, der mit Textdaten arbeitet.

Wir haben zunächst die String-Sortierung besprochen, die optimierte Sortieralgorithmen sind, die die besonderen Eigenschaften von Strings ausnutzen. Key-Indexed Counting, LSD Radix Sort und MSD Radix Sort bieten effiziente Methoden zum Sortieren von Strings basierend auf ihren einzelnen Zeichen.

Als Nächstes haben wir Tries, eine baumähnliche Datenstruktur zum Speichern und Abrufen von Strings, untersucht. Tries ermöglichen schnelles Präfixmatching und werden häufig in Anwendungen wie Autovervollständigung und IP-Routing-Tabellen verwendet.

Substring-Suchalgorithmen wie Knuth-Morris-Pratt und Boyer-Moore ermöglichen es uns, effizient nach Mustern in größeren Strings zu suchen. Diese Algorithmen haben zahlreiche Anwendungen in der Textbearbeitung, Bioinformatik und Informationssuche.

Reguläre Ausdrücke bieten eine leistungsfähige und flexible Möglichkeit, Stringmuster zu beschreiben. Wir haben die grundlegende Syntax regulärer Ausdrücke besprochen und wie sie in verschiedenen Programmiersprachen und Tools für Musterabgleich und Stringmanipulation verwendet werden können.

Schließlich haben wir Datenkompressionsalgorithmen untersucht, die die Größe von Daten durch Ausnutzung von Redundanz und Mustern im Eingabematerial reduzieren. Wir haben Run-Length Encoding, Huffman-Codierung und Lempel-Ziv-Welch-Kompression behandelt, von denen jede ihre eigenen Stärken und Anwendungen hat.

Das Verständnis dieser String-Verarbeitungsalgorithmen und Datenstrukturen ist entscheidend für jeden, der mit Textdaten arbeitet. Da die Menge an unstrukturierten Daten weiter wächst, ist die Fähigkeit, Textdaten effizient zu manipulieren, zu durchsuchen und zu komprimieren, von großer Bedeutung.Here is the German translation of the provided text, with the code comments translated:

Pressetexte werden nur noch wertvoller werden. Durch die Beherrschung der in diesem Kapitel behandelten Techniken werden Sie gut gerüstet sein, um eine Vielzahl von Herausforderungen bei der Textverarbeitung in Ihren eigenen Projekten und Anwendungen zu bewältigen.

# Definiere eine Funktion, die einen String als Eingabe nimmt
def process_string(input_string):
    # Konvertiere den String in Großbuchstaben
    uppercase_string = input_string.upper()
    
    # Zähle die Anzahl der Vorkommen jedes Buchstabens
    letter_counts = {}
    for char in uppercase_string:
        if char.isalpha():
            if char in letter_counts:
                letter_counts[char] += 1
            else:
                letter_counts[char] = 1
    
    # Sortiere die Buchstaben nach Häufigkeit in absteigender Reihenfolge
    sorted_counts = sorted(letter_counts.items(), key=lambda x: x[1], reverse=True)
    
    # Gib die sortierten Buchstaben und ihre Häufigkeiten aus
    for letter, count in sorted_counts:
        print(f"{letter}: {count}")
 
# Rufe die Funktion mit einem Beispielstring auf
process_string("Hello, World!")

Chapter 5 Graphs Chapter 7 Context