Java - Levenshtein-Distanz

From XennisWiki
Jump to: navigation, search

In information theory and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after Vladimir Levenshtein, who considered this distance in 1965. (Wikipedia)

Code

Das Programm berechnet die Levenshtein-Distanz mittels dynamischer Programmierung.

LevenshteinDistanz.java

public class LevenshteinDistanz {

	public static final int C1 = 2;
	public static final int C2 = 3;
	
	public static void main(String[] args) {
		System.out.println(lev("Hallo", "Hally"));
	}

	/**
	 * Berechnet die Levenshtein-Distanz (Editierdistanz) zweier Strings.
	 * 
	 * @param s
	 *            String über dem Alphabet
	 * @param t
	 *            String über dem Alphabet
	 * @return Editierdistanz der beiden Strings
	 */
	public static int lev(String s, String t) {
		int sLen = s.length();
		int tLen = t.length();

		int[][] lev = new int[sLen+1][tLen+1];

		for (int sCount = 0; sCount < sLen; sCount++) {
			for (int tCount = 0; tCount < tLen; tCount++) {
				
				if (sCount == 0 && tCount == 0) {
					lev[0][0] = 0;
				}
				else if (sCount == 0) {
					lev[0][tCount] = tCount * C1;
				}
				else if (tCount == 0) {
					lev[sCount][0] = sCount * C1;
				}
				else if (s.charAt(sCount) == t.charAt(tCount)) {
					lev[sCount][tCount] = lev[sCount - 1][tCount - 1];
				} else {
					lev[sCount][tCount] = min(
							lev[sCount - 1][tCount] + C1,
							lev[sCount][tCount - 1] + C1,
							lev[sCount - 1][tCount - 1] + C2);
				}
			}
		}

		return lev[sLen-1][tLen-1];
	}

	/**
	 * Berechnet das Minimum von drei Zahlen.
	 * 
	 * @param a
	 *            Zahl
	 * @param b
	 *            Zahl
	 * @param c
	 *            Zahl
	 * @return Minimum der drei Zahlen
	 */
	private static int min(int a, int b, int c) {
		return Math.min(a, Math.min(b, c));
	}
}