# 10 Fingersystem-Lernprogramm



## The_S (7. Apr 2005)

Hi, arbeite gerade an nem 10 Fingersystem-Lernprogramm und stehe vor einem Problem. Ich habe einen vorgabetext (dasMuss) und einen Eingabetext (text). Wenn der User jetzt einen Buchstaben eingibt, der nicht an dieser Stelle (soweit) im Vorgabetext steht, soll der Buchstabe nicht dargestellt werden. Momentan löse ich dass, indem ich einfach den letzten wieder remove. Das funktioniert auch nur bekomme ich jedes mal eine ArrayOutOfBoundsException und ich hab keine Ahnung warum!? Hier der Code:


```
public void keyTyped(KeyEvent key) {
	if (soweit != dasMuss.getText().length()) {
		if(key.getKeyChar() != dasMuss.getText().charAt(soweit)) {
			text.remove(soweit);
		}
		else {
			soweit++;
		}
	}
	else {
		text.remove(soweit);
	}
}
```


----------



## mic_checker (7. Apr 2005)

Der User muss also letztendlich den korrekt vorgegebenen Text eingegeben haben, bis er weiter machen kann (mit nem neuem Text z.B.) oder?

Was ist "text" bei dir?


----------



## The_S (7. Apr 2005)

jup, text ist (wie in meinem 1. Post schon geschrieben :wink: der Eingabetext).


----------



## mic_checker (7. Apr 2005)

Das meinte ich nicht 

Ein String,Textfeld,Textarea etc. ?

Btw. das hier sieht schon verdächtig aus:


```
if (soweit != dasMuss.getText().length())
..
```

Weiss jetzt net genau was dein "text" ist, aber wahrscheinlich kommt ne Überschreitung bei ArrayIndexOutOfBounds oder?


----------



## The_S (7. Apr 2005)

JTextArea


----------



## mic_checker (7. Apr 2005)

Warum machst du es nicht so:

Ist die Eingabe korrekt wird das Zeichen ans Ende der JTextArea angehangen , ansonsten machst du nichts...

Du willst mit remove das Zeichen an einer best. Stelle "löschen" oder? Afaik erbt JTextArea eine Methode remove von Container/Component, diese ist aber nicht zum entfernen von Zeichen gedacht.


----------



## The_S (7. Apr 2005)

und wie mache ich das  ?


----------



## mic_checker (7. Apr 2005)

Ach quatsch, was red ich denn...das kannst du nur mit anhängen machen wenn du ne separate JTextArea holen würdest, zumindest würde es dann nur Sinn machen.

Ansonsten müsstest du wohl über setText() arbeiten.


----------



## The_S (7. Apr 2005)

Das ist ja fast so unschön wie meine Methode :wink: . Gibts da nicht noch ne andere Möglichkeit?


----------



## KSG9|sebastian (7. Apr 2005)

post mal bitte die genaue exception und den code. wo verwendest du nen array dass so ne exception geworfen wird ?


----------



## The_S (7. Apr 2005)

Das is es ja! Ich verwende kein Array ???:L . Code ist nicht arg viel mehr momentan, da ich erst in der Testphase bin.


----------



## mic_checker (7. Apr 2005)

Ich denke die Exception wird ausgelöst weil er mit remove (von Component/Container) versucht eine Komponente zu entfernen, aber er möchte ja das entsprechende Zeichen entfernen. So denke ich das zumindest mal...


----------



## The_S (7. Apr 2005)

mit replaceRange() bekomm ich ne IllegalArgumentException


----------



## mic_checker (7. Apr 2005)

Post mal bitte den genauen Code, der die IAE auslöst + Stack Trace


----------



## The_S (7. Apr 2005)

```
text.replaceRange("", soweit, soweit + 1);
```

Stack Trace?


----------



## mic_checker (7. Apr 2005)

Nein, meinte die IllegalArgumentException (IAE):



> mit replaceRange() bekomm ich ne IllegalArgumentException



Wie hast du das aufgerufen etc. ?


----------



## The_S (7. Apr 2005)

Sry, scheiß Copy & Paste! Habs ausgebessert.


----------



## mic_checker (7. Apr 2005)

Stack Trace ist in dem Fall nicht nötig, da du die entsprechende Zeile ja alleinstehend gepostet hast - damit meinte ich nur die genaue Fehlermeldung.

Du versuchst nen "illegalen Bereich" zu markieren, z.B. dein Textfeld hat nur 3 Zeichen und du versuchst den Bereich 7-8 durch "" zu ersetzen.

Dein somit ist also fehlerhaft. 

http://java.sun.com/j2se/1.5.0/docs/api/javax/swing/JTextArea.html#replaceRange(java.lang.String,%20int,%20int)

Beachte: der zweite Parameter ist >= 0.

Hab oben in deiner Bedingung ja schon gesagt das da wohl auch was nicht stimmt, schau dir die Bedingung nochmal an.

Notfalls lass dir die Werte von somit ausgeben damit du weisst was genau falsch läuft.


----------



## The_S (7. Apr 2005)

Und wie löse ich das dann?


----------



## The_S (7. Apr 2005)

Hab ne Lösung gefunden!!!


```
text.replaceRange("", text.getText().length() - 1, text.getText().length());
```


----------



## The_S (7. Apr 2005)

Nö, geht leider doch net :cry: , wird zwar keine Exception mehr geworfen, funzt aber net immer so, wie es soll


----------



## mic_checker (7. Apr 2005)

Du hast es jetzt in keyTyped() oder? Versuch das mal mit keyReleased(). Wenn du schnell genug tippst führt das aber immer noch zu Fehlern.


----------



## The_S (7. Apr 2005)

Jo, für Turbotipper is das nix. Aber das muss doch irgendwie gehen (ich könnts ja in nen String speichern und dann da den letzten Buchstaben ersetzen und dann wieder ins JTextArea, aber bevor ich das mach, fang ich lieber einfach die Exception und geb nix aus  :wink: ), bin doch sicherlich nicht der 1. der sowas probiert!


----------



## mic_checker (7. Apr 2005)

Habs kurz testweise bei mir mit keyRelease probiert und dort deinen replaceRange, hat gefunzt, nur halt net für Turbotipper 

Die brauchen das Prog ja eh nicht mehr benutzen *g*


----------



## The_S (7. Apr 2005)

Is aber nicht schön, wenn der User aus versehen mal auf ner Taste einschläft und dadurch ein Fehler im Programm findet :wink:


----------



## Wildcard (7. Apr 2005)

Du kannst auch das Textfeld in ein Panel legen, den KeyListener auf das Panel, das Panel fokusieren und 
damit alle Eingaben abfangen...  :wink:


----------



## Roar (7. Apr 2005)

häng doch einfach ein eigenes Document an deine JTextArea. siehe dazu in der FAQ


----------



## The_S (8. Apr 2005)

OK, danke! Funktioniert jetzt soweit. Jetzt komme ich aber zum nächsten Problem! Natürlich soll auch ein Text einfach so geschrieben werden können. Dazu gibts dann auf Wunsch noch eine Vorlage. Wenn der Text beendet ist möchte ich jetzt überprüfen, wie viele Fehler gemacht wurden. Ich hab aber keine Ahnung, wie ich das machen könnte. Man könnte zwar die einzelnen Zeichen des Eingabetextes und des Ausgabetextes vergleichen, aber sobald dann ein Buchstabe zu viel oder zu wenig vorkommt, sind alle darauf folgenden Buchstaben auch falsch! Hat da jemand eine Idee?


----------



## mic_checker (8. Apr 2005)

Du liest zuerst natürlich komplett, ohne jegliche überprüfungen den eingegebenen text ein.

dann könntest du ja z.B. in ner for schleife den ursprünglichen text durchgehen ("Buchstabenweise") mit einer Zählvariable und den eingegebenen Text mit ner andern Zählvariable, wenn der Buchstabe an Stelle 0 mit dem eingegebenen Buchstaben an Stelle 0 übereinstimmt, inkrementiere die beiden Zählvariablen und geh weiter zu Buchstabe 1. 
Wenn ein Fehler auftritt inkrementiere nur die Zählvariable des eingegebenen Textes (und die Anzahl der Fehler).

Hoffe du verstehst was ich meine, ansonsten versuch ich noch etwas Code zu posten.


----------



## The_S (8. Apr 2005)

Jo, versteh ich! Genial! Bin zwar noch nicht an dieser Stelle angekommen (hab die Frage einfach mal vorab gestellt :wink: ), geb aber bescheid obs funktioniert hat oder nicht.


----------



## mic_checker (8. Apr 2005)

Gut 

Du müsstest nach der For Schleife aber noch eine Bedingung überprüfen.

Beispiel:
-----------

Original = Hallo Welt
Input = Hallo

Wenn du es so machst wie oben meldet er u.U. keinen Fehler, deshalb musst du noch  den Wert der Zählvariable des Original Textes überprüfen.
In diesem Fall müssen ja 5 Fehler rauskommen.

