Braucht die Welt die Levenshtein-Distanz?

Wer kennt nicht das Phänomen, dass man sich eines Tages fragt: “Wieso funktioniert das so?”. Und im ganz konkreten Fall stellen wir Informatiker uns diese Frage sehr häufig rund um unsere Softwareprojekte. Diese Frage wird auch gerne von unseren Benutzern gestellt. Also, heute hat mich diese Frage wieder eingeholt. Die Frage lautete konkret: ”Wieso wird das Publikationsdatum zu einem Artikel automatisch aktualisiert. “Die Levenshtein-Distanz”, war die Antwort unseres Entwicklers. Er musste es wissen, denn er war in der kleinen Software-Ingenieur-Gruppe, die vor fünf Jahren diese Metrik auf dem Raum der Symbolsequenzen einführte. Trifft die Levenshtein-Distanz also ein, wird das Datum aktualisiert — kurz und knapp und logisch.

Hier die Logik, die vollkommene Logik des ganzen Abstrakten.

Der Algorithmus

Der Pseudocode schaut nett aus.

string backtrace(i, j):
if i>0 && D[i-1,j] + 1 == D[i,j]
return backtrace(i-1, j) + " Del "
if j>0 && D[i,j-1] + 1 == D[i,j]
return backtrace(i, j-1) + " Ins "
if i>0 && j>0 && D[i-1, j-1] + 1 == D[i,j]
return backtrace(i-1, j-1) + " Rep "
if i>0 && j>0 && D[i-1, j-1] == D[i,j]
return backtrace(i-1, j-1) + " Eq "
return ""

(c) by Wikipedia

Wieso wir das gebaut haben? Keine Ahnung.
Wann haben wir das eingebaut? Keine Ahnung.
Können wir das wieder ausbauen? Hoffentlich.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.