Fehler in der String-Distanz-Berechnung

[oldshoe]

Irgendwie bekomme ich einen Fehler in der String-Distanz-Berechnung.
Ich habe versucht die Damerau-Levensthein-Distanz zu implementieren und dafür folgenden Code gefunden. Allerdings denke ich, dass das Ergebnis z.B. für "Areal" und "Arel" so wie beim normalen Levensthein =1 sein sollte oder irre ich mich?

hier auch mal der PseudoCode: Damerau-Levenshtein distance - Wikipedia

public static int damlev(String s, String t) /* never tested! */
	{
		int l1 = s.length();
		int l2 = t.length();
		int n = l1 + 1;
		int m = l2 + 1;
		if (m == 1)
			return n - 1;
		if (n == 1)
			return m -1;
		int[] d = new int[m * n];
		int k = 0;
		for (int i = 0; i < n; i++)
			d[i] = i;
		k = n;
		for (int i = 1; i < m; i++)
		{
			d[k] = i;
			k += n;
		}
		int f = 0, g = 0, h = 0, min = 0, b = 0, c = 0, cost = 0, tr = 0;
		for (int i = 1; i < n; i++)
		{
			k = i;
			f = 0;
			for (int j = 1; j < m; j++)
			{
				h = k;
				k += n;
				min = d[h] + 1;
				b = d[k - 1] + 1;
				if (g < l1 && f < l2)
					if (s.charAt(g) == t.charAt(f))
						cost = 0;
					else
					{
						cost = 1;
						/* Sean's transposition */
						if (j < l2 && i < l1)
								if (s.charAt(i) == t.charAt(f) && s.charAt(g) == t.charAt(j))
								{
									tr = d[(h) - 1]/* + 1*/; // transposition yields deletion cost at next iteration?
									if (tr < min)
										min = tr;
								}
					}
				else
					cost = 1;
				c = d[h - 1] + cost;
				if (b < min)
					min = b;
				if (c < min)
					min = c;
				d[k] = min;
				/*
				System.out.println("i=" + i + ", j=" + j);
				for (int v = 0; v < m; v++)
				{
					for (int w = 0; w < n; w++)
						System.out.print(d[v * n + w] + " ");
					System.out.println();
				}
				*/
				f = j;
			}
			g = i;
		}
		return d[k];
	}

 

[Matze75]

Hi

dein Progamm funktioniert bei mir einwandfrei mußt nur noch eine main Methode einfügen z.B.:

public static void main(String[] args) {
	int z=durchschnitt.damlev ("Areal","Aral");
	System.out.println("Levenshtein Distanz:" +z);
}

 

[eRaaaa]

hu, also bei mir funktionierts auch.
(auch z.b. eine wirkliche damerau-levenshtein-distanz (beispiel von wikipedia: „Raisch“ ↔ „Rasich“) = 1

Ich habe versucht die Damerau-Levensthein-Distanz zu implementieren und dafür folgenden Code gefunden.

find ich ja mal gut :>

aber irgendwie sieht dein code unnötig kompliziert aus. du könntest eig. FAST den code von wiki 1zu1 übernehmen, c# ist da sehr ähnlich 😀

public class Levensthein {

	public static void main(String[] args) {
		System.out.println(damlev("Areal", "Arel"));
	}

	public static int damlev(String src, String dest) /* never tested! */
	{
		int[][] d = new int[src.length() + 1][dest.length() + 1];
		int i, j, cost;
		char[] str1 = src.toCharArray();
		char[] str2 = dest.toCharArray();
		for (i = 0; i <= str1.length; i++) {
			d[i][0] = i;
		}
		for (j = 0; j <= str2.length; j++) {
			d[0][j] = j;
		}
		for (i = 1; i <= str1.length; i++) {
			for (j = 1; j <= str2.length; j++) {

				if (str1[i - 1] == str2[j - 1])
					cost = 0;
				else
					cost = 1;

				d[i][j] = Math.min(d[i - 1][j] + 1, // Deletion
						Math.min(d[i][j - 1] + 1, // Insertion
								d[i - 1][j - 1] + cost)); // Substitution

				if ((i > 1) && (j > 1) && (str1[i - 1] == str2[j - 2])
						&& (str1[i - 2] == str2[j - 1])) {
					d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
				}
			}
		}
		return d[str1.length][str2.length];
	}

}

 

[oldshoe]

Vielen Dank erstmal für eure Anteilnahme😉
Ich frage mich nur wieso "Areal" und "Arel" mit Damerau-Levensthein = 2 liefert und mit Levensthein =1. Denn der Levensthein-Ansatz wurde doch nur um das Vertauschen 2er Zeichen erweitert und es geht ja um die minimale Anzahl an Operationen.
Jemand eine Idee?

 

[eRaaaa]

???:L

System.out.println("Distanz = "+damlev("Areal", "Arel"));

liefert mir 1. so wie es sein soll und so wie es auch von dir vermutet wird 😀
hast du vllt ein tippfehler bei dir in einem der strings? :>

 

[oldshoe]

ja super, das ist mir auch eben aufgefallen! Deine Version liefert =1 aber meine vorgeschlagene liefert = 2 also war meine auch fehlerhaft!
Vielen Dank!:toll::toll::toll: