#sequenzalignment

New Post has been published on http://blog.relast.de/string-alignment/

String-Alignment

DNA-Analyse, String Alignment, Pattern Matching, die meisten kennen es einfach nur von Google, da nennt es sich Suchvorschlag. Am Ende dreht es sich immer um die Distanz zwischen Zeichenketten.

Warum das interessant ist? Aus mehreren Gründen.

Begriffe suchen

Begriffe finden

Duplikate finden

Fehlerkorrekturen ermöglichen

Eingaben unterstützen

Sequenzen vergleichen

Die besten Übereinstimmungen finden

Es gibt eine ganze Reihe von Anwendungen. In der Biologie versucht man DNA-Stränge auf Übereinstimmungen zu untersuchen. Da diese Stränge sehr lang sein können, verwendet man Algorithmen um Bereiche zu finden die möglichst ähnlich (oder identisch) sind. Der DNA-Vergleich spielt auch bei der Suche nach Verbrechern eine Rolle. Es gibt auch Modelle die automatisch Fehler korrigieren. Dabei sucht man in Texten nach Wörtern die eine minimale Distanz zu anderen Wörtern haben, und geht dann davon aus das es sich um einen Rechtschreibfehler handelt. Schon in einem Textverarbeitungsprogramm (Word, LibreOffice o.ä.) einen Vorschlag bekommen das man ein Wort vielleicht falsch geschrieben hat? Genau, die nutzen das auch.

Einfacher wird die Vorstellung wenn wir irgendwo etwas Wort für Wort eingeben. Zum Beispiel bei Google, oder in unser Handy. Jeder kennt das mittlerweile, wenn wir etwas eintippen versucht der Computer zu erraten was wir meinen, und macht uns schon beim tippen Vorschläge. Wie er das macht? Ganz einfach, er sucht im Hintergrund nach Zeichenketten die möglichst ähnlich zu der Zeichenkette sind die wir gerade tippen.

Um solche Zeichenketten zu finden braucht man drei Dinge: eine Zeichenkette als Referenz, eine Liste von Zeichenketten in denen man nach der Referenz suchen kann, und eine Methode um die Distanz zu messen. Wenn ich die Referenz mit allen Einträgen in der Liste vergleiche und die Distanz berechne, nehme ich am Ende die Zeichenkette aus der Liste die am dichtesten dran ist, also die geringste Distanz aufweist. So einfach ist das.

Der eigentliche Trick ist also: ich brauch eine Methode um die Distanz zwischen den Zeichenketten zu messen.

Levenshtein

Die Levenshtein-Distanz bemisst die Distanz zwischen zwei Zeichenketten durch drei Operationen: ersetzen, einfügen und löschen. Mit diesen drei Operationen muss man von der einen Zeichenkette zu der anderen gelangen. Dabei wird die Anzahl der Operationen gezählt und ergibt somit ein Maß für die Ähnlichkeit der Zeichenketten.

KnowHow: Levenshtein-Distanz

Damerau-Levenshtein

Die Damerau-Levenshtein-Distanz erweitert die Levenshtein-Distanz um eine Operation: Vertauschen. Sollten in der einen Zeichenkette zwei Zeichen in umgekehrter Reihenfolge vorkommen, dürfen diese mit einer Operation ausgetauscht werden. Bei der Levenshtein-Distanz wären das zwei Operationen. Die Damerau-Levenshtein-Distanz berechnet also sogenannte „Buchstabendreher“ weniger gewichtig als die Levenshtein-Distanz.

KnowHow: Damerau-Levenshtein-Distanz

Schreibmaschinendistanz

Die Damerau-Levenshtein-Distanz macht deutlich das es Sinn macht die möglichen Ursachen von Unterschieden zu berücksichtigen, und dementsprechend zu gewichten. Ein weiterer Kandidat ist die Schreibmaschinendistanz. Wenn man sich die Tasten auf der Tastatur (egal ob Schreibtisch oder Handy) ansieht, stellt man fest das manche „Vertipper“ schneller passieren als andere. Da ist schnell mal ein „T“ statt einem „R“ erwischt, oder umgekehrt.

Fazit

Das ist nur eine Handvoll Beispiele. Tatsächlich spielt der Vergleich von Zeichenketten, wie oben erwähnt, in einer ganzen Reihe von Szenarien eine Rolle. In jedem dieser Szenarien gibt es spezialisierte und angepasste Algorithmen. Auch das zeigt wie wichtig das Thema ist. Jeder Computer wird immer vor der Aufgabe der Interaktion mit dem Menschen stehen, und somit vor der Aufgabe Sprache zu verarbeiten. Spracherkennung, Texterkennung, Datenübertragung, Datenanalyse, immer muss der Computer zuerst die Sprache und später auch den Sinn dahinter erkennen.

Die Anwendungen reichen dabei von der einfachen Texterkennung im heimischen Scanner, über die Spracherkennung im digitalen Assistenten der meine Musik abspielen soll, bis hin zu künstlichen Intelligenzen die uns irgendwann mal als echte Assistenten zur Verfügung stehen sollen. Unser digitaler Assistent soll uns schließlich verstehen, egal ob wir morgens vor oder nach dem ersten Kaffee oder gar unter der Dusche mit ihm sprechen, oder?

    KnowHow: String-Alignment

Tools: String-Alignment

  amzn_assoc_ad_type = "responsive_search_widget"; amzn_assoc_tracking_id = "relastde-21"; amzn_assoc_marketplace = "amazon"; amzn_assoc_region = "DE"; amzn_assoc_placement = ""; amzn_assoc_search_type = "search_widget"; amzn_assoc_width = "auto"; amzn_assoc_height = "auto"; amzn_assoc_default_search_category = ""; amzn_assoc_default_search_key = "String Alignment"; amzn_assoc_theme = "light"; amzn_assoc_bg_color = "FFFFFF";