0.07.18
C++ Open Travel Request Parsing Library
Loading...
Searching...
No Matches
Levenshtein.cpp
Go to the documentation of this file.
1
// //////////////////////////////////////////////////////////////////////
2
// Import section
3
// //////////////////////////////////////////////////////////////////////
4
// STL
5
#include <string>
6
#include <vector>
7
// OpenTREP
8
#include <
opentrep/bom/Levenshtein.hpp
>
9
10
namespace
OPENTREP
{
11
12
// //////////////////////////////////////////////////////////////////
13
int
Levenshtein::getDistance
(
const
std::string& iSource,
14
const
std::string& iTarget) {
15
16
// Step 1
17
18
const
int
n = iSource.length();
19
const
int
m = iTarget.length();
20
21
if
(n == 0) {
22
return
m;
23
}
24
25
if
(m == 0) {
26
return
n;
27
}
28
29
// Definition of Matrix Type
30
typedef
std::vector<std::vector<int> > Matrix_T;
31
32
Matrix_T matrix (n+1);
33
34
// Size the vectors in the 2.nd dimension. Unfortunately C++ doesn't
35
// allow for allocation on declaration of 2.nd dimension of vec of vec
36
37
for
(
int
i = 0; i <= n; i++) {
38
matrix[i].resize(m+1);
39
}
40
41
// Step 2
42
43
for
(
int
i = 0; i <= n; i++) {
44
matrix[i][0]=i;
45
}
46
47
for
(
int
j = 0; j <= m; j++) {
48
matrix[0][j]=j;
49
}
50
51
// Step 3
52
53
for
(
int
i = 1; i <= n; i++) {
54
55
const
char
s_i = iSource[i-1];
56
57
// Step 4
58
59
for
(
int
j = 1; j <= m; j++) {
60
61
const
char
t_j = iTarget[j-1];
62
63
// Step 5
64
65
int
cost;
66
if
(s_i == t_j) {
67
cost = 0;
68
69
}
else
{
70
cost = 1;
71
}
72
73
// Step 6
74
75
const
int
above = matrix[i-1][j];
76
const
int
left = matrix[i][j-1];
77
const
int
diag = matrix[i-1][j-1];
78
int
cell = std::min ( above + 1, std::min (left + 1, diag + cost));
79
80
// Step 6A: Cover transposition, in addition to deletion,
81
// insertion and substitution. This step is taken from:
82
// Berghel, Hal ; Roach, David : "An Extension of Ukkonen's
83
// Enhanced Dynamic Programming ASM Algorithm"
84
// (http://www.acm.org/~hlb/publications/asm/asm.html)
85
86
if
(i>2 && j>2) {
87
int
trans = matrix[i-2][j-2] + 1;
88
89
if
(iSource[i-2] != t_j) {
90
trans++;
91
}
92
93
if
(s_i != iTarget[j-2]) {
94
trans++;
95
}
96
97
if
(cell > trans) {
98
cell = trans;
99
}
100
}
101
102
matrix[i][j] = cell;
103
}
104
}
105
106
// Step 7
107
108
return
matrix[n][m];
109
}
110
111
}
Levenshtein.hpp
OPENTREP::Levenshtein::getDistance
static int getDistance(const std::string &iSource, const std::string &iTarget)
Definition
Levenshtein.cpp:13
OPENTREP
Definition
BasChronometer.cpp:10
Generated on Mon May 5 2025 00:00:00 for OpenTREP by
1.13.2