ldistv.c

NIST Handwriting OCR Testbed

/*
# proc: ldv - computes the Levenstein Distance between two strings and returns
# proc:       their corresponding alignment.
*/

#ifndef lint
  static char rcsid[] = "$Header$";
#endif


/* LINTLIBRARY */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <sys/param.h>


#include <align.h>
#include <pointers.h>
#include <defs.h>



#define MIN3(x,y,z)		(( x < y) ? min( x, z ) : min( y, z ))

#define EQUAL( x, y )		( case_sensitive ? \
				     ( ref[x-1] == hyp[y-1] ) : \
				     ( toupper( ref[x-1] ) == toupper( hyp[y-1] )))


#define DISTANCE(i,j)		(    distance[ (i) * ( hyplen + 1 ) + (j) ] )
#define BP(i,j)			(          bp[ (i) * ( hyplen + 1 ) + (j) ] )
#define PATH(i,j)		(        path[ (i) * ( hyplen + 1 ) + (j) ] )
#define SUB_PENALTY(i,j)	( sub_penalty[ (i) * ( hyplen + 1 ) + (j) ] )



	/*
	 *  Returns distance between reference and hypothesis strings,
	 *	or -1 on failure.
	 *  On success, sets *vlen to the length of the alignment, and
	 *	sets v[] to contain *vlen integers representing the
	 *	positions in the alignment.
	 *  The array v[] must be allocated by the caller. The length
	 *	needed for it depends on the alignment itself, but it's
	 *	maximum length is the sum of the lengths of the strings.
	 *  The character strings need to be unsigned so that we can
	 *	index into arrays using their elements' values.
	 */


int ldv ( ref, hyp, ap, fp, vlen, v )
u_char *ref;
u_char *hyp;
struct align_params_t *ap;
FILE *fp;			/* if non-NULL, print debugging code to here */

int *vlen;			/* OUTPUT */
int v[];			/* OUTPUT */
{
register int i, j;
int *distance;
char *bp;
char *path;
int reflen, hyplen, arr_size;
int eq, d1, d2, d3, dmin;
int c;


int case_sensitive = ap->case_sensitive;
int *ins_penalty = ap->insv;
int *del_penalty = ap->delv;
int *sub_penalty = ap->subv;

reflen = strlen( (char *)ref );				/* >= 0 */
hyplen = strlen( (char *)hyp );				/* >= 0 */
arr_size = ( reflen + 1 ) * ( hyplen + 1 );	/* >= 1 */


distance = (int *) malloc( arr_size * sizeof(int) );
if ( distance == INULL )
	return -1;

bp = malloc( arr_size * sizeof(int) );
if ( bp == CNULL ) {
	free((char *) distance );
	return -1;
}

path = malloc( arr_size );
if ( path == CNULL ) {
	free((char *) distance );
	free( bp );
	return -1;
}


DISTANCE(0,0) = 0;
BP(0,0) = CHAR_OK;
PATH(0,0) = '*';

for ( j=1; j <= hyplen; j++ ) {
	DISTANCE(0,j) = DISTANCE(0,j-1) + ins_penalty[ hyp[j] ];
	BP(0,j) = CHAR_INS;
	PATH(0,j) = ' ';
}

for ( j=1; j <= reflen; j++ ) {
	DISTANCE(j,0) = DISTANCE(j-1,0) + del_penalty[ ref[j] ];
	BP(j,0) = CHAR_DEL;
	PATH(j,0) = ' ';
}

for ( i=1; i <= reflen; i++ )
  for ( j=1; j <= hyplen; j++ ) {

	PATH(i,j) = ' ';

	eq = EQUAL( i, j );

	d1 = DISTANCE(i-1,j-1);
	if ( ! eq )
		d1 += SUB_PENALTY( ref[i], hyp[j] );

	d2 = DISTANCE(i,j-1) + ins_penalty[ hyp[j] ];
	d3 = DISTANCE(i-1,j) + del_penalty[ ref[i] ];

	dmin = MIN3( d1, d2, d3 );
	DISTANCE(i,j) = dmin;

	if ( d1 == dmin )
		BP(i,j) = eq ? CHAR_OK : CHAR_SUB;
	else
		BP(i,j) = ( d2 == dmin ) ? CHAR_INS : CHAR_DEL;
  }


i = reflen;
j = hyplen;
*vlen = 0;
while ( i >= 0 && j >= 0 ) {

	PATH(i,j) = '*';
	v[ *vlen ] = BP(i,j);
	++*vlen;

	switch ( BP(i,j) ) {

		case CHAR_OK:
			i--; j--;
			break;
		case CHAR_SUB:
			i--; j--;
			break;
		case CHAR_INS:
			j--;
			break;
		case CHAR_DEL:
			i--;
			break;

		default:
#ifdef DEBUG
			(void) fprintf( stderr, "ldv: bad bp value %d\n",
					BP(i,j) );
#endif
			free((char *) distance );
			free( bp );
			free( path );
			return -1;

	}
}


if ( fp != FPNULL ) {
	for ( i=0; i < *vlen; i++ )
		(void) fprintf( fp, "%c ", getalignchar( v[i] ));
	(void) fprintf( fp, "\n" );
}

--*vlen;
reverse_ivec( *vlen, v );

if ( fp != FPNULL ) {
	for ( i=0; i <= *vlen; i++ )
		(void) fprintf( fp, "%c ", getalignchar( v[i] ));
	fprintf( fp, "\n" );
}
 

if ( fp != FPNULL ) {

	(void) fprintf( fp, "\n      " );
	for ( j=0; j <= hyplen; j++ )
		(void) fprintf( fp, "   %c %3d %c", ' ', j, ( j == 0 ) ? ' ' : hyp[j-1] );
	(void) fprintf( fp, "\n\n" );

	for ( i=0; i <= reflen; i++ ) {

		(void) fprintf( fp, "%3d %c: ", i, ( i == 0 ) ? '0' : ref[i-1] );

		for ( j=0; j <= hyplen; j++) {

			c = getalignchar( BP(i,j ));
			(void) fprintf( fp, "   %3d %c %c",
				DISTANCE(i,j), c, PATH(i,j) );

		}

		(void) fprintf( fp, "\n" );
	}

}

dmin = DISTANCE( reflen, hyplen );

free( (char *) distance );
free( bp );
free( path );

return dmin;

} /*  ldv()  */