1 #ifndef ROSE_EditDistance_Levenshtein_H
2 #define ROSE_EditDistance_Levenshtein_H
5 namespace EditDistance {
10 typedef std::pair<T,
size_t> KeyVal;
11 typedef std::list<KeyVal> KeyValList;
14 void unique_push_zero(
const T& key) {
15 for (
typename KeyValList::iterator pi=pairs.begin(); pi!=pairs.end(); ++pi) {
19 pairs.push_front(KeyVal(key, 0));
22 size_t& operator[](
const T& key) {
23 for (
typename KeyValList::iterator pi=pairs.begin(); pi!=pairs.end(); ++pi) {
41 if (src.empty() || tgt.empty())
42 return std::max(src.size(), tgt.size());
44 const size_t x = src.size();
45 const size_t y = tgt.size();
46 std::vector<std::vector<size_t> > score(x+2, std::vector<size_t>(y+2, 0));
47 size_t score_ceil = x + y;
48 score[0][0] = score_ceil;
49 for (
size_t i=0; i<=x; ++i) {
51 score[i+1][0] = score_ceil;
53 for (
size_t j=0; j<=y; ++j) {
55 score[0][j+1] = score_ceil;
59 for (
size_t i=0; i<x; ++i)
60 dict.unique_push_zero(src[i]);
61 for (
size_t j=0; j<y; ++j)
62 dict.unique_push_zero(tgt[j]);
64 for (
size_t i=1; i<=x; ++i) {
65 for (
size_t j=1; j<=y; ++j) {
66 if (src[i-1]==tgt[j-1]) {
67 score[i+1][j+1] = score[i][j];
69 score[i+1][j+1] = std::min(score[i][j], std::min(score[i+1][j], score[i][j+1])) + 1;
75 return score[x+1][y+1];