Folgendes Groovy Skript berechnet die Levenshtein Distanz zweier Zeichenketten. Die Levenshtein Distanz ist ein Maß bezüglich der Operationen Ersetzen, Einfügen und Löschen, um die Gleichheit beider Zeichenketten zu erreichen. In anderen Worten, die Levenshtein Distanz ist ein Maß für die Ähnlichkeit zweier Zeichenketten. Der Algorithmus benötigt im Gegensatz zur normalen Implementierung nur linearen Speicherplatz.


01 /**
02  * Berechnet die Levensthein Distanz der beiden Strings x und y.
03  * 
04  * @param x String x des Vergleichs, nicht null.
05  * @param y String y des Vergleichs, nicht null.
06  * @return die Levensthein Distanz der beiden Strings x und y
07  */
08 int linearLD(String x, String y) {
09   int n = y.length();
10   int m = x.length();
11  
12   if (n == 0) return m;
13   if (m == 0) return n;
14  
15   def T = [];
16   T[0] = 0;
17   for (j in 1..n) {
18     T[j] = T[j-1] + 1;
19   }
20   for (i in 1..m) {
21     def s = T[0];
22     T[0] = T[0] + 1;
23     def c = T[0];
24     for (j in 1..n) {
25       def sub = s + (x.charAt(i-1) == y.charAt(j-1) ? 0 : 1);
26       def del = T[j] + 1;
27       def ins = c + 1;
28       c = Math.min(Math.min(sub, del), ins);
29       s = T[j];
30       T[j] = c;
31     }
32   }
33   return T[n];
34 }
35 
36 println linearLD("Lin", "Lang");

Das Ergebnis des Aufrufs lautet 2, da zwei Operationen zum Angleichen der Zeichenketten notwendig wären.

Hier der Algorithmus nochmal in Java:


01 public class LinearLD {
02 
03   /**
04    * Berechnet die Levensthein Distanz der beiden Strings x und y.
05    * 
06    * @param x String x des Vergleichs, nicht null.
07    * @param y String y des Vergleichs, nicht null.
08    * @return die Levensthein Distanz der beiden Strings x und y
09    */
10   public static int linearLD(String x, String y) {
11     int n = y.length();
12     int m = x.length();
13    
14     if (n == 0) return m;
15     if (m == 0) return n;
16    
17     int[] T = new int[n+1];
18     T[0] = 0;
19     for (int j=1; j <= n; j++) {
20       T[j] = T[j-1] + 1;
21     }
22     for (int i=1; i<=m; i++) {
23       int s = T[0];
24       T[0] = T[0] + 1;
25       int c = T[0];
26       for (int j=1; j<=n; j++) {
27         int sub = s + (x.charAt(i-1) == y.charAt(j-1) ? 0 : 1);
28         int del = T[j] + 1;
29         int ins = c + 1;
30         c = Math.min(Math.min(sub, del), ins);
31         s = T[j];
32         T[j] = c;
33       }
34     }
35     return T[n];
36   }
37   
38   public static void main(String[] args) {
39     System.out.println(LinearLD.linearLD("", "Tier"));
40   }
41 }

Ein praktischer Anwendungsfall für die Berechnung der Levenshtein Distanz ist z.B. im Falle der automatisierten Zusammenführung von unterschiedlichen Stammdatenbeständen gegeben, in denen etwa Vergleiche auf Personen- oder Ortsnamen durchgeführt werden müssen, und in denen Umlaute unterschiedliche dargestellt (z.B. ü und ue) werden.