From Wikipedia article; Iterative with two matrix rows.
(s, t)
| 5 | import sys |
| 6 | |
| 7 | def levenshtein(s, t): |
| 8 | ''' From Wikipedia article; Iterative with two matrix rows. ''' |
| 9 | if s == t: return 0 |
| 10 | elif len(s) == 0: return len(t) |
| 11 | elif len(t) == 0: return len(s) |
| 12 | v0 = [None] * (len(t) + 1) |
| 13 | v1 = [None] * (len(t) + 1) |
| 14 | for i in range(len(v0)): |
| 15 | v0[i] = i |
| 16 | for i in range(len(s)): |
| 17 | v1[0] = i + 1 |
| 18 | for j in range(len(t)): |
| 19 | cost = 0 if s[i] == t[j] else 1 |
| 20 | v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost) |
| 21 | for j in range(len(v0)): |
| 22 | v0[j] = v1[j] |
| 23 | |
| 24 | return v1[len(t)] |
| 25 | |
| 26 | f1 = sys.argv[1] |
| 27 | f2 = sys.argv[2] |