Example

Give first word:
> ekhnilinen
Give second word:
> teknillinen

String 'ekhnilinen' will be compared with 'teknillinen'.

WLD =   3

       t  e  k  n  i  l  l  i  n  e  n 

    0  1  2  3  4  5  6  7  8  9 10 11 
e   1  1  1  2  3  4  5  6  7  8  9 10 
k   2  2  2  1  2  3  4  5  6  7  8  9 
h   3  3  3  2  2  3  4  5  6  7  8  9 
n   4  4  4  3  2  3  4  5  6  6  7  8 
i   5  5  5  4  3  2  3  4  5  6  7  8 
l   6  6  6  5  4  3  2  3  4  5  6  7 
i   7  7  7  6  5  4  3  3  3  4  5  6 
n   8  8  8  7  6  5  4  4  4  3  4  5 
e   9  9  8  8  7  6  5  5  5  4  3  4 
n  10 10  9  9  8  7  6  6  6  5  4  3 

Program

#include <stdio.h>
#include <string.h>

#define STRMAX 20

int min( int x, int y, int z );

int main( void ) {
  int p[ STRMAX ][ STRMAX ];
  int q[ STRMAX ];
  int r[ STRMAX ];
  int D[ STRMAX ][ STRMAX ];
  int i, j, k;
  char A[ STRMAX ], B[ STRMAX ];
  int m1, m2, m3;
  int WLD;

  printf("DEMO OF COMPUTING EDIT DISTANCE BY DYNAMIC PROGRAMMING\n\n");
  printf("Teuvo Kohonen: Self-Organizing Maps, Springer, 1995, pp. 20-21\n");
  printf("Programmed by Timo Honkela, 22.11.1995\n");
  printf("A bug detected and corrected by Sabine Buchholz, 1.4.1998\n");
  printf("Another bug detected and corrected by Heikki Junes, 23.2.2004\n\n");

  printf("Give first word:\n");
  printf("> ");
  fgets( A, 100, stdin );
  printf("Give second word:\n");
  printf("> ");
  fgets( B, 100, stdin );

  printf("\nString '%s' will be compared with '%s'.\n\n", A, B );

  /* Unweighted Levenshtein distance (p. 20) */

  for( i=0; i<strlen( A ); i++ ) {
    for( j=0; j<strlen( B ); j++ ) {
      if( A[ i ] == B[ j ] ) {
        p[ i ][ j ] = 0;
      }
      else {
        p[ i ][ j ] = 1;
      }
    }
    r[ i ] = 1;
  }
        
  for( j=0; j<strlen( B ); j++ ) {
    q[ j ] = 1;
  }

  /* Computation of WLD, Table 1.1, p. 21 */

  D[ 0 ][ 0 ] = 0;

  for( i=0; i<strlen( A ); i++ ) {
    D[ i+1 ][ 0 ] = D[ i ][ 0 ] + r[ i ];   /* corrected */
  }
  
  
  for( j=0; j<strlen( B ); j++ ) {
    D[ 0 ][ j+1 ] = D[ 0 ][ j ] + q[ j ];   /* corrected */
  }
  
  for( i=0; i<strlen( A ); i++ ) {
    for( j=0; j<strlen( B ); j++ ) {
      m1 = D[ i ][ j ] + p[ i ][ j ];
      m2 = D[ i+1 ][ j ] + q[ j ];
      m3 = D[ i ][ j+1 ] + r[ i ];
      D[ i+1 ][ j+1 ] = min( m1, m2, m3 );
    }
  }

  WLD = D[ strlen( A ) ][ strlen( B ) ];     /* corrected */

  /* Printing results */

  printf("WLD = %3d\n\n", WLD);

  printf("      ");
  for( j=0; j<strlen( B ); j++ ) {
    printf(" %c ", B[ j ] );
  }
  printf("\n\n");
  printf("   %2d ",D[ 0 ][ 0 ]);
  for( j=0; j<strlen( B ); j++ ) {
      printf("%2d ", D[ 0 ][ j+1 ] );
  }

  printf("\n");

  for( i=0; i<strlen( A ); i++ ) {
    printf("%c  %2d ", A[ i ], D[ i+1 ][ 0 ] );
    for( j=0; j<strlen( B ); j++ ) {
      printf("%2d ", D[ i+1 ][ j+1 ] );
    }
    printf("\n");
  }
  printf("\n");
}
      

/* Minimum of three numbers with minimal number of comparisons */

int min( int x, int y, int z ) {
  int mi;

  if( y < x )
    mi = y;
  else
    mi = x;

  if( z < mi )
    mi = z;

  return( mi );
}

Back to my home page.