Edit Distance und Longest Common Subsequence

Immer wieder ist es notwendig, zwei Strings miteinander zu vergleichen und festzustellen, wie ähnlich sie sich sind. Hierzu gibt es verschiedene Möglichkeiten, z. B. könnte man einfach die Länge beider Strings vergleichen oder ob sie die gleichen Buchstaben enthalten. Etwas komplizierter wird es, wenn man der Reihenfolge der Buchstaben eine Bedeutung zumisst. Dann könnte man prüfen, ob es eine Sequenz von Buchstaben gibt, die in beiden Strings in der gleichen Reihenfolge vorkommen. Die längste dieser Sequenzen ist die Longest Common Subsequence. Oder man überlegt sich, wie viele Editier-Operationen (Einfügen, Löschen, Ersetzen) notwendig sind, um aus dem ersten String den zweiten zu erzeugen. In diesem Artikel geht es um diese Algorithmen.

Edit Distance

Um aus einem String „A“ den String „AB“ zu machen, muss nur der Buchstabe ‚B‘ angehängt werden. Dies entspricht einer Edit Distance von 1. Möchte man aus dem String „BC“ den String „C“ machen, muss nur das erste Zeichen ‚B‘ entfernt werden. Und um aus „A“ den String „B“ zu erzeugen, muss der Buchstabe ersetzt werden. Man kann also leicht erkennen, dass die Anzahl der Operationen, die nötig sind um einen String A in einen String B zu transformieren genau so groß ist, wie um aus B A zu erzeugen.

Die Frage ist jetzt: mit welchem Algorithmus kann die Operationen möglichst effizient berechnet werden? Die Literatur empfiehlt her den Levenshtein-Algorithmus. Dieser bedient sich der Dynamischen Programmierung und zerlegt das Problem in Teilprobleme. Es wird eine Matrix aus beiden Strings gebildet, und die Werte der Edit Distance werden nacheinander eingetragen:

-ACHSE
-012345
L1
A2
S3
E4
R5

Der ‚-‚ steht für den leeren String. Um also aus dem leeren String einen String der Länge N zu machen, sind N Einfüge-Operationen notwendig. Deshalb wird die erste Zeile mit den Werten 0 bis N befüllt. Anders herum: um aus einem String mit M Zeichen einen leeren String zu erzeugen, müssen N Zeichen gelöscht werden. Deshalb ist die erste Spalte ebenfalls mit den Werten 0 bis M befüllt.

Nun werden die restlichen Zellen nach folgendem Algorithmus befüllt:
setzt
Wenn die Zeichen an der Kreuzungsstelle identisch sind (A(i) == B(j)), dann ist der neue Wert

c(i, j) = min( c(i - 1, j - 1), c(i, j - 1) + 1, c(i - 1, j) + 1 )

sonst

c(i, j) = min( c(i - 1, j - 1) + 1, c(i, j - 1) + 1, c(i - 1, j) + 1 )

Also ergibt sich folgendes Bild nach dem einige Werte berechnet wurden:

-ACHSE
-012345
L123456
A212345
S322334
E4
R5

Und schließlich sieht die vollständig gefüllte Matrix wie folgt aus:

-ACHSE
-012345
L123456
A212345
S322334
E433343
R544444

Der Wert rechts unten in der Matrix gibt die Edit Distance an. In unserem Beispiel ist es 4. Diese Zahl setzt sich zusammen aus den 2 Löschungen der Zeichen ‚L‘ und ‚R‘ aus dem String „LASER“ und den 2 Ergänzungen der Zeichen ‚C‘ und ‚H‘ im String „ACHSE“.

In Scala sieht der Algorithmus dann so aus:

class EditDistance( val text: String ) {
	def distanceTo( otherText: String ): Int = {
		Levenshtein.distance( text, otherText )
	}
}

object EditDistance {
	import scala.language.implicitConversions
	implicit def stringToLevenshtein( str: String ) = new EditDistance( str )
}

object Levenshtein {
	private def min( nums: Int* ): Int = nums.min
	
	def distance( first: String, second: String ): Int = {
		lastDistanceLine( first, second ).last
	}
	
	protected[distance] 
	def lastDistanceLine( first: String, second: String ): Array[Int] = {
		val line = Range( 0, second.length() + 1 ).toArray

		@tailrec
		def computeNextLine( indexOfFirst: Int ): Array[Int] = {
			def costIfReplacement( first: Char, second: Char ): Int = if ( first == second ) 0 else 1

			@tailrec
			def computeDistancesOfLine( index: Int, left: Int, top: Int ) {
				if ( index <= second.length() ) {
					val newTop = line( index )
					line( index ) = min(
						top + costIfReplacement( first( indexOfFirst - 1 ), second( index - 1 ) ),
						line( index ) + 1,
						left + 1 )
					computeDistancesOfLine( index + 1, line( index ), newTop )
				}
			}

			if ( indexOfFirst > first.length() ) {
				line
			} else {
				val oldLine0 = line( 0 )
				line( 0 ) = line( 0 ) + 1

				computeDistancesOfLine( 1, line( 0 ), oldLine0 )
				computeNextLine( indexOfFirst + 1 )
			}
		}

		computeNextLine( 1 )
	}
}

