]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | use std::cmp; | |
12 | ||
c34b1796 | 13 | pub fn lev_distance(me: &str, t: &str) -> usize { |
1a4d82fc JJ |
14 | if me.is_empty() { return t.chars().count(); } |
15 | if t.is_empty() { return me.chars().count(); } | |
16 | ||
85aaf69f | 17 | let mut dcol: Vec<_> = (0..t.len() + 1).collect(); |
1a4d82fc JJ |
18 | let mut t_last = 0; |
19 | ||
20 | for (i, sc) in me.chars().enumerate() { | |
21 | ||
22 | let mut current = i; | |
23 | dcol[0] = current + 1; | |
24 | ||
25 | for (j, tc) in t.chars().enumerate() { | |
26 | ||
27 | let next = dcol[j + 1]; | |
28 | ||
29 | if sc == tc { | |
30 | dcol[j + 1] = current; | |
31 | } else { | |
32 | dcol[j + 1] = cmp::min(current, next); | |
33 | dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1; | |
34 | } | |
35 | ||
36 | current = next; | |
37 | t_last = j; | |
38 | } | |
39 | } | |
40 | ||
41 | dcol[t_last + 1] | |
42 | } | |
43 | ||
44 | #[test] | |
45 | fn test_lev_distance() { | |
46 | use std::char::{ from_u32, MAX }; | |
47 | // Test bytelength agnosticity | |
c34b1796 | 48 | for c in (0..MAX as u32) |
1a4d82fc JJ |
49 | .filter_map(|i| from_u32(i)) |
50 | .map(|i| i.to_string()) { | |
85aaf69f | 51 | assert_eq!(lev_distance(&c[..], &c[..]), 0); |
1a4d82fc JJ |
52 | } |
53 | ||
54 | let a = "\nMäry häd ä little lämb\n\nLittle lämb\n"; | |
55 | let b = "\nMary häd ä little lämb\n\nLittle lämb\n"; | |
56 | let c = "Mary häd ä little lämb\n\nLittle lämb\n"; | |
57 | assert_eq!(lev_distance(a, b), 1); | |
58 | assert_eq!(lev_distance(b, a), 1); | |
59 | assert_eq!(lev_distance(a, c), 2); | |
60 | assert_eq!(lev_distance(c, a), 2); | |
61 | assert_eq!(lev_distance(b, c), 1); | |
62 | assert_eq!(lev_distance(c, b), 1); | |
63 | } |