Editierinstanz

[Malcolm X]

Hallo,

es geht darum einen Algorithmus zu implementieren welcher die miminale Anzahl von Operationen ermittelt um Zeichenkette a in Zeichenkette b zu überführen.

Erlaubte Operationen sind:

- einen Buchstaben löschen
- einen Buchstaben einfügen
- einen Buchstaben umbenennen

Beispielsweise haben 'apfel' und 'pferd' die Editierinstanz 3:

- löschen von a
- umbenennen von l nach r
- einfügen von d

Das Problem soll nun so gelöst werden indem Teilaufgaben durch Präfixbetrachtung gelöst werden.

Habt ihr eine Ahnung wie ein passender Algorithmus arbeiten könnte um diese Aufgabe zu lösen. Weiss nicht so richtig wie ich anfangen soll.

 

[André Uhres]

..Weiss nicht so richtig wie ich anfangen soll..

Ich fang mal hiermit an:

       StringBuilder sb = new StringBuilder("apfel");
        sb.deleteCharAt(0);
        sb.replace(3,4,"r");
        sb.insert(4,"d");
        System.out.println(sb.toString());

Dann wissen wir schonmal welche Methoden wir nehmen können zum löschen usw..

 

[Beni]

Irre ich mich, oder beschäftigt ihr euch mit dynamischem Programmieren? Jedenfalls kann man das so lösen:

Man bastelt eine Tabelle, oben wird "_apfel", links "_pferd" eingetragen. Das obere linke Feld wird mit 0 initialisiert. Jedes andere Feld sollte den minimalen Wert haben, wobei das entweder oben+1 (löschen), links+1 (einfügen) oder oben-links+1 falls unterschiedliche Buchstaben da stehen, oder =oben-links falls gleiche Buchstaben dastehen.

Eine Tabelle so gefüllt:

	_	P	F	E	R	D
_	0	1	2	3	4	5
A	1	1	2	3	4	5
P	2	1	2	3	4	5
F	3	2	1	2	3	4
E	4	3	2	1	2	3
L	5	4	3	2	2	3

Die Reihenfolge, was wann gemacht wurde, erhält man indem man unten-rechts beginnt rückwärts zu rechnen. Das ergibt hier:

Distanz: 3

delete: A
shift: P = P
shift: F = F
shift: E = E
insert: R
replace: L -> D

Da ich nicht so sicher bin, ob meine Erklärungen stimmen, der Code der das erzeugt siehr folgendermassen aus: (und ja, ich löse gerade deine Hausaufgaben, aber das Problem hat mich selbst interessiert - Freundlichkeit ist das also nicht).

package forum;

import java.util.Stack;

public class Test{
	public static void main(String[] args) {
		test( "APFEL", "PFERD" );
	}
	
	public static void test( String a, String b ){
		a = "_" + a;
		b = "_" + b;
		
		int[][] table = new int[a.length()][b.length()];
		
		table[0][0] = 0;
		for( int i = 1; i < table.length; i++ )
			table[i][0] = i;
		
		for( int i = 1; i < table[0].length; i++ )
			table[0][i] = i;
		
		for( int i = 1; i < a.length(); i++ ){
			for( int j = 1; j < b.length(); j++ ){
				if( a.charAt( i ) == b.charAt( j )){
					table[i][j] = min( table[i-1][j-1], table[i][j-1]+1, table[i-1][j]+1 );
				}
				else{
					table[i][j] = min( table[i-1][j-1]+1, table[i][j-1]+1, table[i-1][j]+1 );
				}
			}
		}
		
		
		// print
		for( int i = 0; i < b.length(); i++ )
			System.out.print( "\t" + b.charAt( i ) );
		System.out.println();
		
		for( int i = 0; i < a.length(); i++ ){
			System.out.print( a.charAt(i) );
			
			for( int j = 0; j < b.length(); j++ ){
				System.out.print( "\t" + table[i][j] );
			}
			
			System.out.println();
		}
		
		// Find solution
		System.out.println( "Distanz: " + table[a.length()-1][b.length()-1] );
		System.out.println();
		int x = a.length()-1;
		int y = b.length()-1;
		
		Stack<String> result = new Stack<String>();
		
		while( x > 0 || y > 0 ){
			if( x > 0 && y > 0 && table[x][y] - 1 == table[x-1][y-1] ){
				result.push( "replace: " + a.charAt( x ) + " -> " + b.charAt( y ));
				x--;
				y--;
			}
			else if( x > 0 && table[x][y] - 1 == table[x-1][y] ){
				result.push( "delete: " + a.charAt( x ));
				x--;
			}
			else if( y > 0 && table[x][y] - 1 == table[x][y-1] ){
				result.push( "insert: " + b.charAt( y ));
				y--;
			}
			else if( x > 0 && y > 0 && table[x][y] == table[x-1][y-1]){
				result.push( "shift: " + a.charAt( x ) + " = " + b.charAt( y ));
				x--;
				y--;
			}
			else throw new IllegalStateException( "Something is wrong" );
		}
		
		while( !result.isEmpty() )
			System.out.println( result.pop() );
	}
	
