Editierdistanz

[Malcolm X]

Hallo,

könnt ihr mir sagen warum folgende Rekursion, zur Ermittlung der Editierdistanz von zwei Wörtern, das richtige Ergebnis liefert?

 public int findDistance(String a, String b, int lenghtA, int lengthB)
   {
	   int cij;
	   
       if(lenghtA == 0)
	       return lengthB;                                            // es sind lengthB Operationen nötig um a nach b zu überführen.
	   if(lengthB == 0)
	       return lenghtA;                                            // es sind lengthA Operationen nötig um b nach a zu überführen.
	   if(a.charAt(lenghtA-1) == b.charAt(lengthB-1))                 // schauen ob die letzten beiden Zeichen identisch sind
		   cij = 0;
	   else
		   cij = 1;

	   return min(findDistance(a, b, lenghtA-1, lengthB  ) + 1,     
	              findDistance(a, b, lenghtA,   lengthB-1) + 1,    
	              findDistance(a, b, lenghtA-1, lengthB-1) + cij);  
   }

 

[Malcolm X]

Im Prinzip würde es schon reichen wenn ihr mir folgende Frage beantworten könntet:

folgende Operationen sind möglich:

- löschen von Buchstaben
- ersetzen von Buchstaben
- hinzufügen von Buchstaben

- ich weiss das ich genau eine Operation brauche um vom leeren Wort zu b zu kommen (hinzufügen)
- ich weiss das ich genau eine Operation brauche um von a zum leeren Wort zu kommen (löschen)
- ich weiss das ich 0 Operationen brauche um vom leeren Wort zum leeren Wort zu kommen.

Nun will ich die minimale Anzahl an Operationen ermitteln um von a nach b zu kommen:

warum darf ich das über folgende Formel ermitteln?

a nach b = min( leeres Wort nach b, a nach leeres Wort, leeres Wort nach leeres Wort)

 

[The_S]

Hm ... ok. Bevor du gar keine Antwort bekommst sag ich mal was dazu.

Ich hab kA was eine Editierdistanz ist, geschweige denn was du eigentlich möchtest ???:L . Möchtest du die minimale Anzahl rausbekommen, die nötig sind um ein Wort in ein anderes Wort zu "verwandeln"? Sprich eine Fehlerkorrektur?

 

[Malcolm X]

Hallo,

hab's nun endlich verstanden. Brauche also keine Hilfe mehr. Wenn es dich trotzdem interessiert kannst Du dir folgenden Beitrag anschauen:

Editierdistanz

 

[The_S]

Ah, sags doch gleich ... sowas hät ich noch rumfliegen gehabt (Gibt auch hier im Forum nen Thread dazu). Aber hast ja schon