http://www.levenshtein.de
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
was isn bei aufgabe-9-1-2 mit “ein Polynom als Argument” gemeint? Der Grad des Polynoms oder wie oder wat oder wer? und was fuer werte sollen wir fuer die a_0 bis a_i benutzen???
ein array mit den einzelnen a’s.
beispiel:
m = new Multinteger(3);
int[] poly = {1,2,3};
System.out.println(m.evalpoly(poly);
waere dann:
1 * 3^0 + 2 * 3^1 + 3 * 3^2
ok thx, warst wohl einer der wenigen die sich vor weihnachten in ne andere übungsgruppe gesetzt haben oder was? 
So auf Wunsch im IRC erklär ich nochmal schnell wie man die kostenmatrix errechnen kann:
man fängt an mit den worten, die man ineinander überführen soll, und nummeriert sozusagen schonmal die zeilen und spalten durch:
H E I N Z
0 1 2 3 4 5
P 1
E 2
T 3
E 4
R 5
jetzt, wie man auf die anderen felder kommt…
man fängt oben links an und geht zeilenweise alle spalten durch (also erst die ganze “P”-Zeile, dann die “E”-Zeile usw…)
Der Wert der Zelle errechnet sich jeweils aus dem Minimum “bereits beschriebenen Nachbarzellen” plus Kosten, also als Beispiel ein Ausschnitt:
H
0 1
P 1
die leere Zelle hier hat den Wert 2, da es das Minimum aus (linker Nachbar (die 1 neben dem P) +1, oberer Nachbar die 1 unter dem H) und dem Nachbar “oben links”, also hier der “0” , +2 ist.
Es gibt dann noch einen Spezialfall: wenn der Buchstabe der Zeile, in der man sich grade befindet, mit dem Buchstaben der Spalte, in der man grade ist, übereinstimmt, werden die Kosten des Nachbars “oben links” weggelassen, damit ist der Wert dieses Nachbars so gut wie immer das Minimum.
Um das zu veranschaulichen vervollständige ich jetzt noch die Beispieltabelle:
H E I N Z
0 1 2 3 4 5
P 1 2 3 4 5 6
E 2 3 2 3 4 5
T 3 4 3 4 5 6
E 4 5 4 5 6 7
R 5 6 5 6 7 8
Die rote Zahl, also ganz rechts unten, ist die Levensthein-Distanz.
Zum Verständnis hab ich noch den Spezialfall, wenn die Buchstaben übereinstimmten, blau eingefärbt.
Hoffe das hilft
weiss jemand was mit “den beiden eben diskutierten auswertungsverfahren” gemeint ist? versteh das nicht so ganz
du sollst die iterative Polynomberechnung mithilfe der STIRLING-Formel mit der rekursiven vergleichen glaub ich
thx, aber wiso zum Geier fängt Bernd Ludwig dann unten rechts an? (und wie kann man laut Angabenblatt „nach rechts einfügen“ :-/
Nachtrag:
ach, ja: und tragt mal die beispielworte „levenshtein + meilenstein“ in die online-demo auf der Seite ein… find ich irgendwie witzig, dass da was anderes rauskommt als bei der erklärung… :vogel:
also:
um die kostenmatrix aufzubauen fängt man oben links an.
wenn man den billigsten weg wissen will, fängt man unten rechts an und versucht (wenn die zahlen sozusagen die felder sind, auf die man treten kann) aufmöglichst kleinen zahlen möglichst direkt zur „0“ zu laufen (so wie der eingefärbte weg auf der levensthein-demo-seite)
wenn du auf diesem weg, also von unten rechts nach oben links, einen schritt nach links machst, hast du nach rechts eingefügt (du bist sozusagen noch gleich viele spalten (buchstaben) von der null (vom anfang des ergebniswortes) weg) und wenn du nach links gehst, hast du gelöscht. wenn du diagonal nach oben links latscht, hast du ausgetauscht.
ich hoff das mit dem links und oben gehen stimmt jetz… 
dafür übernehm ich null garantie
das benutzt man zur plagiatverhinderung oder so (also texte vergleichen)
und noch andere sachen^^
ok aber ich versteh immer noch nich, warum bei dir zwischen P und H als erstes eine 2 kommt, und bei der erklärung auf der verlinkten seite eine 1???
edit: ok ich glaub ich hatte nen kleinen aussetzer, alles klar jetz
der praktische nutzen dieses algorithmus ist eigentlich gleich 0 so wie ich das sehe
aber der kostengünstigste weg ist soweit ich das in der übung verstanden hab derjenige welcher sich am ehesten an der diagonalen von links oben nach rechts unten orientiert
mehr muss ich erst nachlesen^^
Marksman :
In dem Beispiel von ChaosFan sind die Substitutionskosten 2. In dem Beispiel auf http://www.levenshtein.de/ kostet das Ersetzen eines Buchstabens aber nur 1. Daher kommt der Unterschied zustande. In der Demo (http://odur.let.rug.nl/~kleiweg/lev/) kann man die Kosten aber einstellen und so wunderbar den Unterschied sehen.
Stellt sich die Frage von was wir ausgehen sollen. Ich hab das jetzt mal mit 2 implementiert. Hoffe das passt so.
[quote=Coder]
der praktische nutzen dieses algorithmus ist eigentlich gleich 0 so wie ich das sehe[/quote]
Wenn man keine Ahnung hat, einfach mal…
Reichen dir so ziemlich jede Rechtschreibkorrektur, Fuzzy-Search, OCR, Spracherkennung oder DNA-Analyse? :finger:
/e: hat sich schon geklaert
du musst immer den kostenguenstigsten Weg nehmen, und der ist in diesem Fall eben wenn du links her kommst und da steht ja eine 2. Somit ergibt das 3 und ist die richtige Loesung.
joar, danke, wurde mir schon nochmal erklaert 
Fuer die Aufgabe 9.2 hat der Bernd Ludwig ein Beispiel aufgeschrieben, wie viele Multiplikationen man mit der “schnellen Exponentation” im iterativen Verfahren benoetigt.
Verwendet er dafuer den dekadischen oder den dualen Logarithmus?
(in seiner Anschrift schreibt er “log”, aber der dekadische erscheint mir nicht allzu sinnvoll).
hab mal gehoert fuer informatiker ist der log immer der ld, also wenn nichts anderes dabeisteht