Dies könnte evtl. so gehen:


```
if(i < original.length())
			fehler += (original.length() - i);
```
i = Zählvariable von Original
fehler = Anzahl Fehler
original = Original Text


----------



## The_S (8. Apr 2005)

Jo, danke! Damit beschäftige ich mich dann, wenn es soweit ist


----------



## mic_checker (9. Apr 2005)

Allerdings gibt es bei dem bisherigen Ansatz ein Problem.

Beispiel:

```
String input = 	"Hallo welt";
		String original = "hallo welt";
```

Vergleichst du einfach nur so buchstabenweise, erhälst du hier viele Fehler, deshalb müsstest du noch einen Fall beachten.

Wenn Buchstabe an Stelle i in beiden Texten sich nur in Groß/Kleinschreibung unterscheiden, zähle beide Zählvariablen hoch, sowie die Fehlervariable, damit kriegst du oben nämlich korrekt raus : 1 Fehler.


----------



## The_S (9. Apr 2005)

Bin immernoch nicht so weit, hab momentan zu viel zu tun :wink: . Geb dann die Lösung, wenn ich eine hab oder frag nochmal nach


----------



## The_S (10. Apr 2005)

So, jetzt stehe ich vor dem Problem. Und das ist wirklich gar nicht so leicht. Ich muss beachten, dass

- Buchstaben zu viel sind
- Buchstaben zu wenig sind
- an gewissen Stellen Buchstaben zu viel und an anderen wieder zu wenig sein können, so dass ich mich auch nicht darauf verlassen kann, dass wenn die Länge der beiden Strings übereinstimmt, auch keine zu vielen oder zu wenigen Zeichen vorkommen
- ein Buchstabe vertauscht wurde
- mehrere Buchstaben hintereinander vertauscht wurden
- ein Buchstabe vertauscht wurde, dann ein Buchstabe zu viel oder zu wenig, dann noch ein vertauscher
- ...

sehr komplex das Ganze. Da kennt nicht jemand zufällig einen Algorithmus oder so was?


----------



## The_S (13. Apr 2005)

Hab da mal nen Ansatz, nur funktioniert der nicht immer ???:L , aber meistens. Wie kann ich das Ding verbessern, so dass es immer funktioniert? Ich brauche einzig und allein die Anzahl der Fehler, nicht wo sie sich befinden.


```
static int differenz(String str1, String str2)  {
		
		int str1F = 0; 
		int str2F = 0; 
		int fehler = 0; 
		int lange = 0; 
		boolean fertig = false; 
		if (str1.length() <= str2.length()) { 
			lange = str1.length() - 1; 
		} 
		else { 
			lange = str2.length() - 1; 
		} 
		if (str1.length() > str2.length()) {
			fehler = str1.length() - str2.length();
		}
		else {
			fehler = str2.length() - str1.length();
		}
		for (int i = 0; i < lange && fertig == false; i++) { 
			if (str1.charAt(str1F) != str2.charAt(str2F) && fertig == false) { 
				int soweit = 0; 
				int test1 = str1F; 
				int test2 = str2F; 
				fehler++; 
				try { 
					while (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
						soweit++; 
						if (test1 + soweit + 1 >= lange) { 
							fertig = true; 
						} 
						if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
							for (int durch = 0; durch != soweit; durch++) { 
								test1++; 
								test2++; 
							} 
						} 
						if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
							test1 = str1F; 
							test2 = str2F; 
							for (int durch = 0; durch != soweit; durch++) { 
								test1++; 
							} 
						} 
						if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
							test1 = str1F; 
							test2 = str2F; 
							for (int durch = 0; durch != soweit; durch++) { 
								test2++; 
							} 
						}    
					} 
				} 
				catch (Exception e) { 
				} 
				str1F = test1; 
				str2F = test2; 
			} 
			str1F++; 
			str2F++; 
			if (str1F >= lange || str2F >= lange) { 
				fertig = true; 
			} 
		} 
		return fehler; 
	}
```


----------



## mic_checker (13. Apr 2005)

Hi,
also ich hab gerad nicht meine Sources griffbereit, aber werd ich nachholen.

Hast du meinen Beitrag oben mal durchgelesen ?

Ich würde an deiner Stelle mit zwei Zählvariablen arbeiten (sowie einer Fehlervariablen), je nach Situation beide oder nur eine Zählvariable inkrementieren.

Btw. wann ist die Fehleranzeige denn fehlerhaft (in welchen Situationen: Text zu kurz,zu lang etc.) ?


----------



## The_S (13. Apr 2005)

Jo, hab deinen Beitrag gelesen. Benutze doch zwei Zählvariablen!? ???:L . Hab das jetzt nochmal überarbeitet. Bekomme Fehler, wenn viele Zeichen (oder ein paar am Ende) fehlen. Hier der überarbeitete Code:


```
static int differenz(String str1, String str2)  {
		
		str1 = str1.replaceAll("\n", " \n") + " ";
		str2 = str2.replaceAll("\n", " \n") + " ";
		int str1F = 0; 
		int str2F = 0; 
		int fehler = 0; 
		int lange = 0; 
		boolean fertig = false; 
		if (str1.length() <= str2.length()) { 
			lange = str1.length(); 
		} 
		else { 
			lange = str2.length(); 
		}
		try {
			for (int i = 0; i < lange && fertig == false; i++) { 
				if (str1.charAt(str1F) != str2.charAt(str2F) && fertig == false) { 
					int soweit = 0; 
					int test1 = str1F; 
					int test2 = str2F; 
					fehler++; 
					while (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
						soweit++; 
						if (test1 < lange && test2 < lange) {
							if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
								for (int durch = 0; durch != soweit; durch++) { 
									test1++; 
									test2++; 
								} 
							}
						}
						if (test1 < lange && test2 < lange) {
							if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
								test1 = str1F; 
								test2 = str2F; 
								for (int durch = 0; durch != soweit; durch++) { 
									test1++; 
								} 
							}
						}
						if (test1 < lange && test2 < lange) {
							if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
								test1 = str1F; 
								test2 = str2F; 
								for (int durch = 0; durch != soweit; durch++) { 
									test2++; 
								} 
							}    
						} 
						else {
							fertig = true;
						}
					}
					str1F = test1;
					str2F = test2;
				}
				str1F++; 
				str2F++;
				if (str1F >= lange || str2F >= lange) { 
					fertig = true; 
				}
			} 
		}
		catch (Exception e) {
			System.out.println(e);
			fehler = -1;
		}  
		return fehler; 
	}
```

Bekomme ne StringIndexOutOfBoundsException (is ja auch das einzig logische :wink: )


----------



## mic_checker (13. Apr 2005)

sorry, habs ganz übersehen das du zwei hast 

Du benutzt eine Längenangabe und zwei Zählvariablen, beim kleineren/kürzeren String verursacht das irgendwann logischerweise ne OutOfBounds, deshalb solltest du zwei Längenangaben kontrollieren, der eine geht nur bis Ende vom ersten String , der ande bis Ende vom anderen.

Ich hab meinen Code noch mal gefunden, funktioniert manchmal ganz gut (manchmal auch nicht ), gibt u.a. Probleme wenn die Texte unterschiedlich lang sind....Werde bei Gelegenheit noch versuchen Fehler auszumerzen etc.


```
String input = "hAlLo WelT";
		String original = "Hallo welt";
		
		int fehler = 0;
		int i = 0;
		int j = 0;
		
		for(;i < original.length() && j < input.length();) {
			if(input.charAt(j) == original.charAt(i))
				i++;
			else if(Character.toLowerCase(input.charAt(j)) == Character.toLowerCase(original.charAt(i))) {
				i++;
				fehler++;
			} else
				fehler++;
			
			j++;
		}
		
		if(i < original.length())
			fehler += (original.length() - i);
```

Es sei noch gesagt: Der Code funzt nicht fehlerfrei, also eher als Ergänzung oder weiteres Beispiel sehen


----------



## The_S (13. Apr 2005)

Kannst mir mal verraten, warum dein Code so verdammt viel kürzer ist!? :x  ???:L  :wink: . Und wenn du schonmal am erklären bist, kannst mir mal sagen wie dein Code funktioniert? Büüüüüüüüüüüüüüüddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee ... :wink: . Der Code ist mir nämlich eindeutig zu kurz :bae:  :autsch:


----------



## mic_checker (13. Apr 2005)

Also er ist kürzer, funktioniert dafür in einigen Fällen auch net 

Das Prinzip:

Du hast den Original String und den eingegebenen String.

Im Optimalfall sind die beiden gleich, bis auf groß/kleinschreibungs unterschiede.

Wie geht das Prog vor?

Es vergleicht die ersten beiden Buchstaben, wenn beide gleich sind gehts weiter und er vergleicht jeweils die zweiten. Wenn sich die beiden ersten Buchstaben nur in Groß/Kleinschreibung unterscheiden geht er auch weiter, zählt allerdings die Fehlervariable hoch, wenn sie sich ganz unterscheiden zählt er die Zählervariable des einen Strings hoch und die Fehlervariable.

