Ich habe eine Frage zur Levensthein-Distanz.
Um den Abstand zwischen den Worten "Tier" und "Tor" zu berechnen müssen 2 Operationen erfolgen:
1. Tier
2. Toer (Ersetze i durch o)
3. Tor (Lösche e)
Somit ist deren Distanz 2.
Dies kann man auch mit Hilfe einer Matrix darstellen:
| e | T | O | R |
| e | 0 | 1 | 2 | 3 |
| T | 1 | 0 | 1 | 2 |
| I | 2 | 1 | 1 | 2 |
| E | 3 | 2 | 2 | 2 |
| R | 4 | 3 | 3 | 2 |
Allerdings verstehe ich nicht, wie die ganzen Zahlen in dieser Matrix zustande kommen. Die Zahlen auf der Diagonale sind klar, bei unterschiedlichen Zeichen wird +1 addiert.
Was haben aber die restlichen Zahlen auf sich?
Wie verhält es sich außerdem, wenn die Worte unterschiedlich lang sind?
Danke!
