Fachrat Informatik - Forum

Also so weit ich die Lückenkosten verstanden habe, kosten die immer so viel, wieviel Zeichen eingefügt oder gelöscht werden.

Beispiel: x=aabbcc und y=aabbccdd

Du müsstest nun in x zwei d einfügen, damit die Strings gleich sind. Also hast Du . sind die Löschkosten.

Ich hoffe ich konnte Dir soweit helfen.

Wenn ich mich recht erinnere, dann waren die Lückkosten hier von Formeln abhängig:



und

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:

1. I[i,j] - Vor d[i,j] berechnetes Teilergebnis: das Optimum aus allen möglichen Ketten von Einsetzoperationen
2. D[i,j] - Vor d[i,j] berechnetes Teilergebnis: das Optimum aus allen möglichen Ketten von Löschoperationen
3. 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

Quoted from "Jojo"

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.

Quoted

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!

np, viel Erfolg von einem, der Appro schon hinter sich hat

Falls noch wer Fragen hat, einfach melden (vielleicht aber in nem neuen Thread wegen Übersicht)