Tag Archives: lcs

In diesem Beitrag beschreibe ich einen Algorithmus zur Lösung des größten häufigen Teilstringproblems. Nehmen wir an, wir versuchen, verschlüsselte Binärdaten zu entschlüsseln. Versuchen wir zunächst, gemeinsame Muster zu finden, indem wir nach der größten Teilzeichenfolge suchen.
Beispiel-Eingabezeichenfolge:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Wir suchen nach einer Zeichenfolge, die sich zweimal wiederholt:
DATAHEADER??

Präfixe

Schreiben wir zunächst eine Methode zum Vergleichen der Präfixe zweier Zeichenfolgen und lassen Sie sie die resultierende Zeichenfolge zurückgeben, in der die Zeichen des linken Präfixes den Zeichen des rechten Präfixes entsprechen.
Zum Beispiel für die Zeilen:

        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

Ergebniszeichenfolge – asdf
Beispiel in Kotlin:

fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Brute Force

Wenn etwas nicht klappt, sollten Sie zu roher Gewalt greifen. Mit der longestPrefix-Methode durchlaufen wir die Zeichenfolge in zwei Schleifen. Die erste Schleife nimmt die Zeichenfolge von i bis zum Ende, die zweite von i + 1 bis zum Ende und gibt sie weiter, um nach dem größten Präfix zu suchen. Die zeitliche Komplexität dieses Algorithmus beträgt ungefähr O(n^2) ~ O(n*^3).
Beispiel in Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Suffix-Array

Für eine elegantere Lösung benötigen wir ein Werkzeug – eine Datenstruktur namens „Suffix Array“. Diese Datenstruktur ist ein Array von Teilzeichenfolgen, die in einer Schleife gefüllt werden, wobei jede Teilzeichenfolge vom nächsten Zeichen der Zeile bis zum Ende beginnt.
Zum Beispiel für die Zeile:

adasDATAHEADER??

Das Suffix-Array sieht folgendermaßen aus:

adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?

Wir lösen durch Sortieren

Sortieren wir das Suffix-Array, gehen wir dann alle Elemente in einer Schleife durch, wobei sich das aktuelle Element in der linken Hand (links) und das nächste in der rechten Hand (rechts) befindet, und berechnen wir das längste Präfix mithilfe des longestPrefix Methode.
Beispiel in Kotlin:

fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

Die zeitliche Komplexität des Algorithmus beträgt O(N log N), was viel besser ist als eine einfache Lösung.

Quellen

https://en.wikipedia.org/wiki/Longest_common_substring_problem

Quellcode

https://gitlab.com/demensdeum/algorithms