Beispiel:


```
String input = 	"Haaallo";
		String original = "Hallo";
```
habe extra ein beispiel gewählt wo es denn mal klappt 

H -> H beide gleich also geh weiter
a -> a beide gleich ....
a -> l  ungleich, geh weiter in input, zähl fehler hoch
a -> l ungleich, ....
l -> l gleich , geh weiter
l -> l gleich ...
o -> o gleich...

Fehler = 2

In einigen Fällen gibts mit diesem Ansatz so aber Probleme, ganz trivialer Fall:

Original  = Hallo
Eingabe = t

H != t , zählt Fehler also hoch , nachher kontrolliert er den Wert der Zählvariable und packt noch die zusätzlichen Fehler drauf, so dass 6 Fehler entstehen....obwohl du wahrscheinlich hier 5 Fehler haben willst....

Das Problem ist aber interessant  Werde versuchen da dran irgendwie weiter zu arbeiten.


----------



## The_S (13. Apr 2005)

Wenn ich mein


```
fehler++
```

in meine while-Schleife schreibe, hab ich den Vorteil, dass jeder Fehler gezählt wird (auch wenn zwei Fehler hintereinander auftreten). Nur stellt sich jetzt ein anderes Problem: Was mache ich bei einem solch speziellen Fall, wenn z. B. statt 

"*Fehler*" 

"*Fler*" 

geschrieben wurde? Dann wird versucht ob es wieder stimmt, wenn man beide um ein Zeichen vorsetzt (h und e), trifft nicht zu, 2. Versuch den Eingabetext um ein Zeichen vorsetzten (e, e) Fehler (angeblich) gefunden, weiter gehts. Nur dass stimmt ja nicht, da nur Zufällig das e nochmal auftritt. Das ganz scheint mir jetzt extrem komplex zu werden ... Am einfachsten wäre es ja, wenn ich einfach pro Wort nur einen Fehler zulassen würde, aber das wäre ja langweilig :bae: :wink: . Jemand ne Idee?

[edit] @mic_checker hast gepostet, als ich auch gepostet hab. Was mich interessiert, funktioniert dein Code an dem von mir geschildertem Problem? Und funktioniert er, wenn ein Buchstabe vergessen wurde?


----------



## mic_checker (13. Apr 2005)

Nein, habe ich auch direkt getestet, das Problem ist scheinbar etwas schwieriger als ich anfangs dachte, das muss ich schon zugeben...ich könnte meinen Ansatz auch dahingehend umstellen das er diesen Fall erkennt, aber dann macht es wieder in anderen Fällen Probleme, was ja nicht im Sinne des Erfinders sein kann.

Kamst du mit (Java) Diff weiter ?


----------



## The_S (13. Apr 2005)

Ich weiß. Hab das Problem auch unterschätzt. Entweder werden zwei oder mehr Fehler hintereinander nicht erkannt, oder es kommt in bestimmten Fällen zu komplexen Situationen bei der der aktuelle Algorithmus versagt. Die Sache mit dem wenn Buchstaben zu viel oder zu wenig sind bearbeitet mein jetztiges Programm, nur wird in diesem Beispiel ein Buchstabe zu wenig angezeigt und ich hab keine Ahnung warum:

Originaltext: "wird es weißen"
Eingabetext: "wird swie"

Hier werden nur 4 Fehler erkannt obwohl es eigentlich 5 seien sollten (wird *_*s*_*w*_*i*_*e*_*) Schreibe ich allerdings "wird eswie" wird alles korrekt ausgegeben. Da ich mir nicht ganz sicher bin, ob mein Code noch aktuell ist poste ich nochmal den Code :wink: 


```
static int differenz(String str1, String str2)  {
		
		str1 = str1.replaceAll("\n", " \n") + " \n";
		str2 = str2.replaceAll("\n", " \n") + " \n";
		int str1F = 0; 
		int str2F = 0; 
		int fehler = 0; 
		int lange = 0; 
		boolean fertig = false; 
		if (str1.length() <= str2.length()) { 
			lange = str1.length(); 
		} 
		else { 
			lange = str2.length(); 
		}
		try {
			for (int i = 0; i < lange && fertig == false; i++) { 
				if (str1.charAt(str1F) != str2.charAt(str2F) && fertig == false) { 
					int soweit = 0; 
					int test1 = str1F; 
					int test2 = str2F; 
					fehler++; 
					while (fertig == false && str1.charAt(test1) != str2.charAt(test2)) { 
						soweit++; 
						if (test1 < lange && test2 < lange) {
							if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
								for (int durch = 0; durch != soweit; durch++) { 
									test1++; 
									test2++; 
								} 
							}
						}
						if (test1 < lange && test2 < lange) {
							if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
								test1 = str1F; 
								test2 = str2F; 
								for (int durch = 0; durch != soweit; durch++) { 
									test1++; 
								} 
							}
						}
						if (test1 < lange && test2 < lange) {
							if (str1.charAt(test1) != str2.charAt(test2) && fertig == false) { 
								test1 = str1F; 
								test2 = str2F; 
								for (int durch = 0; durch != soweit; durch++) { 
									test2++; 
								} 
							}    
						} 
						if (test1 >= lange || test2 >= lange) {
							fertig = true;
						}
					}
					str1F = test1;
					str2F = test2;
				}
				str1F++; 
				str2F++;
				if (str1F >= lange || str2F >= lange) { 
					fertig = true; 
				}
			} 
		}
		catch (Exception e) {
			System.out.println(e);
		}
		return fehler; 
	}
```


----------



## The_S (13. Apr 2005)

Mir ist da noch was eingefallen ... weiß nur noch nicht wie ichs einsetz bzw. umsetzen kann. Leider weiß ich aber auch noch nicht ob es überhaupt nützlich ist ???:L  :?  :roll: . Man könnte doch den Fehlerzähler erhöhen und dann den falschen Buchstaben

a) durch den Richtigen ersetzen

b) löschen

c) vorher den Richtigen einfügen

jenachdem woran es liegt. Dann weitervergleichen. Das würde zumindest mal das Problem lösen, dass ich bei zu wenigen (oder zuviel) Buchstaben Schwierigkeiten bekomme. Und ich denke es kann auch anderweitig nütlich sein. Ich weiß nur noch nicht wie :bae:  :wink:  :autsch: .


----------



## mic_checker (13. Apr 2005)

Durch die Korrektur wird es imho nicht immer einfacher. Zumindest ist es wohl nicht einfach das ganze korrekt und praktisch umzusetzen.

Oder kannst du mal an einem ausführlichen Beispiel zeigen wie du das umsetzen willst? Deine Idee ist mir schon klar, frag mich gerade nur ob es was bringt zur Lösung des Problems.


----------



## Wildcard (13. Apr 2005)

Ich abstrahier das ganze mal etwas:
Die korrekt Fehlerzahl währe also die minimal nötige Anzahl von Operationen um aus einem beliebigen String einen anderen zu machen. Als eine Operation gilt hier 
 - Buchstabe einfügen
 - Buchstabe löschen
 - Buchstabe ändern

soweit korrekt?
Ratschlag von mir: 
lass es sein, das kriegst du nicht hin!  :wink: 
Wie willst du einen Algorithmus schreiben der erkennt das es sinnvoller ist an Stelle 14 einen Buchstaben zu ändern,
da er dann die 5 davor einfach weiterschieben kann, anstatt alle Buchstaben zu änder...   :autsch: 
Die einzige Methode die mir jetzt einfallen würde ist alle Möglichkeiten zu testen und die Günstigste zu
nehmen(was alles andere als trivial ist). 
Und wenn du das tatsächlich versuchst hast du ein exptime Problem und wirst während dein PC rechnet
viel zeit haben um über dein nächstes Projekt nachzudenken  :lol: 
Mach Einschränkungen:
 -Man kann nur 2 Buchstaben verdrehen
 -Man kann nur einen Buchstaben zuviel oder zu wenig schreiben, der nachfolgende muss dann aber korrekt sein
Wirklich korrekt wirst du's nicht schaffen...


----------



## The_S (13. Apr 2005)

diff kann das doch auch. Ich hab schon gesucht, aber nirgends was gefunden, was AUSFÜHRLICH beschreibt, wie diff funktioniert. Es muss also irgendwie funktionieren. Oder sehe ich da was falsch?


----------



## Wildcard (13. Apr 2005)

Meinst du sowas?
Hab mir das jetzt nur kurz angesehen, aber der Alogrithmus entstammt einem eigenen Buch über diese Art
Algorithmus, also von jemandem der sich sehr lange damit beschäftigt hat Lösungen für genau dieses Problem 
zu finden. Wie im Comment vermerkt wurde erziehlt der verlinkte Algorithmus kürzere Änderungslisten als das 
Orginal, was bedeutet das beide nicht-deterministisch sind, also nicht unbedingt die beste Anzahl an Änderungen 
liefern. Wie hoch schätzt du jetzt deine Chancen ein das Problem korrekt zu lösen?  :wink:


