Vom Fischen und vom Rüsseln...

Womit sich Elefanten am liebsten den Arsch abwischen:


Denn der Charming-Bär hat ausgedient.

Ich bin es leid, immer diese Informatiker-Witze. Wir sind hier doch nicht bei Geekcore. Aber Derby ist auch nicht schlecht.

1234567654321

Also ich weiß genau, was ich am 14.02.2009 um 01:27:34.321 MEZ machen werde. Richtig, schlafen. Im Nachhinein kann man diesen Zeitpunkt aber als Palindrom-Differenz-in-Millisekunden-zwischen-jetzt-und-Mitternacht-01.01.1970-UTC feiern. Oder auch nicht. Sicher, es gibt nicht wenige von solchen Palindromen, aber dieser hier sieht doch besonders schön aus.

Nachtrag: Auch heise.de hat etwas dazu zu sagen.

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".