blob: 3ae56cf5beefb56ea575c8577e37029340f4ad22 (
plain)
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
|
#ifndef LEVENSHTEIN_H_
#define LEVENSHTEIN_H_
namespace cdec {
template <typename V>
inline unsigned LevenshteinDistance(const V& a, const V& b) {
const unsigned m = a.size(), n = b.size();
std::vector<unsigned> edit((m + 1) * 2);
for (unsigned i = 0; i <= n; i++) {
for (unsigned j = 0; j <= m; j++) {
if (i == 0)
edit[j] = j;
else if (j == 0)
edit[(i % 2) * (m + 1)] = i;
else
edit[(i % 2) * (m + 1) + j] = std::min(std::min(
edit[(i % 2) * (m + 1) + j - 1] + 1,
edit[((i - 1) % 2) * (m + 1) + j] + 1),
edit[((i - 1) % 2) * (m + 1) + (j - 1)]
+ (a[j - 1] == b[i - 1] ? 0 : 1));
}
}
return edit[(n % 2) * (m + 1) + m];
}
}
#endif
|