----------



## The_S (14. Apr 2005)

Boah, des is ja dermaßen unlerserlich geschrieben ... Aber ich habe eine andere Idee:
Ich gehe den Text wie bisher durch + dass die Fehler korrigiert werden (kann ja abfragen, was genau falsch gemacht wurde), sobald das 1. Vorgabe Wort vollständig überprüft wurde, wird es mit dem 1. Eingabe Wort verglichen. Stimmt das überein, wird bei der Vorgabe und der Eingabe das 1. Wort entfernt und es geht ganz normal weiter. Stimmt es aber nicht überein, gehe ich die ganze Schleife mit dem original eingegebenen Wort nochmal durch, und teste, ob es bei dem 1. Buchstaben noch eine andere Korrekturmöglichkeit gibt (z. B. bei dem "Fehler" "Fler"). Funzt das auch net, wird der 2. überprüft usw. Stimmt dann das Eingabewort mit dem Vorgabewort überein geht es weiter im Text. Eigentlich müsste das doch funktionieren!? Oder habe ich da einen Denkfehler?


----------



## Wildcard (14. Apr 2005)

Wenn du es weiterhin 'korrekt'(also mit minimal möglichen Veränderungen) machen willst, viel Glück!
Poste es doch bitte wenn du's fertig hast, dann zeig ich dir gerne einen Fall bei dem's nicht funktioniert  :wink:


----------



## mic_checker (14. Apr 2005)

Also ich hab heute den Prof in unserer Datenstrukturen+Algorithmen Übungsstunde diesbezüglich mal "angehauen" 

Der wollte mir noch nen Link schicken, bzgl. einer Diplomarbeit die sich wohl teilweise damit beschäftigt.
Wenn er geantwortet hat werd ich dir den Link mal schicken...


----------



## The_S (14. Apr 2005)

Ach verdammt, konnte das zwar noch nicht durchprogrammieren (ja ich hab auch andere Hobbys und Verpflichtungen :wink: ), aber hab das mal theoretisch auf nem Blatt durchgespielt. Das würde dann so Enden, dass aus Fler gleich im 1. Durchlauf das Wort Fehler gebastelt wird. Nur nicht so wie es eigentlich gedacht war. Weil es dann insgemsamt 4 Fehler gibt. :autsch: Das funzt allso auch nicht. Noch ne möglichkeit wäre, dass Wort so lange durchzugehen, bis die Methode mit den wenigsten Fehlern gefunden wird. Wäre aber sehr Rechenaufwendig.

Ja, poste den Link sobald du ihn hast.


----------



## Wildcard (14. Apr 2005)

Ich hab langsam das Gefühl das du mir gar nicht glauben willst!   
Wofür muss das ganze denn so exakt sein? Wenn jemand so dämlich ist den ganze Wörter zu vergessen,
dann wird er wohl kaum über dein Prog merkern dürfen...


----------



## The_S (14. Apr 2005)

Will ich auch nicht :wink: . Das Problem hat jetzt meinen Ehrgeiz geweckt. Mittlerweile ist die implementierung dieses "Projekts" in mein 10-Fingersystem-Übungsprogramm zweitrangig geworden. Will das jetzt umbedingt lösen! Koste es was es wolle :wink: . 

Aber net bös verstehen. Muss ich jetzt einfach ne Lösung für finden. Ich komm (wenn ich zulange keine Erfolgserlebnisse hab) von meinem Trip auch wieder runter, aber solange ich noch drauf bin :bae: , bin ich für jeden Tip dankbar.


----------



## mic_checker (14. Apr 2005)

Hab leider noch keine Antwort bekommen, aber anhand des Gesprächs konnte ich v.a. eins extrahieren:
Das Problem ist nicht gerade trivial, ums mal vorsichtig auszudrücken  

Zu deiner Idee :
Wer sagt denn das die Variante mit den wenigsten Fehlern die richtige ist? In manchen Fällen ist ja vielleicht die mit den meisten Fehlern korrekt, dann mal wieder die mit den wenigsten etc. 
Soll heissen: Nicht nur das es zu rechenintensiv ist, es ist auch praktisch nicht brauchbar.

Würde empfehlen ein paar Regeln aufzustellen nachdenen Fehler berechnet werden, in manchen Fällen muss der User halt in den sauren Apfel beissen und kriegt evtl. mehr Fehler angezeigt als er eigentlich gemacht hat.

Btw. kann deinen Ehrgeiz durchaus verstehen, hab heute ein paar meiner Kumpels damit konfrontiert und die waren nach ein paar Minuten Überlegungen auch überrascht ..... *g*


----------



## The_S (15. Apr 2005)

mic_checker hat gesagt.:
			
		

> Zu deiner Idee :
> Wer sagt denn das die Variante mit den wenigsten Fehlern die richtige ist? In manchen Fällen ist ja vielleicht die mit den meisten Fehlern korrekt, dann mal wieder die mit den wenigsten etc.
> Soll heissen: Nicht nur das es zu rechenintensiv ist, es ist auch praktisch nicht brauchbar.



Nach irgendwas muss ich ja gehen :bae: . Denk mal, dass es wahrscheinlicher ist, dass weniger Fehler gemacht wurden als mehr.



			
				mic_checker hat gesagt.:
			
		

> Würde empfehlen ein paar Regeln aufzustellen nachdenen Fehler berechnet werden, in manchen Fällen muss der User halt in den sauren Apfel beissen und kriegt evtl. mehr Fehler angezeigt als er eigentlich gemacht hat.



Beispiel? Kann mir da nämlich nichts drunter vorstellen :bahnhof:  ???:L


----------



## mic_checker (15. Apr 2005)

Also hab heute morgen eine Antwort bekommen, da er momentan nicht auf den zuständigen Server zugreifen konnte hat er mir die Diplomarbeit so zugeschickt.

Viellleicht helfen dir auch noch die Stichworte:
- Levensthein Distanz 
(- edit Distanz )


Hab mal kurz gesucht und bin darauf gestossen:
http://www.levenshtein.de/

Viel Spaß


----------



## mic_checker (15. Apr 2005)

Hab gerad etwas weiter gesucht.

Vielleicht solltest du dir auch mal die "Damerau-Levenshtein-Metrix" anschauen, da dieser Metrix im Gegensatz zur Levenshtein Metrix ein weiterer Operator zur Verfügung  steht (Transposition), die kann benachbarte Elemente/Symbole vertauschen, eignet sich also für dein Beispiel bei "Buchstabendrehern".

Ich kann dir die Arbeit gerne per EMail zuschicken, allerdings befasst sie sich wirklich nur an einigen Stellen damit, da es eigentlich um "Sprachunterstützung" und "eLearning" geht...


----------



## The_S (15. Apr 2005)

Kann mir das alles grad net so anschauen, weil ich Berufsschule hab. Kannst mir aber gerne mal per Mail schicken.


----------



## The_S (15. Apr 2005)

Hab da noch was gefunden!!! Was als "Longest common Subsequence" bekannt ist. Kennt dazu jemand interessante Links? Bzw. wie realisiere ich sowas in Java?


----------



## mic_checker (15. Apr 2005)

Sie haben Post 

Btw. hab noch ne andere Seite zum Levenshtein Algo gefunden :

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

Dort ist auch ne Implementierung in Java etc.



> Longest-Common-Subsequence (LCS)
> 
> Dieses gilt als eine vereinfachte Variante des Levenshtein-Algorithmuses. Dieser Ansatz findet in der Diskussion um approximative Suchtechnologien Bedeutung, da hier direkt zusammenliegende Buchstaben-Sequenzen die gleiche Bedeutung zugewiesen bekommenen, wie Buschstaben-Sequenzen, die innerhalb des Wortes verteilt sind. In Fällen, in denen ein direktes Verhältnis zwischen der Länge der Suchanfrage und der Länge der Wörterbucheinträge nicht gegeben werden kann, ist es ein geeigneter Algorithmus für approximative Suchanfragen. Aber genauso wie beim Bipartiten Matching, gelang bisher nur der Firma Exorbyte eine performante Implementierung kaum möglich.


http://www.levenshtein.de/levenshtein_search.htm


----------



## The_S (15. Apr 2005)

Hey das Ding ist geil! Jetzt müsst ichs nur noch verstehen   :wink: .

@Wildcard ein vorläufiges :bae:  :wink:


----------



## mic_checker (15. Apr 2005)

Meinst du den Levi Algorithmus oder Longest-Common-Subsequence oder die ganze Diplomarbeit ? 

Da hast du wenigstens was zu tun in den Pausen *g*


----------



## The_S (15. Apr 2005)

Alles insgesamt, habs aber auch nur überflogen. Werd mich jetzt mal dran machen da ein wenig durchzusteigen :wink: . Nochmal Danke. :toll:


