OpenTREP Logo  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
9
10namespace 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}
static int getDistance(const std::string &iSource, const std::string &iTarget)