Definition - Länge der längsten gemeinsamen Teilfolge

• Generalisierungen:
  • Ähnlichkeitsmaß
• Involvierte Definitionen:
  • Zeichenkette
  • Teilfolge
  • siehe auch Levenshtein-Distanz
• Veranstaltung: DM
• Referenz: @valdes2025 (p. 40 f.)

⠀

Definition: Länge der längsten gemeinsamen Teilfolge

Als Länge der längsten gemeinsamen Teilfolge (en. Longest Common Subsequence, kurz LCS) bezeichnen wir ein gängiges Ähnlichkeitsmaß für Zeichenketten.

Dabei ist nach Definition der Teilfolge zu beachten, dass die Zeichen nicht zusammenhängend sein müssen - ihre Reihenfolge darf aber nicht verändert werden.

Das heißt: ist sowohl Teilfolge der Folge und der Folge .

Die Länge der längsten Teilfolge zweier Teilstrings erhalten wir rekursiv durch

Für die Basisfälle setzen wir:

Anmerkung

Berechnung der LCS mittels Matrixdarstellung

Die Berechnung der LCS können wir ähnlich durchführen wie die Berechnung der Levenshtein-Distanz zwischen zwei Strings.

Für die beiden Wörter BIENE und BEIN erhalten wir beispielsweise:

	#	B	E	I	N
#	0	0	0	0	0
B	0	1	1	1	1
I	0	1	1	2	2
E	0	1	2	2	2
N	0	1	2	2	3
E	0	1	2	2	3

Die LCS zwischen BIENE und BEIN beträgt also (entweder BIN oder BEN).