Textalgorithmen

Das entsprechende Suchmuster wird im gesamten Text gesucht und gibt die Startposition des Suchmusters innerhalb des Textes zurück oder -1 bei Nichtauffinden des Musters. Dieser Algorithmus gehört zu den effizientesten Algorithmen für die exakte Suche und besitzt eine Laufzeitkomplexität von O(n/m).

Dieser Algorithmus zählt die Anzahl der gemeinsamen Zeichen innerhalb zweier Zeichenketten und kann als Validierungsgröße beim ungefähren Zeichenkettenvergleich verwendet werden. Die Laufzeitkomplexität liegt bei O(n*m).

Dieser Algorithmus berechnet die Anzahl aller Zeichen von allen identischen Teilstrings der Eingabestrings. Identische Einzelzeichen werden nicht berücksichtigt.

Dieser Algortihmus berechnet die Anzahl aller Zeichen des längsten gemeinsamen Teilstrings der Eingabestrings.

Die oft nur als Editierdistanz bezeichnete Levenshtein distance wurde 1965 von Vladimir Levenshtein erstmals erwähnt. Dabei wird die Anzahl der notwendigen Änderungen ermittelt, um beide Strings aneinander anzugleichen. Gilt trotz der Laufzeitkomplexität von O(n*m) als sehr effizient.

Wie Levenshtein, jedoch mit der Optimierung, dass zwei auffeinanderfolgende vertauschte Zeichen berücksichtigt werden. Die Laufzeitkomplexität liegt bei O(n*m).

Ermittelt den Ähnlichkeitsgrad zweier Eingabestrings auf Basis der Levenshtein Distanz und der Länge der Eingabestrings. Die Laufzeitkomplexität liegt ebenfalls bei O(n*m).

Ist ein Maß für die teilweise Nichtübereinstimmung zweier Eingabestrings. Die Berechnung dieser Metrik erfolgt aufgrund von Einfügungen, Löschungen und Vertauschungen von Zeichen, die nötig sind um die Eingabestrings anzugleichen, sowie aufgrund der Länge der Eingabestrings.

Wird häufig in der Bioinformatik zum Abgleich von DNA Sequenzen eingesetzt und gilt als globales Alignmentverfahren, dessen Grundlage ebenfalls die Levenshtein Distanz bildet und die Ähnlichkeit der gesamten Eingabestrings ermittelt. Gilt trotz der Laufzeitkomplexität von O(n*m) als sehr effizient.

Modifikation des Needleman-Wunsch Algorithmus zur Berechnung des optimalen lokalen Alignments. Ein optimales lokales Alignment ist definiert als das beste globale Alignment zwischen zwei Teilstrings der ursprünglichen Eingabestrings. Auch hier liegt die Laufzeitkomplexität bei O(n*m).

Der Soundex Code als Verfahren der phonetischen Suche nutzt die Kenntnis über die Art und Weise, wie Wörter und Silben ausgesprochen werden, um geringfügige typografische Fehler zu übergehen. Die Idee beruht darauf, einen Namen in einen Code zu konvertieren, der die phonetische Zusammensetzung repräsentiert. Der Code besteht immer aus vier Zeichen, wobei das erste Zeichen immer der Anfangsbuchstabe des umzuwandelnden Worts ist. Jeder Wert der drei Folgezeichen ist numerisch und stellt einen von sechs Konsonanten dar. In der Aussprache ähnlich klingende Namen, haben somit denselben Code. Der vorliegende Algorithmus ist auf den deutschen Sprachraum angepasst.

Gesamte Textbausteine werden in Einzelwörter zerlegt und in Soundex Code umgewandelt. Funktionsweise mit vorangegangener Erklärung zu Soundex identisch.