	public static int min( int a, int b, int c ){
		if( a < b && a < c )
			return a;
		
		if( b < c )
			return b;
		
		return c;
	}
}

 

[Guest]

Moin Moin

Tip:
http://de.wikipedia.org/wiki/Editierdistanz

oder Stichwort Levenshtein-Distanz

cu Jens

 

[Beni]

Ey, wieso schreibe ich das denn ein zweites Mal? :? :###

 

[Malcolm X]

demnach ergibt sich doch folgende rekursive Lösungsbeschreibung:

Wort eins = a = (a1, ..., ak)
Wort zwei = b = (b1, ..., bk)

d(i,j) = 0 falls i=0 und j=0

d(i,j) = i falls j=0

d(i,j) = j falls i=0

d(i,j) = min{ d(i-1, j-1), d(j, j-1) + 1, d(i-1,j)+1 } falls ai = bj

d(i,j) = min{ d(i-1, j-1)+1, d(j, j-1) + 1, d(i-1,j)+1 } sonst


Könnt ihr mir verraten wie denn nun die Richtigkeit dieser rekursiven Lösungsbeschreibung begründet werden kann. Ich will jetzt keine vollständige Induktion sondern einfach nur eine kurze Erklärung so das ich mir klar machen kann warum dieser Algorithmus das richtige Ergebnis liefert.

 

[Malcolm X]

Man bastelt eine Tabelle, oben wird "_apfel", links "_pferd" eingetragen. Das obere linke Feld wird mit 0 initialisiert. Jedes andere Feld sollte den minimalen Wert haben, wobei das entweder oben+1 (löschen), links+1 (einfügen) oder oben-links+1 falls unterschiedliche Buchstaben da stehen, oder =oben-links falls gleiche Buchstaben dastehen.

Mein Problem ist das ich nicht verstehe warum das so realisiert wurde. Ich würde es gerne verstehen und nicht auswendig lernen.

warum die erste Spalte bzw. Zeile nach diesem Prinzip gefüllt werden ist mir noch klar.

 

[Beni]

Bei d(i,j) gehst du davon aus, dass du schon weisst, wie d(i-1,j), d(i-1,j-1) und d(i,j-1) hergestellt werden. Jetzt musst du nur noch den besten Übergang finden. Das Herstellen von d(i-1,j) etc ist aber einfacher als d(i,j), denn die möglichen 3 Vorgänger arbeiten mit kleineren Strings. So vereinfacht sich das, bis nur noch leere Strings verglichen werden müssen.

Du kannst die Rekursion ausprogrammieren (Stichwort: Backtracking), die Tabelle ist einfach eine Abkürzung dafür.

 

[Guest]

Du kannst die Rekursion ausprogrammieren (Stichwort: Backtracking), die Tabelle ist einfach eine Abkürzung dafür.

Ich versuche gerade die Rekursion auszuprogrammieren. Mein Problem ist das ich damit nicht so richtig klar komme u.a., weil ich die Tabelle die sich auf die dynamische Programmierung bezieht noch nicht so richtig verstanden habe. Vielleicht kannst Du mir ja noch den ein oder anderen Tipp bezüglich der Ausprogrammierung geben.

Wäre sehr nett...

 

[Malcolm X]

Mal angenommen ich will Mein nach Dein überführen. Soll nun das Feld in der Matrix ausfüllt werden in welchem steht wieviel Operationen mindestens notwendig sind um M nach D zu überführen so brauche ich laut des Algorithmus folgende drei Felder um dieses Feld ausfüllen zu können

Epsilon ==> Epsiloon = 0
Epsikon ==> M = 1
Epsilon ==> D = 1

Von diesen drei Feldern wähle ich mir nun das mit dem minimalen Wert aus. Nun addiere ich noch 1 dazu da M und D verschieden sind.

Was mir nicht klar ist ist warum die drei besagten Felder zur Lösung führen.