1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
| #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;
} |