----------



## The_S (15. Apr 2005)

Versuche zZ das hier umzusetzen. Bekomm dass aber nicht so hin, wie ich es möchte. Bin gerade dabei das 2 Dimensionale Array mit Zahlen zu bestücken, damit die Ausgabe so ausschaut, wie bei dem Beispiel auf der Seite. Das klappt auch, solange ich keine Buchstaben zu viel oder zu wenig hab. Wie müsste ich meinen Code erweitern, dass soetwas auch geht (oder geh ich das mit meinem aktuellen Code total falsch an?)?


```
public class diffTest {
	
	public static void main(String[] args) {
		
		String str1 = "Fehlt";
		String str2 = "Fehlt";
		int fehler = 0;
		int stelle = 1;
		int[][] check = new int[str1.length() + 1][str2.length() + 1];
		for (int a = 0; a < str1.length() + 1; a++) {
			check[a][0] = 0;
		}
		for (int a = 0; a < str2.length() + 1; a++) {
			check[0][a] = 0;
		}
		for (int a = 1; a < str1.length() + 1; a++) {
			for (int b = a; b < str2.length() + 1; b++) {
				if (str1.charAt(a - 1) == str2.charAt(b - 1)) {
					for (int c = b; c < str2.length() + 1; c++) {
						check[a][c] = b - (stelle - 1);
					}
					for (int c = a; c < str1.length() + 1; c++) {
						check[c][a] = b - (stelle - 1);
					}
				}
				else {
					for (int c = b; c < str2.length() + 1; c++) {
						check[a][c] = b - stelle;
					}
					for (int c = a; c < str1.length() + 1; c++) {
						check[c][a] = b - stelle;
					}
					stelle++;
				}
				b = str2.length() + 1;
			}
		}
		for (int a = str1.length(); a >= 0; a--) {
			for (int b = 0; b < str2.length() + 1; b++) {
				System.out.print(check[a][b]);
			}
			System.out.println();
		}
	}
}
```


----------



## mic_checker (17. Apr 2005)

Kamst du eigentlich nochmal weiter? Hatte leider noch keine Zeit mir LCS näher anzuschauen....

Hilft dir der Source vom Applet nicht weiter?


----------



## The_S (17. Apr 2005)

Nö bis jetzt noch nicht. Und aus dem Applet-Code werde ich auch nicht wirklich schlau ... Ich post ihn mal ganz *g*:


```
import java.applet.Applet;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.EventObject;

public class LCSApplet extends Applet
    implements ActionListener, Runnable
{

    public LCSApplet()
    {
        pos_i = 1;
        pos_j = 1;
        backcount = 0;
        calc_length_done = false;
        status = 1;
    }

    public void run()
    {
        setButtons();
        while(status == 0) 
        {
            lcs_next();
            waitDelay(100);
        }
        setButtons();
    }

    public synchronized void stop()
    {
        if(runner != null && runner.isAlive())
        {
            status = 1;
            notify();
            runner = null;
        }
        setButtons();
    }

    public void init()
    {
        y_label = getImage(getDocumentBase(), "label_y.gif");
        x_label = getImage(getDocumentBase(), "label_x.gif");
        setBackground(Color.lightGray);
        Panel panel = new Panel();
        Panel panel1 = new Panel();
        Panel panel2 = new Panel();
        outputPanel = new OutputPanel();
        panel.setLayout(new GridBagLayout());
        GridBagConstraints gridbagconstraints = new GridBagConstraints();
        y_input = new String("ABCBDAB");
        x_input = new String("BDCABA");
        length_output = 0;
        lcs_output = new String("");
        btnPlay = new Button("Play");
        btnStop = new Button("Stop");
        btnPrev = new Button("Prev");
        btnNext = new Button("Next");
        btnReset = new Button("Init / Reset");
        yField = new TextField("ABCBDAB", 14);
        xField = new TextField("BDCABA", 14);
        btnHelp = new Button("Help");
        canvas = new LCSCanvas(y_input, x_input, y_label, x_label);
        label1 = new Label("String 1:", 2);
        label2 = new Label("String 2:", 2);
        btnPlay.addActionListener(this);
        btnStop.addActionListener(this);
        btnPrev.addActionListener(this);
        btnNext.addActionListener(this);
        btnReset.addActionListener(this);
        xField.addActionListener(this);
        yField.addActionListener(this);
        btnHelp.addActionListener(this);
        btnPlay.setFont(new Font("SansSerif", 0, 12));
        btnStop.setFont(new Font("SansSerif", 0, 12));
        btnPrev.setFont(new Font("SansSerif", 0, 12));
        btnNext.setFont(new Font("SansSerif", 0, 12));
        btnReset.setFont(new Font("SansSerif", 0, 12));
        xField.setFont(new Font("SansSerif", 0, 12));
        yField.setFont(new Font("SansSerif", 0, 12));
        label1.setFont(new Font("SansSerif", 0, 12));
        label2.setFont(new Font("SansSerif", 0, 12));
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnPlay, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnStop, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnPrev, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 1);
        panel.add(btnNext, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(btnReset, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(label1, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(yField, gridbagconstraints);
        gridbagconstraints.insets = new Insets(2, 0, 4, 2);
        panel.add(label2, gridbagconstraints);
        panel.add(xField, gridbagconstraints);
        panel1.add(btnHelp);
        panel2.add(canvas);
        BorderLayout borderlayout = new BorderLayout();
        setLayout(borderlayout);
        add("North", panel);
        add("Center", canvas);
        add("South", outputPanel);
        setButtons();
        canvas.setPos(pos_i, pos_j);
        outputPanel.SetContent(Integer.toString(canvas.getLength(pos_i, pos_j)), "");
    }

    public void start()
    {
    }

    public Insets getInsets()
    {
        return new Insets(3, 3, 3, 3);
    }

    public void actionPerformed(ActionEvent actionevent)
    {
        Object obj = actionevent.getSource();
        if(obj instanceof TextField)
            lcs_reset();
        if(actionevent.getActionCommand() == "Play")
        {
            if(inputHasChanged())
                lcs_reset();
            lcs_play();
        }
        if(actionevent.getActionCommand() == "Stop")
            lcs_stop();
        if(actionevent.getActionCommand() == "Prev")
            lcs_prev();
        if(actionevent.getActionCommand() == "Next")
        {
            if(inputHasChanged())
                lcs_reset();
            lcs_next();
        }
        if(actionevent.getActionCommand() == "Init / Reset")
            lcs_reset();
    }

    public boolean inputHasChanged()
    {
        return !x_input.equals(xField.getText()) || !y_input.equals(yField.getText());
    }

    public synchronized void lcs_play()
    {
        runner = new Thread(this);
        status = 0;
        runner.start();
        setButtons();
    }

    public synchronized void lcs_stop()
    {
        stop();
        setButtons();
        setButtons();
    }

    public synchronized void lcs_prev()
    {
        int i = y_input.length();
        int j = x_input.length();
        if(calc_length_done)
        {
            if(backcount == 1)
                calc_length_done = false;
            backcount--;
            canvas.setPos(calc_length_done, backcount);
            if(canvas.isDone_LCS())
                canvas.isDone_LCS(false);
        } else
        {
            if(pos_j > 1)
                pos_j--;
            else
            if(pos_i > 1)
            {
                pos_i--;
                pos_j = j;
            }
            canvas.setPos(pos_i, pos_j);
        }
        canvas.setStatus(status);
        canvas.setPos(calc_length_done, backcount);
        canvas.repaint();
        int k = canvas.getLength(pos_i, pos_j);
        outputPanel.SetContent(Integer.toString(k), canvas.getLCS(k, backcount));
        setButtons();
    }

    public synchronized void lcs_next()
    {
        int i = y_input.length();
        int j = x_input.length();
        if(pos_j < j)
            pos_j++;
        else
        if(pos_i < i)
        {
            pos_i++;
            pos_j = 1;
        } else
        {
            calc_length_done = true;
        }
        if(calc_length_done)
        {
            if(!canvas.isDone_LCS())
                backcount++;
            canvas.setPos(calc_length_done, backcount);
        } else
        {
            canvas.setPos(pos_i, pos_j);
        }
        if(canvas.isDone_LCS())
            status = 1;
        canvas.setStatus(status);
        canvas.setPos(calc_length_done, backcount);
        canvas.repaint();
        int k = canvas.getLength(pos_i, pos_j);
        outputPanel.SetContent(Integer.toString(k), canvas.getLCS(k, backcount));
        setButtonsPre();
    }

    public synchronized void lcs_reset()
    {
        x_input = xField.getText();
        y_input = yField.getText();
        if(x_input.length() > 14)
        {
            x_input = x_input.substring(0, 14);
            xField.setText(x_input);
        }
        if(y_input.length() > 14)
        {
            y_input = y_input.substring(0, 14);
            yField.setText(y_input);
        }
        pos_j = 1;
        pos_i = 1;
        calc_length_done = false;
        backcount = 0;
        canvas.isDone_LCS(false);
        canvas.setPos(pos_i, pos_j);
        canvas.setPos(calc_length_done, backcount);
        canvas.LCSReset(y_input, x_input);
        outputPanel.SetContent(Integer.toString(canvas.getLength(pos_i, pos_j)), "");
        setButtons();
    }

    public synchronized void setButtons()
    {
        if(status == 0)
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(true);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(false);
            btnReset.setEnabled(false);
        } else
        if(canvas.isDone_LCS())
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(false);
            btnReset.setEnabled(true);
        } else
        if(pos_i == 1 && pos_j == 1)
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        } else
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        }
    }

    public synchronized void setButtonsPre()
    {
        if(status == 0)
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(true);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(false);
            btnReset.setEnabled(false);
        } else
        if(canvas.isPreDone_LCS())
        {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(false);
            btnReset.setEnabled(true);
        } else
        if(pos_i == 1 && pos_j == 1)
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(false);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        } else
        {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnPrev.setEnabled(true);
            btnNext.setEnabled(true);
            btnReset.setEnabled(true);
        }
    }

    public synchronized void waitDelay(int i)
    {
        try
        {
            wait(i);
        }
        catch(InterruptedException interruptedexception) { }
    }

    public static final int UP = 1;
    public static final int LEFT = 2;
    public static final int DIAGONAL = 3;
    public static final String Y_DEFAULT = "ABCBDAB";
    public static final String X_DEFAULT = "BDCABA";
    public static final int MAX_INPUT_SIZE = 14;
    public static final int STEP_SPEED = 100;
    public volatile int pos_i;
    public volatile int pos_j;
    public volatile int backcount;
    public volatile boolean calc_length_done;
    private static final int GO = 0;
    private static final int TERMINATE = 1;
    private volatile int status;
    Thread runner;
    String y_input;
    String x_input;
    int length_output;
    String lcs_output;
    TextField yField;
    TextField xField;
    Button btnPlay;
    Button btnStop;
    Button btnPrev;
    Button btnNext;
    Button btnReset;
    Button btnHelp;
    Label label1;
    Label label2;
    LCSCanvas canvas;
    OutputPanel outputPanel;
    Image y_label;
    Image x_label;
}
```

