summaryrefslogtreecommitdiff
path: root/mteval
diff options
context:
space:
mode:
authorChris Dyer <cdyer@allegro.clab.cs.cmu.edu>2014-09-06 02:55:29 -0400
committerChris Dyer <cdyer@allegro.clab.cs.cmu.edu>2014-09-06 02:55:29 -0400
commitb40c064987b1fb188daf040a068a459711385eac (patch)
tree20630b59fa74bb0b60a292424a357e338bc872dc /mteval
parent5dfecf3ac4a0755255bb806f7d556f1f8e7dbc38 (diff)
ld commit
Diffstat (limited to 'mteval')
-rw-r--r--mteval/levenshtein.h29
1 files changed, 29 insertions, 0 deletions
diff --git a/mteval/levenshtein.h b/mteval/levenshtein.h
new file mode 100644
index 00000000..13a97047
--- /dev/null
+++ b/mteval/levenshtein.h
@@ -0,0 +1,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