Teilstringsuche aus einer Zeichenfolge
Eingabe: Zeichenfolge S = AAGATATGATAGGAT.
Ausgabe: Maximale Wiederholungen wie GATA (wie in den Positionen 3 und 8), GAT (wie in Position 3, 8 und 13) und so weiter ...
-
Eine maximale Wiederholung ist eine Teilzeichenkette t tritt in S 1 mal auf, und wenn t nach links oder rechts verlängert wird, wird sie weniger als k mal vorkommen.
-
Die Blattnachfahren eines internen Knotens sind Suffixe, von denen jedes ein linkes Zeichen hat.
-
Wenn die linken Zeichen aller Blattnachfahren nicht alle identisch sind, wird dies als "linker diversitärer" Knoten bezeichnet.
-
Maximale Wiederholungen sind links-diverse interne Knoten.
Allgemeine Idee:
-
Erstellen Sie einen Suffixbaum und führen Sie dann ein DFS (Tiefensuche) in der Baumstruktur
aus
-
Beschriften Sie jedes Blatt mit seinem linken Zeichen
-
Für jeden internen Knoten:
-
Wenn mindestens ein Kind mit * gekennzeichnet ist, beschriften Sie es mit *
-
Anderenfalls, wenn die Labels seiner Kinder verschiedenartig sind, mit * beschriften.
-
Sonst haben alle untergeordneten Elemente dasselbe Label, kopieren Sie es in den aktuellen Knoten
Ist die obige Idee richtig? Wie soll der Pseudocode sein? Dann kann ich versuchen, selbst programmieren zu schreiben.
1 Antwort
Ihre Idee ist gut, aber mit einem Suffixbaum können Sie etwas noch einfacher machen.
Sei T der Suffixbaum deiner Sequenz.
Sei x ein Knoten in T, T_x ist der Teilbaum von T mit Wurzel x.
Sei N_x die Anzahl der Blätter in T_x
Sei word (x) das Wort, das erzeugt wird, indem T von der Wurzel zum Knoten x durchquert wird.
Wenn wir nun die Definition eines Suffixbaums verwenden, erhalten wir:
Anzahl der Wiederholungen von Wort (x) = N_x und die Position dieser Wörter sind die Bezeichnung jedes Blattes
Der Algorithmus hierfür wäre eine grundlegende Baumdurchquerung, für jeden Knoten in dem Baum wird N_x berechnet, wenn N_x & gt; 2 füge das zu deinem Ergebnis hinzu (wenn du auch die Position haben willst, kannst du die Beschriftung jedes Blattes hinzufügen)
Pseudocode:
Eingabe:
mySequenz
Ausgabe:
Ergebnis (Liste der Wörter, die mit Anzahl und Position wiederholt werden)
Algorithmus:
T = suffixTree (meineSequenz)
Für jeden internen Knoten X in T:
%Vor%Ergebnis zurückgeben
Beispiel:
Nehmen wir das Wikipedia-Beispiel für Suffix-Bäume: "BANANA" :
wir bekommen:
%Vor%Ich habe dieses Papier gefunden, das Ihr Problem auf die gleiche Weise zu behandeln scheint, wie Sie es tun, also ja ich denke Ihre Methode ist schreiben:
Rechtschreibung wiederholter oder allgemeiner Motive unter Verwendung eines Suffixbaums
Extrahieren
Wir präsentieren in dieser Arbeit zwei Algorithmen. Der erste extrahiert Wiederholte Motive aus einer über einem Alphabet definierten Sequenz Sigma. Zum Zum Beispiel kann Sigma gleich {A, C, G, T} und der Sequenz sein repräsentieren eine Codierung eines DNA-Makromoleküls. Die Motive gesucht Wörter über dem gleichen Alphabet entsprechen, die ein Minimum auftreten Anzahl der Male in der Sequenz mit höchstens e Fehlpaarungen jedes Mal (q heißt Quorum-Einschränkung) [...]
Sie können es herunterladen und sehen, der Autor gibt Pseudo-Code für Ihren Algorithmus.
Hoffe das hilft
Tags und Links algorithm language-agnostic suffix-tree