Tu mir im Moment ein bisschen schwer damit, fremden Code zu verstehen.


----------



## The_S (18. Apr 2005)

Hab jetzt eine Denk ich verwertbare Ausgabe, nur weiß ich nicht wie ich sie auswerte :autsch:  :bae:   . Mein aktueller Code:


```
public class diffTest { 
    
	public static void main(String[] args) { 
       
		String str1 = "Fehler"; 
		String str2 = "Fehler"; 
		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;
				}
			} 
		} 
		for (int a = str1.length() - 1; a >= 0; a--) { 
			for (int b = 0; b < str2.length(); b++) { 
				System.out.print(check[a][b]); 
			} 
			System.out.println(); 
		} 	
	} 
}
```

In diesem Beispiel wird

000001
010010
000100
001000
010010
100000

ausgegeben. D. h. dass alles richtig ist, da von rechts oben diagonal bis links unten alles mit 1ern voll steht. Nur wie werte ich das in anderen Fällen am Besten aus? könne ja auch z. B. so dastehen:

Fehler => Fdhler

000001
000010
000100
001000
000010
100000

oder so:

Fehler => Fler

0001
0010
0100
0000
0010
1000

usw.


----------



## mic_checker (18. Apr 2005)

Hab mir jetzt den Algo nicht mehr genau angeschaut, aber warum kontrollierst du dann nicht einfach die Werte in der Hauptdiagonalen (also ob 1) und zählst Unterschiede (wenn das reicht).

Im andern Fall : Die Anzahl der Spalten und Zeilen ist ja schon unterschiedlich....was gibt er denn aus wenn du nicht "Fler" eingibst sondern "Fder" oder sonst was, was nicht genau übereinstimmt (bis auf Länge)?

Kann leider momentan nichts testen und kann deswegen auch nichts konkretes sagen....


----------



## The_S (18. Apr 2005)

mic_checker hat gesagt.:
			
		

> Hab mir jetzt den Algo nicht mehr genau angeschaut, aber warum kontrollierst du dann nicht einfach die Werte in der Hauptdiagonalen (also ob 1) und zählst Unterschiede (wenn das reicht).



Wie stellst du dir dass vor?



			
				mic_checker hat gesagt.:
			
		

> Im andern Fall : Die Anzahl der Spalten und Zeilen ist ja schon unterschiedlich....was gibt er denn aus wenn du nicht "Fler" eingibst sondern "Fder" oder sonst was, was nicht genau übereinstimmt (bis auf Länge)?



Hier noch ein paar Beispiele:

Fder

000*1* 
00*1*0 
0000
0000
0010
*1*000

Feehder

000000*1*
01100*1*0
0000000
000*1*000
01*1*0010
*1*000000

Feeler

00000*1*
0110*1*0
000*1*00
000000
0*1*1010
*1*00000

Feeeee

000000
0111*1*1
000000
000000
0*1*1111
*1*00000

...


----------



## mic_checker (18. Apr 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Wie stellst du dir dass vor?



Also - wenn in der Hauptdiagonalen von rechts oben nach links unten nur Einsen stehen und die Anzahl der Spalten == Anzahl der Zeilen, dann ist alles korrekt . richtig?

Du musst also sukzessive die Werte in der Hauptdiagonalen überprüfen.

Falls Anzahl Spalten != Anzahl Zeilen müsste man die Zeilen/Spalten vielleicht irgendwie ummodellieren...

Hatte eben "Arbeitsrecht" , also entschuldige bitte wenn das was ich geschrieben hab totaler Schwachsinn ist


----------



## The_S (18. Apr 2005)

Hmm ... hab bis jetzt geschafft, dass es erkennt, wenn es richtig ist und wenn ein Buchstabe zuviel ist. Noch fraglich ist es, wie ich es anstelle, damit er den Rest erkennt (also Buchstaben vergessen, Buchstaben vertauscht oder eine Kombination aus beiden). Das hier ist der Code um festzustellen ob es richtig ist, oder ob ein Buchstabe im Eingabetext zuviel ist (einfach an den ursprünglichen Dranhängen):


```
for (int a = str1.length() - 1, b = str2.length() - 1; a >= 0 && b >= 0;) {
			if (check[a][b] == 1) {
				a--;
				b--;
			}
			else {
				if (a != str1.length() - 1 && check[a + 1][b] == 1) {
					fehler++;
					a++;
				}
			}
		}
```

Hab zwar schon einiges für die anderen möglichen Varianten ausprobiert, aber nichts hat wirklich 100%ig funktioniert.


----------



## mic_checker (18. Apr 2005)

Hab gerad auch ne andere Lösung dafür gemacht, aber ist ja gehoppt wie gesprungen. Übrigens: Deine Ausgabe oben könnte etwas verwirren: Man könnte meinen die Hauptdiagonalen beginne bei [0][5] und ende bei [5][0], tatsächlich aber fängt sie ja eigentlich bei [0][0] an und endet bei [5][5] (Wenn man Array-Elemente "richtig" ausgeben lässt).

Ist nur ne Idee, aber wenn was zuviel/zuwenig eingegeben wurde, könnte man doch Spalten/Zeilen löschen , bzw. die Matrizen irgendwie in eine symmetrische Matrix transferieren...


----------



## mic_checker (18. Apr 2005)

Damit man besser sieht was ich meine:

Ursprung:
Fder

0001
0010
0000
0000
0010
1000 


Nachher:
0001
0010
0000
0000

-> Du hast zwei Zeilen gelöscht (Fehler = 2), es fehlen zwei Einsen in der neuen Hauptdiagonalen (Fehler + 2), somit hast du 4 Fehler, was ja stimmen müsste.

Fraglich ist noch ob man dafür ne allgemeine Regel aufstellen kann....

Hoffe ich hab mich nicht unklar ausgedrückt.


----------



## The_S (18. Apr 2005)

mic_checker hat gesagt.:
			
		

> Ursprung:
> Fder
> 
> 0001
> ...



Aber hier wurden keine 4 Fehler gemacht :bae: . Die letzten beiden Buchstaben sind Richtig

000*1*
00*1*0

er

zwei Buchstaben wurden ausgelassen und einer vertauscht. Der 1. Buchstabe ist wieder richtig

*1*000

F

Macht nach Adam Riese 3 Fehler. Hat ich auch schon so versucht. Hab es auch mal versucht, die Matrix einmal falsch und einmal komplett richtig zu erzeugen und dann zu vergleichen. Das hat aber auch nicht wirklich hingehauen, sobald in nem Wort ein Buchstabe zweimal vorkommt ???:L . Wie wäre denn deine Lösung für Buchstaben zuviel und richtig? Vielleicht inspiriert sie mich ja :wink: . Vielleicht könnte man aber die drei falschen Zeilen

