Mercurial > hg > toys

annotate c++/breathalyzer/levenshtein.c++ @ 20:2b8cbff9f9ce

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
move breathalyzer under c++
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Fri, 17 Apr 2015 15:34:05 -0400
parents breathalyzer/levenshtein.c++@7ce081b92ff9
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
57fc6080db4d Implement levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents:
diff changeset
1 #include <string>
57fc6080db4d Implement levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents:
diff changeset
2 #include <vector>
2
0748d902784c Fix off-by-ones, don't use std globally
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 0
diff changeset
3 #include <iostream>
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
4 #include <algorithm>
0
57fc6080db4d Implement levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents:
diff changeset
5
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
6 size_t levenshtein(std::string& a,
6
cad6633bc1fc Preliminary final form
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 4
diff changeset
7 std::string& b)
0
57fc6080db4d Implement levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents:
diff changeset
8 {
2
0748d902784c Fix off-by-ones, don't use std globally
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 0
diff changeset
9 using namespace std;
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
10 size_t asize=a.size(), bsize = b.size();
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
11
4
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
12 //Just need two rows at a time
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
13 vector<size_t> prevrow(bsize+1), thisrow(bsize+1);
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
14
4
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
15 for(size_t i = 0; i <= bsize; i++)
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
16 prevrow[i] = i;
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
17
4
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
18 for(size_t i = 1; i <= asize; i ++)
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
19 {
4
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
20 thisrow[0] = i;
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
21 for(size_t j = 1; j <= bsize; j++)
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
22 {
4
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
23 thisrow[j] = min(prevrow[j-1] + size_t(a[i-1] != b[j-1]),
de7bbee608ee Abandon narrowing idea -- no actual benefit
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 3
diff changeset
24 1 + min(prevrow[j],thisrow[j-1]) );
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
25 }
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
26 swap(thisrow,prevrow);
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
27 }
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
28
6
cad6633bc1fc Preliminary final form
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 4
diff changeset
29 return prevrow[bsize];
cad6633bc1fc Preliminary final form
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 4
diff changeset
30 }
3
56c58a177cde First attempt at optimising levenshtein distance
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 2
diff changeset
31