Mehrfach-Pattern-Matching mit DL-Distanz ≤ 1 in Python mit Suffixbaum

Einführung in das Mehrfach-Pattern-Matching mit DL-Distanz

In der Bioinformatik, Textverarbeitung und bei Suchmaschinen ist es oft nötig, mehrere Pattern in einer großen Textsammlung zu finden – und das mit einer gewissen Toleranz. Deine FIT3155 Assignment 2 verlangt genau das: DL-Distanz ≤ 1 (Damerau-Levenshtein-Distanz) für jedes Pattern. Das bedeutet, dass ein Pattern als Treffer gilt, wenn es im Text exakt oder mit einer einzigen Editieroperation (Einfügen, Löschen, Ersetzen oder Vertauschen zweier benachbarter Zeichen) vorkommt.

Warum ein Suffixbaum?

Ein Suffixbaum ist eine Datenstruktur, die alle Suffixe eines Textes in einer Baumstruktur speichert. Damit kannst du in O(m + Vorkommen) nach einem Pattern der Länge m suchen. Für DL-Distanz ≤ 1 erweiterst du die Suche, indem du an jedem Knoten mögliche Editierungen berücksichtigst – ohne den Baum neu aufzubauen. Das ist viel effizienter als Brute-Force.

Stell dir vor, du suchst in einem Chatverlauf nach dem Wort „KI“ mit Tippfehlern wie „K“ oder „I“ – der Suffixbaum findet beides schnell.

Aufbau eines Suffixbaums in Python

Wir bauen den Suffixbaum mit einer Knotenklasse. Jeder Knoten speichert Kinder (als Dictionary), den Startindex und die Länge des Kantenlabels sowie einen Link zum Suffix-Link (für spätere Erweiterungen).

class SuffixTreeNode:
    def __init__(self, start, length):
        self.start = start
        self.length = length
        self.children = {}
        self.suffix_link = None

Der eigentliche Baum wird mit Ukkonens Algorithmus in O(n) gebaut. Für Assignment 2 reicht es, einen einfachen Suffixbaum zu bauen – ohne Online-Features.

Suche mit DL-Distanz ≤ 1

Die Suche startet an der Wurzel. Wir führen eine Tiefensuche durch, wobei wir die aktuelle Distanz mitführen. Erlaubt sind 0 oder 1. An jedem Knoten vergleichen wir das Pattern mit dem Kantenlabel. Dabei zählen wir Editierungen:

• Match: Distanz bleibt gleich.
• Einfügen/Löschen/Ersetzen: Distanz +1, wenn ≤1.
• Vertauschen: Distanz +1, wenn zwei Zeichen vertauscht werden.

Ein Beispiel: Pattern „abc“ im Text „abdc“. An Position 1 (1-basiert) ist „abc“ mit Vertauschen von „c“ und „d“ zu „abd“ – Distanz 1, Treffer.

Implementierung der DL-Suche

def search_dl(node, pattern, text, pos, dist):
    if dist > 1:
        return
    if not pattern:
        # Pattern erschöpft → alle Blätter unter node sind Treffer
        collect_leaves(node, text, pos)
        return
    for char, child in node.children.items():
        label = text[child.start:child.start+child.length]
        # Vergleiche Zeichen für Zeichen
        ...

Die Funktion collect_leaves sammelt alle Blattpositionen (1-basiert) unter einem Knoten.

Einbindung mehrerer Texte und Pattern

Die Run-Konfigurationsdatei gibt die Dateinamen vor. Lies sie ein und baue für jeden Text einen eigenen Suffixbaum. Suche dann jedes Pattern in jedem Baum.

def read_config(filename):
    with open(filename) as f:
        lines = f.read().strip().split('\n')
    # erstes Pattern, dann Text
    ...

Beachte: Die Nummerierung in der Ausgabe folgt der Reihenfolge in der Config-Datei (1-basiert).

Optimierung für große Datenmengen

Ein Suffixbaum kann speicherhungrig sein. Verwende Dictionary für Kinder, aber nur wo nötig. Für die DL-Suche kannst du Pruning einsetzen: Sobald die Distanz 1 überschreitet, brich den Pfad ab.

Aktuell im Trend: KI-Chatbots wie ChatGPT nutzen ähnliche Algorithmen, um Tippfehler in Suchanfragen zu tolerieren. Dein Suffixbaum ist quasi ein Mini-Index dafür.

Beispiel aus der Praxis: Sport-Statistiken

Stell dir vor, du hast eine Textsammlung mit Spielberichten der Bundesliga und suchst nach dem Pattern „Tor“ mit DL ≤ 1. Ein Bericht enthält „Tor“ exakt, ein anderer „Toor“ (Tippfehler). Dein Suffixbaum findet beide.

Oder in der Finanzwelt: Suche nach Firmennamen mit Abweichungen wie „Apple“ vs. „Appple“ in Nachrichtenartikeln.

Häufige Fehler und Tipps

• Vergiss nicht die 1-basierte Position: Position 1 ist das erste Zeichen des Textes.
• Behandle das Ende-Zeichen $: Es kommt nicht in den Dateien vor, aber du kannst es intern anhängen, um Suffixe eindeutig zu machen.
• Teste mit kleinen Beispielen: Erstelle Text- und Pattern-Dateien mit 2-3 Zeichen, um die DL-Logik zu prüfen.

Fazit

Mit einem Suffixbaum und einer erweiterten Suche meisterst du die FIT3155 Assignment 2. Der Schlüssel liegt in der korrekten Implementierung der DL-Distanz und dem effizienten Durchlaufen des Baums. Nutze die Kraft der Datenstruktur – sie ist wie ein Superindex für deine Texte.

Viel Erfolg beim Programmieren!