0000
0000
0010

rauslöschen. Wäre nur die Frage nach welchem Schema man das macht ...

Stimmt, könnte echt ein wenig verwirren meine Aussage. An alle (sofern dass hier jemand liest außer dir mic_checker :wink: ) ich hab das so wie mic_checker gesagt hat gemeint. Von [0][0] zu [5][5].


----------



## mic_checker (18. Apr 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> Aber hier wurden keine 4 Fehler gemacht :bae:


arg, wer zählen kann ist klar im vorteil 

Hab leider heute und morgen nicht viel zeit mir was zu überlegen, bzw. was konkretes an code zu posten, aber es müsste eigentlich irgendwie möglich sein , nur wie ...


----------



## The_S (19. Apr 2005)

Schade, dass du keine Zeit hast. Kann mir auch nicht vorstellen, dass das so schwer ist. Ich versuchs auf jeden Fall weiter. Wenn ichs bis morgen noch net hab, kannst ja mal schauen, ob dir noch was einfällt.


----------



## mic_checker (19. Apr 2005)

Hab mal ne Frage zu deiner Implementierung des LCS:

In dem Beispiel auf der Seite entsteht eine Matrix auch mit Zahlen > 1, also 2, 3 und 4. Es wird auch jeweils auf andere Array Elemente zugegriffen (siehe Pseudocode und "Zeichnung").
In deiner Variante vergleichst du nur jeweils die Strings an den jeweiligen Stellen und setzt je nachdem den Wert auf 1 oder lässt ihn auf 0.

Warum hast du dich für diese Implementierung entschieden und nicht für die auf der Seite? Versuche gerade das von der Seite zu machen, allerdings gefällt mir der Pseudocode nicht besonders ....

Hoffe du weisst was ich meine....


----------



## mic_checker (19. Apr 2005)

Also ich hab mich nochmal dran gesetzt und hab folgenden Code entwickelt:


```
public static void lcs() {
   	String orig = "Fehler";
	   String in = "Fder";
	   int[][] l = new int[orig.length()+1][in.length()+1];
	   
	   int laenge = 0;
	   for(int i = 0,c = orig.length()-1;i < orig.length() && c >= 0;i++,c--) {
	   	for(int j = 0,k = 1;j < in.length() && k <= in.length();j++,k++) {
		   	if(orig.charAt(i) == in.charAt(j)) {
			   	l[c][k] = l[c+1][k-1] + 1; 
			   } else {
			   	if(l[c+1][k] > l[c][k-1])
				   	l[c][k] = l[c+1][k];
					else
						l[c][k] = l[c][k-1];
			   }	
			   laenge = l[c][k];   
		   }
		}
		
		System.out.println("Aktuelle Länge = "+laenge);
		
		for (int a = 0; a < l.length; a++) {
         for (int b = 0; b < l[0].length; b++) {
            System.out.print(l[a][b]);
         }
         System.out.println();
      } 
   
   }
```
Bisherige Tests gaben mir die gleiche "Matrix" aus wie die Seite die du gepostet hast, es wurde bisher auch immer die LCS korrekt ausgegeben.

Allerdings will ich mich nicht zu früh freuen, hab ich schon zu oft zuvor gemacht in dem Thread 

Bitte darum das ganze zu testen !


----------



## The_S (19. Apr 2005)

Jo, wird morgen gemacht. Hab jetzt aber keine Zeit mehr. Ich hab mich gegen die Seite entschieden, weil ich aus dem Pseudo-Code nicht schlau wurde und es auch so nicht hinbekommen hab   :wink: .


----------



## mic_checker (19. Apr 2005)

Der Pseudocode hat mich anfangs auch verwirrt, man muss sich die Matrix ganz genau angucken und darf es nicht eins zu eins vom Pseudocode übertragen, wie man oben sieht.

Wichtig ist, dass man links unten im Array anfängt und dann Reihe für Reihe weiter nach oben geht, außerdem ist wichtig das man die zwei Zählvariablen für die zwei Strings und extra Zählvariablen für Zeile/Spalte holt (zumindest ist es so einfacher).

Und wehe du findest ein Beispiel wo es nicht klappt !  

Btw. Wildcard: Du wolltest doch ein Beispiel posten *g*


----------



## Wildcard (19. Apr 2005)

Ist das das Endergebnis? Will mir das jetzt nicht alles durchlesen, was soll die Matrix am Ende bedeuten?


----------



## mic_checker (19. Apr 2005)

Das ist noch nicht direkt  das Endergebnis, da du mit dem Code von oben nur die sog. "Longest Common Subsequence" kriegst, aber wenn ich das bisher richtig beobachtet habe kannst du anhand dessen die Anzahl der Fehler ermitteln.

Beispiel:
Du ermittelst mit die LCS für den eingegebenen Text (verglichen mit Original Text) - kommt dabei die Länge des Original Textes raus ist alles fehlerfrei, kommt z.B. 0 raus, sind nur Fehler aufgetreten. Entsprechend kannst du die Anzahl der Fehler bestimmen. (Falls ich nichts falsch verstanden hab).


----------



## Wildcard (19. Apr 2005)

Also ist die Anzahl der Fehler die originallänge - das länge ergebnis?


----------



## mic_checker (19. Apr 2005)

Es ist nicht immer die Originallänge, es kommt darauf an ob man zuviel/zuwenig Buchstaben eingetippt hat.
Es gilt also den längeren Text zu ermitteln und danach das Ergebnis der Methode lcs() davon abzuziehen.

Das ist zumindest aktueller Stand der Dinge 

Falls jemand ein Beispiel findet bei dem es nicht funktioniert bitte Original String und eingegebenen String  posten.


----------



## Wildcard (19. Apr 2005)

mic_checker hat gesagt.:
			
		

> Es gilt also den längeren Text zu ermitteln und danach das Ergebnis der Methode lcs() davon abzuziehen.
> 
> 
> Falls jemand ein Beispiel findet bei dem es nicht funktioniert bitte Original String und eingegebenen String posten.




```
String orig = "aaabbbb"; 
        String in = "bbbaaa";
```
Laut Ergebnis 4 Fehler. Wie soll das gehen?  :wink:


----------



## mic_checker (19. Apr 2005)

Ach du mit deinen utopischen Beispielen 

Mal schauen wie man das ganze noch weiterentwickeln kann. Der Algorithmus ermittelt ja eigentlich "nur" in dem Fall : "aaa" als LCS. 

Für die richtigen Ergebnisse in (fast allen) Fällen müsste man wohl die komplexeren Algorithmen zu Rate ziehen , zumindest funzt es so schon besser als vorher 

Gilt noch zu klären ob es einen weiterbringt die Position der LCS zu ermitteln, ob man darauf aufbauend also noch weiter schlussfolgern kann: IN dem und dem Fall muss man noch weitere schritte einleiten......mal gucken....

edit:
Hab gerad nochmal das ganze auf der einen Seite mit dem Applet getestet, auch da kommt man zum selben Ergebnis, liegt also nicht am Code (scheinbar), sondern am Algorithmus.....weiss nicht ob das gut oder schlecht sein soll


----------



## Wildcard (19. Apr 2005)

mic_checker hat gesagt.:
			
		

> Ach du mit deinen utopischen Beispielen


  :lol: 

Womit wir aber wieder bei dem sind was ich weiter vorne schon gesagt hab: Einschränkungen. Exakt wird das IMHO sehr sehr schwierig. Von der Rechenzeit abgesehen würds mich interessieren ob dafür überhaupt schonmal jemand einen exakten Algo geschrieben hat.


----------



## mic_checker (19. Apr 2005)

Ich weiss jetzt nicht genau ob der Levenshtein Fälle wie oben erkennen würde, afaik ist der LCS ja "nur" eine vereinfachte Version des Levenshtein.

Allerdings erkennt man so schon mal in einigen Fällen Fehler die man sonst nicht erkannt hätte.

Denke also das dieser Ansatz vorerst als "eingeschränkte Version" akzeptabel ist.....


----------



## Wildcard (19. Apr 2005)

mic_checker hat gesagt.:
			
		

> Ich weiss jetzt nicht genau ob der Levenshtein Fälle wie oben erkennen würde, afaik ist der LCS ja "nur" eine vereinfachte Version des Levenshtein.


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.


			
				mic_checker hat gesagt.:
			
		

> Denke also das dieser Ansatz vorerst als "eingeschränkte Version" akzeptabel ist.....


Ich denke er ist mehr als ausreichend! Klar entwickelt man für DAU's, aber mal eben 20 Buchstaben vergessen und dann 4 vertauschen geht IMHO über einen DAU hinaus und würde mich nicht weiter interessieren.
Wenn das tatsächlich real vorkommt ist der entsprechende DAU vermutlich auch ausserstande das Ergebnis zu überprüfen  :wink:


----------



## mic_checker (20. Apr 2005)

