1/**
2 * `levenshtein-rs` - levenshtein
3 *
4 * MIT licensed.
5 *
6 * Copyright (c) 2016 Titus Wormer <tituswormer@gmail.com>
7 */
8#[must_use]
9pub fn levenshtein(a: &str, b: &str) -> usize {
10 let mut result = 0;
11
12 /* Shortcut optimizations / degenerate cases. */
13 if a == b {
14 return result;
15 }
16
17 let length_a = a.chars().count();
18 let length_b = b.chars().count();
19
20 if length_a == 0 {
21 return length_b;
22 }
23
24 if length_b == 0 {
25 return length_a;
26 }
27
28 /* Initialize the vector.
29 *
30 * This is why it’s fast, normally a matrix is used,
31 * here we use a single vector. */
32 let mut cache: Vec<usize> = (1..).take(length_a).collect();
33 let mut distance_a;
34 let mut distance_b;
35
36 /* Loop. */
37 for (index_b, code_b) in b.chars().enumerate() {
38 result = index_b;
39 distance_a = index_b;
40
41 for (index_a, code_a) in a.chars().enumerate() {
42 distance_b = if code_a == code_b {
43 distance_a
44 } else {
45 distance_a + 1
46 };
47
48 distance_a = cache[index_a];
49
50 result = if distance_a > result {
51 if distance_b > result {
52 result + 1
53 } else {
54 distance_b
55 }
56 } else if distance_b > distance_a {
57 distance_a + 1
58 } else {
59 distance_b
60 };
61
62 cache[index_a] = result;
63 }
64 }
65
66 result
67}
68