Minimale Editierdistanz

In der Computerlinguistik ist die minimale Editierdistanz (auch Levenshtein-Distanz) ein Abstandsmaß für Zeichenketten, die angibt, wieviel Änderungsoperationen notwendig sind, um einen String in einen anderen umzuwandeln.

Um diese händisch zu berechnen benutzt man eine Distanz-Matrix, in der die Änderungsoperationen eingetragen werden und in der oberen, rechten Ecke steht zum Schluss der Berechnung das Ergebnis der Distanz. Für das Beispiel otto und oktan ergäbe sich eine solche Matrix:

o|4 3 4 3 4 5
t|3 2 3 2 3 4
t|2 1 2 1 2 3
o|1 0 1 2 3 4
#|0 1 2 3 4 5
/ # o k t a n

Also ist die minimale Editierdistanz für otto und oktan 5. Dabei wurden für die Entfernung und Hinzufügung eines Buchstabens die Kosten von 1 angesetzt, dementsprechend für das Ändern eines Buchstabens in einen anderen die Kosten von 2.

Folgender Java-Code berechnet die minimale Editierdistanz:

public class MinimumEditDistance {
  
  private int[][] matrix;
  private String source,target;
  private int n,m;
  private int minimumEditDistance=-1;
  
  public MinimumEditDistance(String source, String target)
  {
    this.source=source;
    this.target=target;
    init();
  }
  
  private void init()
  {
    m=source.length();
    n=target.length();
    
    matrix=new int[n+1][m+1];
    matrix[0][0]=0;
    for(int i=1;i<=n;i++)
    {
      matrix[i][0]=matrix[i-1][0]+insCost(target.charAt(i-1));
    }
    for(int j=1;j<=m;j++)
    {
      matrix[0][j]=matrix[0][j-1]+delCost(source.charAt(j-1));
    }
  }

  public String getSource() {
    return source;
  }

  public void setSource(String source) {
    this.source = source;
    init();
  }

  public String getTarget() {
    return target;
  }

  public void setTarget(String target) {
    this.target = target;
    init();
  }
 
  public int insCost(char c)
  {
    return 1;
  }
  
  public int delCost(char c)
  {
    return 1;
  }
  public int substCost(char c1,char c2)
  {
    if(c1==c2)
    {
      return 0;
    }
    
    return 2;
  }
  
  public void computeMinimumEditDistance()
  {
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++)
      {
        matrix[i][j]=Math.min(Math.min(
                matrix[i-1][j]+insCost(target.charAt(i-1)),
                matrix[i-1][j-1]+substCost(source.charAt(j-1), target.charAt(i-1))),
                matrix[i][j-1]+delCost(source.charAt(j-1)));
      }
    }
    minimumEditDistance=matrix[n][m];
  }
  
  public int getMinimumEditDistance()
  {
    if(minimumEditDistance==-1)
    {
      computeMinimumEditDistance();
    }
    return minimumEditDistance;
  }
  
  public void printMatrix()
  {
    for (int i=0;i<matrix.length;i++)
    {
      for(int j=0;j<matrix[0].length;j++)
      {
         System.out.print(matrix[i][j]);
         System.out.print(" ");
      }
      System.out.println("");
    }    
  }
  
  public void printMatrixWithStrings()
  {
    char[][] out=new char[n+2][m+2];
    
    for(int i=0;i<matrix.length;i++)
    {
      for(int j=0;j<matrix.length;j++)
      {
        out[i+1][j+1]=(new Integer(matrix[i][j])).toString().charAt(0);
      }
    }
    
    for(int I=0;I<out.length;I++)
    {
      for(int J=0;J<out[I].length;J++)
      {
        System.out.print(out[I][J]);
        System.out.print(" ");
      }
      System.out.println();
    }
  }
  
  public static void main(String[] args)
  {
 if(args.length!=2)
 {System.out.println("usage: java MinimumEditDistance String1 String2");}
 else
 {System.out.println((new MinimumEditDistance(args[0],args[1])).getMinimumEditDistance());}
  }
}

Zum Ausführen genügt nach dem Kompilieren "java MinimumEditDistance String1 String2".