Wildcard hat gesagt.:
			
		

> 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.



Das Themengebiet ist schon sehr interessant, wir werden wohl leider nur sehr entfernt und ansatzweise in Datenstrukturen und Algorithmen drauf eingehen ..... allerdings ist es - wie du ja auch schon mehrfach gesagt hast - eine recht komplexe Thematik.



			
				Wildcard hat gesagt.:
			
		

> Ich denke er ist mehr als ausreichend! Klar entwickelt man für DAU's, aber mal eben 20 Buchstaben vergessen und dann 4 vertauschen geht IMHO über einen DAU hinaus und würde mich nicht weiter interessieren.
> Wenn das tatsächlich real vorkommt ist der entsprechende DAU vermutlich auch ausserstande das Ergebnis zu überprüfen  :wink:


Idealfall ist eh: Der Benutzer macht keine Fehler, kriegt nur bestätigt :  0 Fehler und gut is  Müsst jetzt noch überlegen wie das Programm das gemacht hat das ich damals mal benutzt habe zum 10 Fingersystem lernen.....

Oder benutzt einer von euch noch so ein Programm und kann mal posten wie das da gehandhabt wird?


----------



## The_S (20. Apr 2005)

Bleiben wir doch bei meiner Matrix, die hat nämlich mit "aaabbb" und "bbbaaa" keine Probleme. Aber wie werte ich sie aus  :cry:  :x  :cry:

[edit] wenn die Strings gleich lang sind ist dass kein Problem, 


```
if (str1.length() == str2.length()) {
	for (int a = str1.length() - 1; a >= 0; a--) {
		if (check[a][a] != 1) {
			fehler++;
		}
	}
}
```
´

aber bei unterschiedlicher länge ... vielleicht wenn man den String irgendwie ergänzt, nur wie


----------



## The_S (20. Apr 2005)

OK, jetzt hab was gebastelt, dass scheinbar funktioniert!!! Wer findet ein Beispiel, dass falsch ist!?


```
import java.io.*;

public class diffTest { 
    
    void 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()) {
			for (int a = str1.length() - 1; a >= 0; a--) {
				if (check[a][a] != 1) {
					fehler++;
				}
			}
		}
		else {
			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) {
								a = a - c;
								b = b - d;
								d = b + 1;
								c = a + 1;
								fehler--;
							}
						}
					}
				}
			}
		}
		System.out.println("Fehler: " + fehler);
    }
    
	public static void main(String[] args) { 

		String str1 = null;
		String str2 = null;
		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());
			}
			test.diff(str1, str2);
		} 
	}
}
```

[edit] *Code angepasst*

Hab festgestellt, dass es zu Problemen kommen kann, wenn der 1. und der letzte Buchstabe falsch ist ....

[edit2] *Code angepasst*

1. und letzter Buchstabe falsch => Problem behoben


----------



## mic_checker (20. Apr 2005)

Hast du das ganze mal mit den Beispielen getestet die im Thread vorkamen?

Muss gleich wieder zur Vorlesung, kann erst heute Mittag testen.

Wenn ich das richtig seh hast du deinen umgewandelten LCS benutzt oder? 
Mal schauen ob es zu den andern Verfahren auch verständlichen Pseudocode gibt - der vom LCS war ja etwas verwirrend.
Hab mir jetzt z.B. die Damerau Levenshtein Metrik etc. nicht mehr angeschaut, aber viel. findet man da auch was passendes.

Also werd heute mittag erste Testergebnisse posten


----------



## The_S (20. Apr 2005)

Hab gerade festgestellt, dass das teilweise ganz gewaltig hackt ...

Fehler bis jetzt:


```
Original    Eingabe    Fehler    Berechnet    Bemerkung

Fehler      Fehla        2           4        Wenn ich als Original Fehla nehme und als Eingabe Fehler stimmts
Microsoft   Microshrot   3           2
Kruzifix    Kreuzfix     2           3
Hirsch      Hier         4           3
```

Weiß jemand woran das liegen könnte, und was ich ändern kann?

@mic_checker, lass dir ruhig Zeit :wink:


----------



## mic_checker (20. Apr 2005)

Ich denke mal wir müssen gar nicht erst großartig weiter testen wenn klar  ist das manchmal was falsches raus kommt (was ja eigentlich klar war).

Du könntest dich jetzt für deine Variante entscheiden, die LCS holen oder dir noch weitere Verfahren anschauen.

Ohne die von Wildcard mehrfach erwähnten "Einschränkungen" wirst du aber wohl nicht leben können  (vorerst *g*)

Hab noch was anderes, was vielleicht helfen könnte:



> Die *Damerau-Levenshtein-Metrik* gibt nichts Anderes als die Zahl der Unterschiede von 2 Wörtern an. Sie ist also ein Maß für die Ähnlichkeit zweier Wörter.


http://www.doublefind.de/technology.html

Hört sich doch net schlecht an oder? Mal gucken wie sich das  implementierungstechnisch umsetzen lässt.


----------



## The_S (20. Apr 2005)

Hey!!! Google macht mir Konkurenz!!! Manchmal wird hier auf meinem Thread rechts oben ein Link zu einem 10-Fingersystem-Lernprogramm angezeigt http://www.neuber.com/schreibtrainer/index.html?ref=google.

Zurück zum Thema:

Ich denke mal, dass Algorithmus nur bestimmte Fehler nicht beachtet. Wenn ich allerdings weiß, wo der Fehler liegt, könnte ich das noch einbauen und ihn vielleicht (nahezu :wink: ) Perfekt machen.

Den Link schau ich mir jetzt gleich mal an.

[edit] Leider findet man im www nicht sonderlich viel zur Damerau-Levenshtein-Metrik. Kennt jemand ne gute seite?


----------



## mic_checker (20. Apr 2005)

Hab auch nicht viel gefunden.

Aber ich hab mich noch mal an den Levenshtein  gemacht:


```
public static int levenshtein() {
   	/* Schritt 1 */
   	String s = "HIRSCH";
	   String t = "HIER";
   	int n = s.length();
	   int m = t.length();
	   int cost,minimum;
	   char chs,cht;
	   
	   if(n == 0 || m == 0)
	   	return 0;
		
		int hoehe = n + 1;
		int breite = m + 1;
		
		int[][] matrix = new int[hoehe][breite];
		
		/* Schritt 2 */
		for(int i = 0;i < hoehe;i++)
			matrix[i][0] = i;
	
		for(int j = 0;j < breite;j++)
			matrix[0][j] = j;
			
		/* Schritte 3 - 6 */
		for(int i = 1;i < hoehe;i++) {
			chs = s.charAt(i-1);
			
			for(int j = 1;j < breite;j++) {
				cht = t.charAt(j-1);
				
				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;
			}
		}
		
		
		/*
		* Ausgabe der Matrix
		*/
		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();
      } 
		
		return matrix[n][m];	
   }
```
Hab nachher gesehen das ne Implementierung einige Zeilen drunter stand, meine müsste aber auch stimmen, da es nach der Algorithmus Beschreibung der selben Seite gemacht wurde (und nur hier und da etwas abweicht).

Die Ausgabe der Matrix kannst du natürlich raus nehmen, hab ich nur testweise reingemacht.

Vielleicht klappt es damit besser als mit LCS.


----------



## The_S (20. Apr 2005)

Levenshtein bin ich irgendwie nie richtig durchgestiegen ... Deswegen, was gibt er mir zurück? Was soll ich damit anfangen?


----------



## mic_checker (20. Apr 2005)

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 (20. Apr 2005)

Ä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 (20. Apr 2005)

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


----------



## mic_checker (20. Apr 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> 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 (20. Apr 2005)

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 (20. Apr 2005)

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 (20. Apr 2005)

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 (20. Apr 2005)

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 (20. Apr 2005)

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 (20. Apr 2005)

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

Lewenstein Wikipedia.de


----------



## mic_checker (20. Apr 2005)

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 (20. Apr 2005)

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 (21. Apr 2005)

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 (21. Apr 2005)

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 (21. Apr 2005)

"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 (21. Apr 2005)

Hab das soweit alles Verstanden, bis auf dass hier:



			
				mic_checker hat gesagt.:
			
		

> ...
> ... 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.



			
				mic_checker hat gesagt.:
			
		

> ...
> ...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 (21. Apr 2005)

Hobbit_Im_Blutrausch hat gesagt.:
			
		

> 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.



> mic_checker hat gesagt.:
> 
> 
> 
> ...


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 (21. Apr 2005)

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 (21. Apr 2005)

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


----------



## The_S (21. Apr 2005)

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 (21. Apr 2005)

> 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 (21. Apr 2005)

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 (21. Apr 2005)

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 (21. Apr 2005)

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 (21. Apr 2005)

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 (21. Apr 2005)

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 (21. Apr 2005)

Wildcard hat gesagt.:
			
		

> 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 (21. Apr 2005)

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 (21. Apr 2005)

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....


----------

