So... mal Seite 31 aufgeschlagen... ich hoffe, dass man es verstehen kann - ich will jetzt nicht noch die Tabellen einscannen und hier die Vorlesung von Herrn Parchmann wiederholen (der kann das eh viel besser...).
Zur Berechnung:
- k ist die Länge der Zeichenkette an der man eine Änderung vornimmt (z.B. k Zeichen nacheinander einsetzen/löschen).
- w_k geht von links nach rechts (also Einsetzkosten in x) [hoffe mein Geschmiere stimmt]
- w_-k von oben nach unten (also Löschkosten in x) [hoffe mein Geschmiere stimmt]
- man kann beliebig oft nacheinander einsetzen/löschen/unverändert lassen, sobald man aber die Operation ändert, muss man einen neuen "Block" anfangen (Bsp: löschen+löschen+so lassen+... = 6 (k=2, w_-k wegen löschen) + 0 (a=b)
Die Tabellen I und D sind unglücklich gewählt, da sich beide über Tabelle d berechnen lassen und d sich wiederrum durch I und D bestimmen lässt. Für manche ist dieser Zwischenschritt vielleicht hilfreich, macht mir aber gerade Probleme das hier zu erklären.
Insgesamt stellen die auf Seite 31/32 (ein Blatt, das man immer wieder drehen muss) nur die Suche nach geringsten Kosten in allen möglichen Ausrichtungen dar:
- I[i,j] - Vor d[i,j] berechnetes Teilergebnis: das Optimum aus allen möglichen Ketten von Einsetzoperationen
- D[i,j] - Vor d[i,j] berechnetes Teilergebnis: das Optimum aus allen möglichen Ketten von Löschoperationen
- s: w(a,b) [Seite 30 unten, 0 bei a=b, 3 bei a != b] also beide Zeichen werden übernommen
1. im Beispiel läuft das so ab:
y' sei leer, Kosten stehen dafür bei d[0,5] = 12, dazu kommen die Kosten für 6 Einsetzungen w_6 = 7 --- 12+7 = 19
Länge von y' sei 1, Kosten stehen dafür bei d[1,5] = 13, dazu kommen die Kosten für 6 Einsetzungen w_5 = 6 --- 13+6 = 19
14+5,13+4,14+3,12+2
daraus wird das Minimum ausgewählt und in I[5,6] gespeichert. also I[5,6] = 12+2 = 14.
Man testet einfach nur sämtliche (möglichen) Kosten für jeden Tabelleneintrag durch - wieviel kostet es, wenn ich jetzt k=1,2,3, .... Zeichen einsetzen muss.
2. dann analog für's Löschen, nur nach oben statt nach links in d und mit w_-k
und die Frage ist: wieviel kostet es, wenn ich k=1,2,3,.... Zeichen löschen muss.
3. ist der Trivialfall
bedeutet das, dass ich fuer dein Beipsiel so was fuer die Lueckenkosten kriegen wuerde
x=aabbcc und y=aabbccdd
k = 1 2 3 4 5 6 7 8
Wk = 2 3 4 5 6 7 8 9
W-k = 4 6 8 10 12 14 16 18
was irgendwie kein Sinn fuer mich macht
bei x fehlt das dd am Ende...
nach den Kosten von Seite 30 gibt w(aabbcc, aabbcc) = 0, weil identisch
für ein d einsetzen guckt man bei w_k und k = 1 Kosten von 2.
für das zweite d nimmt man (hier) einfach die bisherigen Kosten 2 und addiert die Kosten für ein d dazu, macht Kosten von 4
ooooder: man geht von aabbcc aus und setzt dd ein, dann guckt man unter w_k für k = 2 nach, w(aabbcc, aabbcc) = 0, 0 + w_2 = 0+3 = 3
Minimum 3, das wären die Kosten in dem Fall.
Bei x=aabbccdd und y=aabbcc müsste man entsprechend w_-k wählen, weil man aus x die zwei d löschen müsste und man dann natürlich die Löschkosten nehmen würde.
Kleines (altes) Beispiel:
wenn du z.B.
x = abcdefghijklmnop
y = dqrstuvwxyz
hast, dann würde man eine Ausrichtung wie
abcdefghijklmnop---------------
-----d------------------qrstuvwxyz
wählen (d unter d und q nach dem p).
Die Kosten würden sich dann zu
w(abc,---) + w(d,d) + w(efghijklmnop, -----........) + w(-----...., qrstuvwxyz)
oder auch
w(abcdefghijklmnop,---d-----........) + w(-----...., qrstuvwxyz)
ergeben, je nachdem was günstiger ist.
Das erste wäre 4 + 0 + 13 [Löschung aus x] + 22 [Einsetzung in x] = 39
das zweite wäre 17 [4 + 1 (d kommt dazu) + 13-1 (weil jetzt eine lange Zeichenkette modifiziert wird, statt abc und e-p einzeln)] + 22 [wie oben]
bin mir gerade nicht sicher, ob w_-k und w_k richtig zugeordnet sind, aber Prinzip ist halt, dass das eine die Kosten für Löschung und das andere die Kosten für Einfügungen (beides in x) darstellt
Lineare Kosten sind übrigens langweilig, weil viele Beispiele mit unentschieden enden!