Wenn ihr euch jetzt fragt, wo denn die Matrix ist: diese ist den Einsparmaßnahmen zum Opfer gefallen. Insbesondere bei langen Strings (z. B. bei DNA-Sequenzen) die gerne Tausende oder Millionen von Zeichen enthalten, wäre die Matrix so riesig, dass selbst moderne PCs sie nicht mehr aufnehmen könnten.

Es wurde also ein Trick verwendet. Aus der vorhergehenden Zeile kann die nächste berechnet werden, ohne dass weitere Zeilen benötigt werden. Also kommt man ganz gut mit 2 Zeilen aus. Der obige Algorithmus ist noch sparsamer, denn er verwendet nur eine Zeile und merkt sich lediglich die alten Werte links und links oberhalb des aktuellen Eintrags um diesen zu berechnen.

Longest Common Subsequence

Wenn man sich das vorhergehende Beispiel ansieht, stellt man fest, dass die Zeichen ‚A‘, ‚S‘ und ‚E‘ in dieser Reihenfolge in beiden Strings auftreten und von den Veränderungen beim Editieren nicht direkt betroffen sind. Statt dessen werden die anderen Zeichen entweder hinzugefügt, gelöscht oder geändert. Es handelt sich also um die längste Sequenz von Zeichen, die in beiden Strings vorkommt: also die Longest Common Subsequence (im Folgenden LCS genannt).

Der Levenshtein-Algorithmus führt also auch zur LCS. Eine effiziente Implementierung ist der Hirschberg-Algorithmus, den ich nun als Scala-Programm vorstellen möchte. Die genaue Wirkungsweise wird sehr gut im Wikipedia-Artikel dargestellt und ich habe versucht, den Grundgedanken im Code einzufangen:

class LongestCommonSubsequence( val text: String ) {
	def lcsWith( otherText: String ): String = Hirschberg.lcsOf( text, otherText )
}

object LongestCommonSubsequence {
	import scala.language.implicitConversions
	implicit def stringToHirschberg( text: String ) = new LongestCommonSubsequence( text )
}

object Hirschberg {
	def lcsOf( text1: String, text2: String ): String = {
		def lcs( shortText: String, longText: String ): String = {
			if ( shortText.length == 0 ) ""
			else if ( shortText.length == 1 ) {
				if ( longText.contains( shortText ) ) shortText
				else ""
			} else {
				val middle = longText.length / 2
				val longTextFirstPart = longText.substring( 0, middle )
				val longTextSecondPart = longText.substring( middle )

				val scoreLeft = Levenshtein.lastDistanceLine( longTextFirstPart, shortText )
				val scoreRight = Levenshtein.lastDistanceLine( longTextSecondPart.reverse, shortText.reverse )

				val cut = findCut( scoreLeft, scoreRight )

				val shortTextFirstPart = shortText.substring( 0, cut )
				val shortTextSecondPart = shortText.substring( cut )

				lcsOf( longTextFirstPart, shortTextFirstPart ) +
					lcsOf( longTextSecondPart, shortTextSecondPart )
			}
		}

		val result = if ( text1.length < text2.length ) lcs( text1, text2 )
		else lcs( text2, text1 )
		result
	}

	import scala.annotation.tailrec

	private def findCut( line1: Array[Int], line2: Array[Int] ): Int = {
		val lastIndex = line1.length - 1
		def computeDistanceSum( index: Int ) = line1( index ) + line2( lastIndex - index )

		@tailrec
		def findMin( index: Int, oldMin: Int, oldMinIndex: Int ): Int = {
			if ( index > lastIndex ) oldMinIndex
			else {
				val distanceSum = computeDistanceSum( index )
				if ( distanceSum < oldMin ) findMin( index + 1, distanceSum, index )
				else findMin( index + 1, oldMin, oldMinIndex )
			}
		}

		findMin( 1, computeDistanceSum( 0 ), 0 )
	}
}

Wie ihr sehen könnt, verwendet der Hirschberg-Algorithmus einen Teil des Levenshtein-Algorithmus, der die letzte Zeile der Levenshtein-Matrix berechnet. Die Implementierung verschwendet etwas Zeit, um die Reversen von Teil-Strings zu berechnen. Dies ließe sich umgehen, in dem ein Pendant zum Levenshtein-Algorithmus erstellt würde, der rückwärts die Edit Distance berechnet. Das sieht für mich aber sehr unelegant aus und da wir hier nicht den LCS von extrem langen Zeichenketten berechnen wollen, habe ich es so belassen. Sollte der Code produktiv eingesetzt werden, empfehle ich eine C / C++ Implementierung zu verwenden.

Ich möchte darauf hinweisen, dass der Code vollständig auf Schleifen verzichtet und statt dessen rekursive Funktionen verwendet. Besonders einfach wird - meines Erachtens nach - die Implementierung der Funktion lcsOf; allerdings gibt es keine elegante Möglichkeit dies in eine Tail-Rekursive Funktion umzuwandeln. Mit Scala-Mitteln lässt sich die Funktion findCut in einen Einzeiler verwandeln. Hierzu müsste man Funktionen wie map, foldLeft und zip einsetzen. Da dies zu Lasten des Arbeitsspeichers geht, der hier für mich besonders relevant ist, habe ich darauf verzichtet. Es ist dem geneigten Leser überlassen, hier eine bessere Implementierung zu versuchen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.