Implementation of Levenshtein Distance in C++

by kalai 2010-01-12 16:56:17

In C++, the size of an array must be a constant, and this code fragment causes an error at compile time:

int sz = 5;
int arr[sz];

This limitation makes the following C++ code slightly more complicated than it would be if the matrix could simply be declared as a two-dimensional array, with a size determined at run-time.

In C++ it's more idiomatic to use the System Template Library's vector class, as Anders Sewerin Johansen has done in an alternative C++ implementation.

Here is the definition of the class (distance.h):

class Distance
{
public:
int LD (char const *s, char const *t);
private:
int Minimum (int a, int b, int c);
int *GetCellPointer (int *pOrigin, int col, int row, int nCols);
int GetAt (int *pOrigin, int col, int row, int nCols);
void PutAt (int *pOrigin, int col, int row, int nCols, int x);
};

Here is the implementation of the class (distance.cpp):

#include "distance.h"
#include <string.h>
#include <malloc.h>

//****************************
// Get minimum of three values
//****************************

int Distance::Minimum (int a, int b, int c)
{
int mi;

mi = a;
if (b < mi) {
mi = b;
}
if (c < mi) {
mi = c;
}
return mi;

}

//**************************************************
// Get a pointer to the specified cell of the matrix
//**************************************************

int *Distance::GetCellPointer (int *pOrigin, int col, int row, int nCols)
{
return pOrigin + col + (row * (nCols + 1));
}

//*****************************************************
// Get the contents of the specified cell in the matrix
//*****************************************************

int Distance::GetAt (int *pOrigin, int col, int row, int nCols)
{
int *pCell;

pCell = GetCellPointer (pOrigin, col, row, nCols);
return *pCell;

}

//*******************************************************
// Fill the specified cell in the matrix with the value x
//*******************************************************

void Distance::PutAt (int *pOrigin, int col, int row, int nCols, int x)
{
int *pCell;

pCell = GetCellPointer (pOrigin, col, row, nCols);
*pCell = x;

}

//*****************************
// Compute Levenshtein distance
//*****************************

int Distance::LD (char const *s, char const *t)
{
int *d; // pointer to matrix
int n; // length of s
int m; // length of t
int i; // iterates through s
int j; // iterates through t
char s_i; // ith character of s
char t_j; // jth character of t
int cost; // cost
int result; // result
int cell; // contents of target cell
int above; // contents of cell immediately above
int left; // contents of cell immediately to left
int diag; // contents of cell immediately above and to left
int sz; // number of cells in matrix

// Step 1

n = strlen (s);
m = strlen (t);
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
sz = (n+1) * (m+1) * sizeof (int);
d = (int *) malloc (sz);

// Step 2

for (i = 0; i <= n; i++) {
PutAt (d, i, 0, n, i);
}

for (j = 0; j <= m; j++) {
PutAt (d, 0, j, n, j);
}

// Step 3

for (i = 1; i <= n; i++) {

s_i = s[i-1];

// Step 4

for (j = 1; j <= m; j++) {

t_j = t[j-1];

// Step 5

if (s_i == t_j) {
cost = 0;
}
else {
cost = 1;
}

// Step 6

above = GetAt (d,i-1,j, n);
left = GetAt (d,i, j-1, n);
diag = GetAt (d, i-1,j-1, n);
cell = Minimum (above + 1, left + 1, diag + cost);
PutAt (d, i, j, n, cell);
}
}

// Step 7

result = GetAt (d, n, m, n);
free (d);
return result;

}

Tagged in:

1699
like
0
dislike
0
mail
flag

You must LOGIN to add comments