#levenshtein

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";

Gira per internet un’accattivante infografica che presenta la cosiddetta distanza lessicale tra le varie lingue d’Europa. La metodologia non è specificata, ma viene fatto un vago riferimento all’articolo di F. Petroni e M. Serva, due fisici evidentemente appassionati di linguistica matematica ed NLP. Presumendo che l’infografica si basa su un qualche ragionamento analogo, propongo un po’ di pensieri critici.

La metodologia di Petroni e Serva si riduce, in ultima analisi, al calcolo della distanza di Levenshtein tra coppie di parole aventi lo stesso significato, provenienti da liste di 100 parole prese da ogni lingua in esame.

L'articolo contiene la seguente affermazione:

Indeed, our method for computing distances is a very simple operation, that does not need any specific linguistic knowledge and requires a minimum of computing time.

Che le conoscenze linguistiche non siano necessarie è, però, un'illusione (e non lo dico per difendere la categoria).

Un primo inghippo si nasconde nel concetto di "parole con lo stesso significato". In realtà, tali parole, cioè perfetti "translational equivalents" semplicemente non esistono. Ogni parola italiana viene tradotta non con una, ma con tante parole inglesi diverse, secondo il contesto, la sfumatura stilistica, ecc.; lo stesso capita per qualsiasi altra coppia di lingue. (Si veda un esempio banale: le possibili traduzioni del verbo italiano andare in inglese). Quindi la scelta di come riempire le liste di parole sulle quali si basa la misurazione è estremamente arbitraria e può trasformarsi in un bias capace di falsare il risultato. Ad esempio, in inglese esistono numerosi doppioni lessicali di tipo "Germanic vs. Latinate". Basta selezionare, per ogni significato, il termine "latinate", ed ecco che la distanza tra ENG e FRA diminuirà miracolosamente, ma indebitamente. Stessa operazione può essere fatta in molti altri casi (ad esempio, in russo esiste un vasto strato di doppioni lessicali di origine europea che affiancano parole di origine slava).

Secondo problema si nasconde nell'idea di confrontare la forma ortografica delle parole. Come sappiamo, le ortografie sono spesso arbitrarie, convenzionali e modificate a posteriori. Gli autori, probabilmente, avrebbero dovuto operare con una trascrizione fonetica normalizzata delle parole di ogni lingua, anziché con la forma ortografica: le due sono spesso talmente diverse l'una dall'altra da poter influenzare in modo significativo il calcolo finale.

Infine, la mancanza di “specific linguistic knowledge” impedisce agli autori di capire il fatto che questa loro "distanza lessicale" in realtà non è correlata con alcunché di scientificamente sensato. È come se dicessimo: classifichiamo le automobili per colore. Scopriremo magari che le macchine scure sono più performanti (perché, ad esempio, le macchine costose tedesche magari sono tendenzialmente di colore scuro). Però in realtà non è una misurazione scientificamente interessante. La distanza lessicale, analogamente, non misura un bel niente, perché gli autori non sanno cosa vanno cercando. Se si vuole ottenere una misura della distanza genetica, allora la "somiglianza" lessicale è un metodo totalmente sbagliato, che semmai impedisce di vedere le relazioni genetiche (le quali si basano sulle corrispondenze fonologiche regolari, non su somiglianze, come è noto a tutti i linguisti storici già da due secoli). Se invece si vuole misurare il numero di prestiti alloglotti in ogni data lingua, allora il calcolo è sbagliato in partenza, perché, appunto, non fa alcuna distinzione tra parole imparentate e quelle di prestito.

LevenshteinSwift

damnyouautocorrect.com is a social site for sharing occurrences of auto-correction.

Auto-correction works using the Levenshtein word distance algorithm that compares words for similarity by calculating the smallest number of insertions, deletions, and substitutions required to transform one string (word) into another. The algorithm is also used for DNA matching, and plagiarism detection. Source.

The figure above can be interpreted as follows: