10 Fingersystem-Lernprogramm

[mic_checker]

Der Rückgabewert - also die Levenshtein Distance (LD) - gibt die Anzahl der Löschungen/Einfügungen/Substitutionen etc. an, die man benötigt um einen String s in einen anderen String t zu transformieren.

 

[The_S]

Äh ja genau ... War grad ein bisschen ganz gewaltig auf den Schlauch gestanden. Peinlich! . Hab mir eingebildet, dass ich zwei Zahlen zurück bekomme und war damit überfordert ... Wird gleich mal ausprobiert.

 

[The_S]

Es scheint zu funktionieren! Nur verstehen tu ich ihn leider nicht ... Kannst du ihn mir erklären?

 

[mic_checker]

Es scheint zu funktionieren!

Freu dich nicht zu früh

Zum Verständnis ist vielleicht folgendes praktisch was ich schon mal gepostet hab:
http://www.merriampark.com/ld.htm

Dort findet man auch die Algorithmusbeschreibung. Da siehst du die Matrix anhand eines Beispiels.

Hab nochma geguckt, mein Code müsste so weit mit dem übereinstimmen.
Scheint auf jeden Fall eine Verbesserung gegenüber LCS zu sein...

 

[The_S]

Ich weiß, die Seite hab ich mir auch schon 10.000 mal durchgelesen. Es erweist sich für mich nur als äußerst komplex Sachen, die ich nichtmal ansatzweiße verstehe auf Englisch erklärlt zu bekommen und dann zu verstehen. :autsch:

 

[mic_checker]

Muss mal schauen ob ich mal Zeit genug hab was dazu zu schreiben, also nen kurzen Erklärungstext. Bisher habe ich lediglich die Algorithmusbeschreibung umgesetzt , das hat noch nichts damit zu tun das ich es jetzt versteh oder net

 

[The_S]

LOL! Hab eigentlich gedacht, dass du verstehst was du programmierst *G*. Sowas tritt bei mir immer erst ein, wenn ich meinen Code in paar Monate aufseite gelget habe (warum muss ich auch immer zu faul zum kommentieren sein ... :wink: ). Egal, wenn du Zeit hast würde ich mich über eine kurze Erklärung freuen (sofern du deinen Code verstehst).

 

[mic_checker]

Ich denke da muss man differenzieren. In dem Fall ist es so:
- Die Algorithmusbeschreibung ist gegeben
- Diese Beschreibung habe ich umgesetzt
- Praktischerweise war gleich noch die Implementierung mit dabei , so dass man damit vergleichen konnte

Ich kann dir zwar sagen welche Zeile was macht etc. aber das genaue Konzept erklären zu können ist was anderes.

So, nur damit das hier nicht falsch verstanden wird

 

[The_S]

Kannst du so in etwa erklären:

... diese Zeile überprüft ob ein Buchstabe vergessen wurde, indem es das und das vergleicht,
... diese Zeile überprüft das und das ...

?

Das würde mir ja schon wahnsinnig helfen

 

[The_S]

Ist die Lewenstein-Distanz eigentlich wieder was anderes, oder hat man sich da nur verschrieben?

Lewenstein Wikipedia.de

 

[mic_checker]

Das ist nur die unterschiedliche Schreibweise des Namen.

Hab noch andern Code gefunden der bei größeren Strings keinen OutOfMemoryError verursacht:

public static int getLevenshteinDistance (String s, String t) {
  if (s == null || t == null) {
    throw new IllegalArgumentException("Strings must not be null");
  }
		
  /*
    The difference between this impl. and the previous is that, rather 
     than creating and retaining a matrix of size s.length()+1 by t.length()+1, 
     we maintain two single-dimensional arrays of length s.length()+1.  The first, d,
     is the 'current working' distance array that maintains the newest distance cost
     counts as we iterate through the characters of String s.  Each time we increment
     the index of String t we are comparing, d is copied to p, the second int[].  Doing so
     allows us to retain the previous cost counts as required by the algorithm (taking 
     the minimum of the cost count to the left, up one, and diagonally up and to the left
     of the current cost count being calculated).  (Note that the arrays aren't really 
     copied anymore, just switched...this is clearly much better than cloning an array 
     or doing a System.arraycopy() each time  through the outer loop.)

     Effectively, the difference between the two implementations is this one does not 
     cause an out of memory condition when calculating the LD over two very large strings.  		
  */		
		
  int n = s.length(); // length of s
  int m = t.length(); // length of t
		
  if (n == 0) {
    return m;
  } else if (m == 0) {
    return n;
  }

  int p[] = new int[n+1]; //'previous' cost array, horizontally
  int d[] = new int[n+1]; // cost array, horizontally
  int _d[]; //placeholder to assist in swapping p and d

  // indexes into strings s and t
  int i; // iterates through s
  int j; // iterates through t

  char t_j; // jth character of t

  int cost; // cost

  for (i = 0; i<=n; i++) {
     p[i] = i;
  }
		
  for (j = 1; j<=m; j++) {
     t_j = t.charAt(j-1);
     d[0] = j;
		
     for (i=1; i<=n; i++) {
        cost = s.charAt(i-1)==t_j ? 0 : 1;
        // minimum of cell to the left+1, to the top+1, diagonally left and up +cost				
        d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);  
     }

     // copy current distance counts to 'previous row' distance counts
     _d = p;
     p = d;
     d = _d;
  } 
		
  // our last action in the above loop was to switch d and p, so p now 
  // actually has the most recent cost counts
  return p[n];
}

http://www.merriampark.com/ldjava.htm

Habs mit dem nicht getestet, sollte aber wohl stimmen und v.a. dann praktisch sein wenn du große Strings vergleichst (beachte: Der Autor rechnet mit Performance Einbußen bei kleineren Strings).

Muss mir auch mal den Artikel bei Wikipedia angucken...

 

[mic_checker]

Hi, also hab mir das ganze nochmal angeschaut. Im Prinzip gibts da nicht viel zu kommentieren

				/* Wenn Zeichen übereinstimmen -> Keine Substitution etc. notwendig -> 0 "Kosten" */
				if(chs == cht)
					cost = 0;
				else
					cost = 1;
				
				/* Berechnung des Minimums */	
				minimum = matrix[i-1][j]+1;
				
				if((matrix[i][j-1]+1) < minimum)
					minimum = matrix[i][j-1]+1;
				
				if((matrix[i-1][j-1] + cost) < minimum)
					minimum = matrix[i-1][j-1] + cost;

				matrix[i][j] = minimum;

Diese "Kostenberechnung" und darauffolgend die Minimumberechnung ist das entscheidende im Algorithmus.

Wenn keine Änderungen (damit meine ich Löschungen/Substitutionen/Einfügungen) notwendig sind, also beide Strings gleich, erhälst du eine Hauptdiagonale voller 0.

Wenn du ein Element in der Matrix setzt wird zuerst die Minimumberechnung durchgeführt. Dabei kannst du die Elemente links neben und direkt über dem neuen Element anschauen.
Außerdem wird das diagonal-linke Element betrachtet.

Nun wird geschaut welches dieser drei den kleinsten Wert hat.

Sagen wir das diagonal linke hat den kleinsten Wert.

Betrugen die "Kosten" 0, haben die Strings also an den Stellen übereingestimmt, so wird zu dem Wert des diagonal - linken Elementes nichts hinzuaddiert (+ cost (== 0)), d.h. für diesen Buchstaben sind keine weiteren Änderungen nötig.
Betrugen die "Kosten" allerdings 1, so sind Änderungen nötig um den neuen Buchstaben zu erhalten, du erhälst also auf jeden Fall in der Hauptdiagonalen einen Wert der um (mind.) eins größer ist als einer der drei.

Sollte ein fehler in der Argumentation sein, bitte darauf aufmerksam machen.

Hoffe ich habe konnte mehr helfen als das ich dich verwirrt habe, schau dir einfach noch die Matrizen an. Mach ein paar Beispiele in denen du dir die ausgeben lässt und geh das ganze selbst im Kopf (am Bildschirm) durch.

Ansonsten poste es.

 

[The_S]

Und wie wird dass dann gehandhabt, wenn es keine Mitteldiagonale gibt, weil ein Wort länger oder kürzer ist? Im extrem Fall statt Fehler F?

[edit] Wie kann mir mal jemand erklären wie man bbabb zu aabba in 3 Schritten umbauen kann?

 

[mic_checker]

Die endgültige Distanz steht nachher unten rechts in der Matrix, bei symmetrischen Matrizen also in der Hauptdiagonalen.

Wenn du keine symmetrische Matrix erhälst, dann addierst du nach dem Schema von oben die Werte drauf (guckst drüber, links und diagonal links und wählst das Minimum) - man ist also nicht darauf angewiesen das die Strings gleich lang sind.

Hab zuhause noch Code der die Matrix etwas schöner darstellt (d.h. eigentlich werden nur die Wörter drüber und die Buchstaben an die Seite geschrieben - falls das für das Verständnis hilft).

Es sei noch eins gesagt: Nach meinem aktuellen Stand der Dinge liefert auch der Levenshtein nicht immer die korrekten Ergebnisse, er ist aber v.a. dann praktisch weil er mittlere Distanzen zwischen Damerau-Levinshtein und Edit-Distanz liefert (schau dazu mal in die Diplomarbeit die ich dir geschickt habe, da sind ein , zwei Beispiele dargestellt).

 

[The_S]

"Mein" Code hab ich jetzt so umgeschrieben, dass er (bis jetzt) bei allem was ich ausprobiert hab funktioniert!!! Wenn du willst, kannst du den ja mal auf "Kuriositäten" testen. Meinen Versteh ich nämlich wenigstens komplett *g*.

import java.io.*;

public class diffTest { 
    
    int diff(String str1, String str2) {
    	
		str1 = " " + str1 + " ";
		str2 = " " + str2 + " ";
		int fehler = 0; 
		int[][] check = new int[str1.length()][str2.length()]; 
		for (int a = 0; a < str1.length(); a++) { 
			for (int b = 0; b < str2.length(); b++) { 
				if (str1.charAt(a) == str2.charAt(b)) { 
					check[a][b] = 1; 
				} 
			} 
		} 
		if (str1.length() < str2.length()) {
			fehler = str2.length() - str1.length();
		}
		for (int a = str1.length() - 1, b = str2.length() - 1; a >= 0 && b >= 0;) {
			if (check[a][b] == 1) {
				a--;
				b--;
			}
			else {
				for (int c = 0; c <= a; c++) {
					fehler++;
					for (int d = 0; d <= b; d++) {
						if (check[a - c][b - d] == 1) {
							if (c != 0) {
								fehler--;
							}
							a = a - c;
							b = b - d;
							d = b + 1;
							c = a + 1;
						}
					}
				}
			}
		}
		return fehler;
	}
    
	public static void main(String[] args) { 

		String str1 = null;
		String str2 = null;
		int fehler1 = 0;
		int fehler2 = 0;
		diffTest test = new diffTest();
		while(true) {
			try {
				str1 = new BufferedReader(new InputStreamReader(System.in)).readLine();
				str2 = new BufferedReader(new InputStreamReader(System.in)).readLine();
			}
			catch (Exception e) {
				System.out.println(e.toString());
			}
			fehler1 = test.diff(str1, str2);
			fehler2 = test.diff(str2, str1);
			if (fehler1 > fehler2) {
				System.out.println("Fehler: " + fehler2);
			}
			else {
				System.out.println("Fehler: " + fehler1);
			}
		} 
	}
}

 

[The_S]

Hab das soweit alles Verstanden, bis auf dass hier:

...
... sind Änderungen nötig um den neuen Buchstaben zu erhalten,...

Hä? Steh hier komplett auf dem Schlau. Wird da was geändert oder ist das einfach nur die Feststellung, dass was nicht überein stimmt.

...
...du erhälst also auf jeden Fall in der Hauptdiagonalen einen Wert der um (mind.) eins größer ist als einer der drei. ...

Woher weiß ich um wieviel er größer ist und von welchem Punkt der Matrix ich das berechne?

Sonst hab ich (bis jetzt) alles verstanden. Bist ein guter Lehrer :wink: :toll: :meld:

[edit] und warum wird bei der Berechnung des Minimums zweimal der Wert "1" als Zusatz verwendet und einmal der Wert von "cost"? Das ist mir auch noch nicht ganz klar

 

[mic_checker]

Hä? Steh hier komplett auf dem Schlau. Wird da was geändert oder ist das einfach nur die Feststellung, dass was nicht überein stimmt.

Der Levenshtein stellt dann nur fest: An dieser Stelle müsste eine Änderung vorgenommen werden, sei es nun eine Löschung,Änderung oder Substitution.
Somit stellt er "nur" fest das was nicht stimmt.

...
...du erhälst also auf jeden Fall in der Hauptdiagonalen einen Wert der um (mind.) eins größer ist als einer der drei. ...

Woher weiß ich um wieviel er größer ist und von welchem Punkt der Matrix ich das berechne?

Das mit dem mindestens war unnötig. Wenn ich das richtig erfasst habe kann der Wert nämlich nur nur 1 zunehmen, also mindestens war überflüssig.
Du schaust dir den Punkt in der Matrix an, hat er mit dem Buchstaben an Stelle i übereingestimmt ? (In dem Fall cost = 0). Dann schaust du dir den Wert links neben diesem Element an, anschließend den dadrüber und den linksdiagonal neben dem Punkt. Der Wert des neuen Punktes in der Matrix ergibt sich aus dem Minimum (+ max 1 - maximal da cost ja 0 sein kann).

[edit] und warum wird bei der Berechnung des Minimums zweimal der Wert "1" als Zusatz verwendet und einmal der Wert von "cost"? Das ist mir auch noch nicht ganz klar

Wenn der jeweilige Buchstabe an einer best. Stelle mit dem Original übereinstimmt (cost = 0) , dann soll natürlich zum linksdiagonalen Element nichts mehr hinzuaddiert werden, da man das Ergebnis natürlich nicht verfälschen will.
Tritt ein Fehler auf, so ist eins sicher: Der Wert wird um 1 größer als der kleinste der drei umliegenden -> Es wären weitere Änderungen notwendig um aufs Original zu kommen.

Btw.
Teste dein Prog mal mit :
aaabbb
bbbbaa

 

[The_S]

Sry für die Mühe, aber ich wollte gerade posten, dass ich es gecheckt hab :bae: :wink: . Ich weiß jetzt auch, warum ich es nicht gecheckt hab! Du hast einen kleinen Denkfehler gemacht. Und zwar hast du deine Matrix falsch herum ausgegeben und deswegen falsch den Code erklärt. In Wirklichkeit ist der Endwert nicht der Wert rechts unten, sondern rechts oben! Da auch nicht mit dem Element drüber und links Diagonal darüber verglichen wird, sondern mit dem Element darunter bzw. links Diagonal darunter. Deswegen hab ich das Ding auch net verstanden, wenn ich den Code mit deiner Matrix und deiner Erklärung verglichen hab :bae: .

Gut, jetzt weiß ich zwar wie es geht, aber nicht warum es geht ???:L . Aber das ist wohl sekundär :bae: . Falls trotzdem noch jemand ne Erklärung hat, warum das funktioniert, würd ich mich freuen. Ansonsten ist das Thema ENDLICH erledigt!!!

Stimmt, mein Code funzt doch net :x

Nochmal vielen vielen Dank!!! :applaus: :toll:

 

[mic_checker]

Ich muss dich enttäuschen, aber warum steht der Wert rechts oben? Schau dir die Indizes doch mal an.

 

[The_S]

Also:

1. Du gibst den Wert in der Matrix zurück, der am höchsten und am weitesten Rechts liegt (um es mal ganz blöd auszurdücken :wink: ).

int n = s.length(); 
int m = t.length();
...
return matrix[n][m];

2. Beide for-Schleifen zählen aufwärts

for(int i = 1;i < hoehe;i++) {
...
    for(int j = 1;j < breite;j++) {
...
    }
}

3. Du gibst die Matrix falsch herum aus!

for (int a = 0; a < matrix.length; a++) { 
	for (int b = 0; b < matrix[0].length; b++) { 
		System.out.print(matrix[a][b]); 
	} 
	System.out.println(); 
}

Richtig wäre

for (int a = matrix.length - 1; a >= 0; a--) { 
	for (int b = 0; b < matrix[0].length; b++) { 
		System.out.print(matrix[a][b]); 
	} 
	System.out.println(); 
}

Da du ja zuerst die letzte Zeile ausgeben musst, dann die vorletzte, usw. da du es ja nicht übereinander auf die Konsole schreibst, sondern untereinander.

Oder hab ich dabei was nicht beachtet!?

 

[mic_checker]

Du gibst den Wert in der Matrix zurück, der am höchsten und am weitesten Rechts liegt

Da hast du recht - doch was heisst es wenn i maximal groß ist ? Dann steht es in der letzten Zeile ganz rechts.

Deine Matrix gibt zuerst die letzte Zeile aus etc.

Nur warum solltest du das so machen?

 

[The_S]

Jetzt bin ich verwirrt :autsch: :bahnhof: ... wenn man mal darüber nachdenkt ... könnte man fast meinen, dass du recht hast ... aber ich bin dennoch verwirrt und muss erstmal mindestens ne Nacht drüber schlafen :wink: ...

Und ich hab mich schon gefreut, dass ich einmal was besser weiß als du ... Egal, es funktioniert und ich versteh den Algrithmus (zwar wie gesagt noch nicht wie das funktioniert, aber das ist erstmal nebensächlich). Danke für deine Mühen.

 

[mic_checker]

Jo - wenns hilft dann schlaf erstmal drüber

Btw. der Damerau-Levenshtein scheint größtenteils mit dem oben geposteteten Levenshtein übereinzustimmen, lediglich eine kleine Änderung in der initialisierenden m - Schleife (für oberste Zeile) müsste etwas abgeändert werden.

Allerdings würde es wohl nicht viel bringen die DL Distanz zu bestimmen, so dass wir den Algorithmus nicht umstellen müssen.

Hier noch die Ausgabe der Matrix mit Beschriftung:

		System.out.print("    ");
		
		for(int i = 0;i < m;i++)
			System.out.print(t.charAt(i)+" ");
		
		System.out.println();
		/*
		* Ausgabe der Matrix
		*/
		for (int a = 0; a < matrix.length; a++) {
			if(a >= 1)
				System.out.print(s.charAt(a-1)+" ");
			else
				System.out.print("  ");
         for (int b = 0; b < matrix[0].length; b++) {
            System.out.print(matrix[a][b]+" ");
         }
         System.out.println();
      }

 

[The_S]

Thx! So damit dürfte das Thema wohl (vorest, es heißt ja 10-Fingersystem-Übungsprogramm und das ist noch lange nicht vertig :wink: ) abgeschlossen sein.

 

[mic_checker]

OK

Was hast du bisher sonst denn schon entwickelt ? Kannst ja mal Code posten (oder nen Thread in Codeschnipsel etc. aufmachen).

Wirst du die Levenshtein Variante holen oder trotzdem deinen Code *g* ?

 

[The_S]

kA was ich scho alles hab (is lang her, hab ja so lange mit dem scheiß Algo rumgemacht). Hab glaub ich bis jetzt die Version, sobald de nen Fehler machst wird die Eingabe beendet, bei nem Fehler gehts net weiter, Dank dem Algo bald frei Schreiben mit Vorlagetext und noch einfach so freies Schreiben ohne Vorgabetext. Alles natürlich als "Stop beim Ende des Textes" (natürlich außer bei mit ohne Vorlage) und "Stop nach ner bestimmten Zeit" Version. Es wird immer die Anschläge pro Minute und die Zeit + gesamt Anschläge ausgegeben. Beim "Freistil" werden zusätzlich noch die Fehler mit ausgegeben. Aber genau weiß ich des selber nimmer *g*. Morgen wird die Arbeit aber wieder aufgenommen. Natürlich benutze ich den Levenshtein. Möcht ja kein Fehlerhaftes Programm :autsch:

 

[mic_checker]

Womöglich schon, mich interessiert eher das algemeinere Problem von minimal möglich Transformationen, und ob's
da einen Algo gibt der nachweislich exakt ist.

Der Algorithmus müsste doch eigentlich für dich in die richtige Richtung gehen oder?
Ich geh mal davon das auch die resultierende LD (Levenshtein Distanz) nicht immer korrekt sein wird, aber im Durchschnitt sollten damit die exaktesten Ergebnisse rauskommen.

 

[Wildcard]

Die Levenstein Distanz wird AFAIK auch praktisch eingesetzt. Hab leider auf die Schnelle nichts gefunden ob
Korrektheit garantiert wird(denke aber schon das er für 'Ersetzen', 'Hinzufügen' und 'Löschen' korrekte Werte liefert).
In der Orginalform (die ihr verwendet habt?) berücksichtigt der Algo aber keine Buchstabendreher! Das ist natürliche eine deutliche Vereinfachung des Problems...

 

[mic_checker]

So weit ich weiss kann zu diesen Zwecken die Damerau-Levenshtein Metrik verwendet werden, da dort evtl. auftretende Buchstabendreher erkannt werden können.

In einem Beispiel habe ich gesehen:
Original = hallo
Input = halol

DLEV = 1

Demnach wäre die DL Distanz 1, ich vermute mal wegen dem Buchstabendreher, allerdings habe ich die Damerau Levenshtein Metrix mal aufgestellt und bei mir kommt genauso wie bei der LD 2 raus. Die einzigste Änderung im Code soll von DL zu L nur die zweite for Schleife sein, in der die Elemente des Arrays mit "0" belegt werden (1 Zeile - für m).

Zumindest scheint es ganz gut zu funktionieren....