src/libsyntax/util/lev_distance.rs

   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 use symbol::Symbol;
  13
  14 /// To find the Levenshtein distance between two strings
  15 pub fn lev_distance(a: &str, b: &str) -> usize {
  16     // cases which don't require further computation
  17     if a.is_empty() {
  18         return b.chars().count();
  19     } else if b.is_empty() {
  20         return a.chars().count();
  21     }
  22
  23     let mut dcol: Vec<_> = (0..b.len() + 1).collect();
  24     let mut t_last = 0;
  25
  26     for (i, sc) in a.chars().enumerate() {
  27         let mut current = i;
  28         dcol[0] = current + 1;
  29
  30         for (j, tc) in b.chars().enumerate() {
  31             let next = dcol[j + 1];
  32             if sc == tc {
  33                 dcol[j + 1] = current;
  34             } else {
  35                 dcol[j + 1] = cmp::min(current, next);
  36                 dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
  37             }
  38             current = next;
  39             t_last = j;
  40         }
  41     } dcol[t_last + 1]
  42 }
  43
  44 /// To find the best match for a given string from an iterator of names
  45 /// As a loose rule to avoid the obviously incorrect suggestions, it takes
  46 /// an optional limit for the maximum allowable edit distance, which defaults
  47 /// to one-third of the given word
  48 pub fn find_best_match_for_name<'a, T>(iter_names: T,
  49                                        lookup: &str,
  50                                        dist: Option<usize>) -> Option<Symbol>
  51     where T: Iterator<Item = &'a Symbol> {
  52     let max_dist = dist.map_or_else(|| cmp::max(lookup.len(), 3) / 3, |d| d);
  53     iter_names
  54     .filter_map(|&name| {
  55         let dist = lev_distance(lookup, &name.as_str());
  56         match dist <= max_dist {    // filter the unwanted cases
  57             true => Some((name, dist)),
  58             false => None,
  59         }
  60     })
  61     .min_by_key(|&(_, val)| val)    // extract the tuple containing the minimum edit distance
  62     .map(|(s, _)| s)                // and return only the string
  63 }
  64
  65 #[test]
  66 fn test_lev_distance() {
  67     use std::char::{from_u32, MAX};
  68     // Test bytelength agnosticity
  69     for c in (0..MAX as u32)
  70              .filter_map(|i| from_u32(i))
  71              .map(|i| i.to_string()) {
  72         assert_eq!(lev_distance(&c[..], &c[..]), 0);
  73     }
  74
  75     let a = "\nMäry häd ä little lämb\n\nLittle lämb\n";
  76     let b = "\nMary häd ä little lämb\n\nLittle lämb\n";
  77     let c = "Mary häd ä little lämb\n\nLittle lämb\n";
  78     assert_eq!(lev_distance(a, b), 1);
  79     assert_eq!(lev_distance(b, a), 1);
  80     assert_eq!(lev_distance(a, c), 2);
  81     assert_eq!(lev_distance(c, a), 2);
  82     assert_eq!(lev_distance(b, c), 1);
  83     assert_eq!(lev_distance(c, b), 1);
  84 }