vendor/strsim-0.8.0/src/lib.rs

   1 //! This library implements string similarity metrics.
   2
   3 use std::char;
   4 use std::cmp::{max, min};
   5 use std::collections::HashMap;
   6
   7 #[derive(Debug, PartialEq)]
   8 pub enum StrSimError {
   9     DifferentLengthArgs
  10 }
  11
  12 pub type HammingResult = Result<usize, StrSimError>;
  13
  14 /// Calculates the number of positions in the two strings where the characters
  15 /// differ. Returns an error if the strings have different lengths.
  16 ///
  17 /// ```
  18 /// use strsim::hamming;
  19 ///
  20 /// match hamming("hamming", "hammers") {
  21 ///     Ok(distance) => assert_eq!(3, distance),
  22 ///     Err(why) => panic!("{:?}", why)
  23 /// }
  24 /// ```
  25 pub fn hamming(a: &str, b: &str) -> HammingResult {
  26     let (mut ita, mut itb, mut count) = (a.chars(), b.chars(), 0);
  27     loop {
  28         match (ita.next(), itb.next()){
  29             (Some(x), Some(y)) => if x != y { count += 1 },
  30             (None, None) => return Ok(count),
  31             _ => return Err(StrSimError::DifferentLengthArgs),
  32         }
  33     }
  34 }
  35
  36 /// Calculates the Jaro similarity between two strings. The returned value
  37 /// is between 0.0 and 1.0 (higher value means more similar).
  38 ///
  39 /// ```
  40 /// use strsim::jaro;
  41 ///
  42 /// assert!((0.392 - jaro("Friedrich Nietzsche", "Jean-Paul Sartre")).abs() <
  43 ///         0.001);
  44 /// ```
  45 pub fn jaro(a: &str, b: &str) -> f64 {
  46     if a == b { return 1.0; }
  47
  48     let a_len = a.chars().count();
  49     let b_len = b.chars().count();
  50
  51     // The check for lengths of one here is to prevent integer overflow when
  52     // calculating the search range.
  53     if a_len == 0 || b_len == 0 || (a_len == 1 && b_len == 1) {
  54         return 0.0;
  55     }
  56
  57     let search_range = (max(a_len, b_len) / 2) - 1;
  58
  59     let mut b_consumed = Vec::with_capacity(b_len);
  60     for _ in 0..b_len {
  61         b_consumed.push(false);
  62     }
  63     let mut matches = 0.0;
  64
  65     let mut transpositions = 0.0;
  66     let mut b_match_index = 0;
  67
  68     for (i, a_char) in a.chars().enumerate() {
  69         let min_bound =
  70             // prevent integer wrapping
  71             if i > search_range {
  72                 max(0, i - search_range)
  73             } else {
  74                 0
  75             };
  76
  77         let max_bound = min(b_len - 1, i + search_range);
  78
  79         if min_bound > max_bound {
  80             continue;
  81         }
  82
  83         for (j, b_char) in b.chars().enumerate() {
  84             if min_bound <= j && j <= max_bound && a_char == b_char &&
  85                !b_consumed[j] {
  86                 b_consumed[j] = true;
  87                 matches += 1.0;
  88
  89                 if j < b_match_index {
  90                     transpositions += 1.0;
  91                 }
  92                 b_match_index = j;
  93
  94                 break;
  95             }
  96         }
  97     }
  98
  99     if matches == 0.0 {
 100         0.0
 101     } else {
 102         (1.0 / 3.0) * ((matches / a_len as f64) +
 103                        (matches / b_len as f64) +
 104                        ((matches - transpositions) / matches))
 105     }
 106 }
 107
 108 /// Like Jaro but gives a boost to strings that have a common prefix.
 109 ///
 110 /// ```
 111 /// use strsim::jaro_winkler;
 112 ///
 113 /// assert!((0.911 - jaro_winkler("cheeseburger", "cheese fries")).abs() <
 114 ///         0.001);
 115 /// ```
 116 pub fn jaro_winkler(a: &str, b: &str) -> f64 {
 117     let jaro_distance = jaro(a, b);
 118
 119     // Don't limit the length of the common prefix
 120     let prefix_length = a.chars()
 121                          .zip(b.chars())
 122                          .take_while(|&(a_char, b_char)| a_char == b_char)
 123                          .count();
 124
 125     let jaro_winkler_distance =
 126         jaro_distance + (0.1 * prefix_length as f64 * (1.0 - jaro_distance));
 127
 128     if jaro_winkler_distance <= 1.0 {
 129         jaro_winkler_distance
 130     } else {
 131         1.0
 132     }
 133 }
 134
 135 /// Calculates the minimum number of insertions, deletions, and substitutions
 136 /// required to change one string into the other.
 137 ///
 138 /// ```
 139 /// use strsim::levenshtein;
 140 ///
 141 /// assert_eq!(3, levenshtein("kitten", "sitting"));
 142 /// ```
 143 pub fn levenshtein(a: &str, b: &str) -> usize {
 144     if a == b { return 0; }
 145
 146     let a_len = a.chars().count();
 147     let b_len = b.chars().count();
 148
 149     if a_len == 0 { return b_len; }
 150     if b_len == 0 { return a_len; }
 151
 152     let mut cache: Vec<usize> = (1..b_len+1).collect();
 153
 154     let mut result = 0;
 155     let mut distance_a;
 156     let mut distance_b;
 157
 158     for (i, a_char) in a.chars().enumerate() {
 159         result = i;
 160         distance_b = i;
 161
 162         for (j, b_char) in b.chars().enumerate() {
 163             let cost = if a_char == b_char { 0 } else { 1 };
 164             distance_a = distance_b + cost;
 165             distance_b = cache[j];
 166             result = min(result + 1, min(distance_a, distance_b + 1));
 167             cache[j] = result;
 168         }
 169     }
 170
 171     result
 172 }
 173
 174 /// Calculates a normalized score of the Levenshtein algorithm between 0.0 and
 175 /// 1.0 (inclusive), where 1.0 means the strings are the same.
 176 ///
 177 /// ```
 178 /// use strsim::normalized_levenshtein;
 179 ///
 180 /// assert!((normalized_levenshtein("kitten", "sitting") - 0.57142).abs() < 0.00001);
 181 /// assert!((normalized_levenshtein("", "") - 1.0).abs() < 0.00001);
 182 /// assert!(normalized_levenshtein("", "second").abs() < 0.00001);
 183 /// assert!(normalized_levenshtein("first", "").abs() < 0.00001);
 184 /// assert!((normalized_levenshtein("string", "string") - 1.0).abs() < 0.00001);
 185 /// ```
 186 pub fn normalized_levenshtein(a: &str, b: &str) -> f64 {
 187     if a.is_empty() && b.is_empty() {
 188         return 1.0;
 189     }
 190     1.0 - (levenshtein(a, b) as f64) / (a.chars().count().max(b.chars().count()) as f64)
 191 }
 192
 193 /// Like Levenshtein but allows for adjacent transpositions. Each substring can
 194 /// only be edited once.
 195 ///
 196 /// ```
 197 /// use strsim::osa_distance;
 198 ///
 199 /// assert_eq!(3, osa_distance("ab", "bca"));
 200 /// ```
 201 pub fn osa_distance(a: &str, b: &str) -> usize {
 202     let a_len = a.chars().count();
 203     let b_len = b.chars().count();
 204     if a == b { return 0; }
 205     else if a_len == 0 { return b_len; }
 206     else if b_len == 0 { return a_len; }
 207
 208     let mut prev_two_distances: Vec<usize> = Vec::with_capacity(b_len + 1);
 209     let mut prev_distances: Vec<usize> = Vec::with_capacity(b_len + 1);
 210     let mut curr_distances: Vec<usize> = Vec::with_capacity(b_len + 1);
 211
 212     let mut prev_a_char = char::MAX;
 213     let mut prev_b_char = char::MAX;
 214
 215     for i in 0..(b_len + 1) {
 216         prev_two_distances.push(i);
 217         prev_distances.push(i);
 218         curr_distances.push(0);
 219     }
 220
 221     for (i, a_char) in a.chars().enumerate() {
 222         curr_distances[0] = i + 1;
 223
 224         for (j, b_char) in b.chars().enumerate() {
 225             let cost = if a_char == b_char { 0 } else { 1 };
 226             curr_distances[j + 1] = min(curr_distances[j] + 1,
 227                                         min(prev_distances[j + 1] + 1,
 228                                             prev_distances[j] + cost));
 229             if i > 0 && j > 0 && a_char != b_char &&
 230                a_char == prev_b_char && b_char == prev_a_char {
 231                 curr_distances[j + 1] = min(curr_distances[j + 1],
 232                                             prev_two_distances[j - 1] + 1);
 233             }
 234
 235             prev_b_char = b_char;
 236         }
 237
 238         prev_two_distances.clone_from(&prev_distances);
 239         prev_distances.clone_from(&curr_distances);
 240         prev_a_char = a_char;
 241     }
 242
 243     curr_distances[b_len]
 244
 245 }
 246
 247 /// Like optimal string alignment, but substrings can be edited an unlimited
 248 /// number of times, and the triangle inequality holds.
 249 ///
 250 /// ```
 251 /// use strsim::damerau_levenshtein;
 252 ///
 253 /// assert_eq!(2, damerau_levenshtein("ab", "bca"));
 254 /// ```
 255 pub fn damerau_levenshtein(a: &str, b: &str) -> usize {
 256     if a == b { return 0; }
 257
 258     let a_chars: Vec<char> = a.chars().collect();
 259     let b_chars: Vec<char> = b.chars().collect();
 260     let a_len = a_chars.len();
 261     let b_len = b_chars.len();
 262
 263     if a_len == 0 { return b_len; }
 264     if b_len == 0 { return a_len; }
 265
 266     let mut distances = vec![vec![0; b_len + 2]; a_len + 2];
 267     let max_distance = a_len + b_len;
 268     distances[0][0] = max_distance;
 269
 270     for i in 0..(a_len + 1) {
 271         distances[i + 1][0] = max_distance;
 272         distances[i + 1][1] = i;
 273     }
 274
 275     for j in 0..(b_len + 1) {
 276         distances[0][j + 1] = max_distance;
 277         distances[1][j + 1] = j;
 278     }
 279
 280     let mut chars: HashMap<char, usize> = HashMap::new();
 281
 282     for i in 1..(a_len + 1) {
 283         let mut db = 0;
 284
 285         for j in 1..(b_len + 1) {
 286             let k = match chars.get(&b_chars[j - 1]) {
 287                 Some(value) => value.clone(),
 288                 None => 0
 289             };
 290
 291             let l = db;
 292
 293             let mut cost = 1;
 294             if a_chars[i - 1] == b_chars[j - 1] {
 295                 cost = 0;
 296                 db = j;
 297             }
 298
 299             let substitution_cost = distances[i][j] + cost;
 300             let insertion_cost = distances[i][j + 1] + 1;
 301             let deletion_cost = distances[i + 1][j] + 1;
 302             let transposition_cost = distances[k][l] + (i - k - 1) + 1 +
 303                                      (j - l - 1);
 304
 305             distances[i + 1][j + 1] = min(substitution_cost,
 306                                       min(insertion_cost,
 307                                       min(deletion_cost,
 308                                           transposition_cost)));
 309         }
 310
 311         chars.insert(a_chars[i - 1], i);
 312     }
 313
 314     distances[a_len + 1][b_len + 1]
 315 }
 316
 317 /// Calculates a normalized score of the Damerau–Levenshtein algorithm between
 318 /// 0.0 and 1.0 (inclusive), where 1.0 means the strings are the same.
 319 ///
 320 /// ```
 321 /// use strsim::normalized_damerau_levenshtein;
 322 ///
 323 /// assert!((normalized_damerau_levenshtein("levenshtein", "löwenbräu") - 0.27272).abs() < 0.00001);
 324 /// assert!((normalized_damerau_levenshtein("", "") - 1.0).abs() < 0.00001);
 325 /// assert!(normalized_damerau_levenshtein("", "flower").abs() < 0.00001);
 326 /// assert!(normalized_damerau_levenshtein("tree", "").abs() < 0.00001);
 327 /// assert!((normalized_damerau_levenshtein("sunglasses", "sunglasses") - 1.0).abs() < 0.00001);
 328 /// ```
 329 pub fn normalized_damerau_levenshtein(a: &str, b: &str) -> f64 {
 330     if a.is_empty() && b.is_empty() {
 331         return 1.0;
 332     }
 333     1.0 - (damerau_levenshtein(a, b) as f64) / (a.chars().count().max(b.chars().count()) as f64)
 334 }
 335
 336 #[cfg(test)]
 337 mod tests {
 338     use super::*;
 339
 340     #[test]
 341     fn hamming_empty() {
 342         match hamming("", "") {
 343             Ok(distance) => { assert_eq!(0, distance); },
 344             Err(why) => { panic!("{:?}", why); }
 345         }
 346     }
 347
 348     #[test]
 349     fn hamming_same() {
 350         match hamming("hamming", "hamming") {
 351             Ok(distance) => { assert_eq!(0, distance); },
 352             Err(why) => { panic!("{:?}", why); }
 353         }
 354     }
 355
 356     #[test]
 357     fn hamming_diff() {
 358         match hamming("hamming", "hammers") {
 359             Ok(distance) => { assert_eq!(3, distance); },
 360             Err(why) => { panic!("{:?}", why); }
 361         }
 362     }
 363
 364     #[test]
 365     fn hamming_diff_multibyte() {
 366         match hamming("hamming", "h香mmüng") {
 367             Ok(distance) => { assert_eq!(2, distance); },
 368             Err(why) => { panic!("{:?}", why); }
 369         }
 370     }
 371
 372     #[test]
 373     fn hamming_unequal_length() {
 374         match hamming("ham", "hamming") {
 375             Ok(_) => { panic!(); },
 376             Err(why) => { assert_eq!(why, StrSimError::DifferentLengthArgs); }
 377         }
 378     }
 379
 380     #[test]
 381     fn hamming_names() {
 382         match hamming("Friedrich Nietzs", "Jean-Paul Sartre") {
 383             Ok(distance) => { assert_eq!(14, distance); },
 384             Err(why) => { panic!("{:?}", why); }
 385         }
 386     }
 387
 388     #[test]
 389     fn jaro_both_empty() {
 390        assert_eq!(1.0, jaro("", ""));
 391     }
 392
 393     #[test]
 394     fn jaro_first_empty() {
 395         assert_eq!(0.0, jaro("", "jaro"));
 396     }
 397
 398     #[test]
 399     fn jaro_second_empty() {
 400         assert_eq!(0.0, jaro("distance", ""));
 401     }
 402
 403     #[test]
 404     fn jaro_same() {
 405         assert_eq!(1.0, jaro("jaro", "jaro"));
 406     }
 407
 408     #[test]
 409     fn jaro_multibyte() {
 410         assert!((0.818 - jaro("testabctest", "testöঙ香test")) < 0.001);
 411         assert!((0.818 - jaro("testöঙ香test", "testabctest")) < 0.001);
 412     }
 413
 414     #[test]
 415     fn jaro_diff_short() {
 416         assert!((0.767 - jaro("dixon", "dicksonx")).abs() < 0.001);
 417     }
 418
 419     #[test]
 420     fn jaro_diff_one_character() {
 421         assert_eq!(0.0, jaro("a", "b"));
 422     }
 423
 424     #[test]
 425     fn jaro_diff_one_and_two() {
 426         assert!((0.83 - jaro("a", "ab")).abs() < 0.01);
 427     }
 428
 429     #[test]
 430     fn jaro_diff_two_and_one() {
 431         assert!((0.83 - jaro("ab", "a")).abs() < 0.01);
 432     }
 433
 434     #[test]
 435     fn jaro_diff_no_transposition() {
 436         assert!((0.822 - jaro("dwayne", "duane")).abs() < 0.001);
 437     }
 438
 439     #[test]
 440     fn jaro_diff_with_transposition() {
 441         assert!((0.944 - jaro("martha", "marhta")).abs() < 0.001);
 442     }
 443
 444     #[test]
 445     fn jaro_names() {
 446         assert!((0.392 - jaro("Friedrich Nietzsche",
 447                               "Jean-Paul Sartre")).abs() < 0.001);
 448     }
 449
 450     #[test]
 451     fn jaro_winkler_both_empty() {
 452         assert_eq!(1.0, jaro_winkler("", ""));
 453     }
 454
 455     #[test]
 456     fn jaro_winkler_first_empty() {
 457         assert_eq!(0.0, jaro_winkler("", "jaro-winkler"));
 458     }
 459
 460     #[test]
 461     fn jaro_winkler_second_empty() {
 462         assert_eq!(0.0, jaro_winkler("distance", ""));
 463     }
 464
 465     #[test]
 466     fn jaro_winkler_same() {
 467         assert_eq!(1.0, jaro_winkler("Jaro-Winkler", "Jaro-Winkler"));
 468     }
 469
 470     #[test]
 471     fn jaro_winkler_multibyte() {
 472         assert!((0.89 - jaro_winkler("testabctest", "testöঙ香test")).abs() <
 473                 0.001);
 474         assert!((0.89 - jaro_winkler("testöঙ香test", "testabctest")).abs() <
 475                 0.001);
 476     }
 477
 478     #[test]
 479     fn jaro_winkler_diff_short() {
 480         assert!((0.813 - jaro_winkler("dixon", "dicksonx")).abs() < 0.001);
 481         assert!((0.813 - jaro_winkler("dicksonx", "dixon")).abs() < 0.001);
 482     }
 483
 484     #[test]
 485     fn jaro_winkler_diff_one_character() {
 486         assert_eq!(0.0, jaro_winkler("a", "b"));
 487     }
 488
 489     #[test]
 490     fn jaro_winkler_diff_no_transposition() {
 491         assert!((0.840 - jaro_winkler("dwayne", "duane")).abs() < 0.001);
 492     }
 493
 494     #[test]
 495     fn jaro_winkler_diff_with_transposition() {
 496         assert!((0.961 - jaro_winkler("martha", "marhta")).abs() < 0.001);
 497     }
 498
 499     #[test]
 500     fn jaro_winkler_names() {
 501         assert!((0.562 - jaro_winkler("Friedrich Nietzsche",
 502                                       "Fran-Paul Sartre")).abs() < 0.001);
 503     }
 504
 505     #[test]
 506     fn jaro_winkler_long_prefix() {
 507         assert!((0.911 - jaro_winkler("cheeseburger", "cheese fries")).abs() <
 508                 0.001);
 509     }
 510
 511     #[test]
 512     fn jaro_winkler_more_names() {
 513         assert!((0.868 - jaro_winkler("Thorkel", "Thorgier")).abs() < 0.001);
 514     }
 515
 516     #[test]
 517     fn jaro_winkler_length_of_one() {
 518         assert!((0.738 - jaro_winkler("Dinsdale", "D")).abs() < 0.001);
 519     }
 520
 521     #[test]
 522     fn jaro_winkler_very_long_prefix() {
 523         assert!((1.0 - jaro_winkler("thequickbrownfoxjumpedoverx",
 524                                     "thequickbrownfoxjumpedovery")).abs() <
 525                 0.001);
 526     }
 527
 528     #[test]
 529     fn levenshtein_empty() {
 530         assert_eq!(0, levenshtein("", ""));
 531     }
 532
 533     #[test]
 534     fn levenshtein_same() {
 535         assert_eq!(0, levenshtein("levenshtein", "levenshtein"));
 536     }
 537
 538     #[test]
 539     fn levenshtein_diff_short() {
 540         assert_eq!(3, levenshtein("kitten", "sitting"));
 541     }
 542
 543     #[test]
 544     fn levenshtein_diff_with_space() {
 545         assert_eq!(5, levenshtein("hello, world", "bye, world"));
 546     }
 547
 548     #[test]
 549     fn levenshtein_diff_multibyte() {
 550         assert_eq!(3, levenshtein("öঙ香", "abc"));
 551         assert_eq!(3, levenshtein("abc", "öঙ香"));
 552     }
 553
 554     #[test]
 555     fn levenshtein_diff_longer() {
 556         let a = "The quick brown fox jumped over the angry dog.";
 557         let b = "Lorem ipsum dolor sit amet, dicta latine an eam.";
 558         assert_eq!(37, levenshtein(a, b));
 559     }
 560
 561     #[test]
 562     fn levenshtein_first_empty() {
 563         assert_eq!(7, levenshtein("", "sitting"));
 564     }
 565
 566     #[test]
 567     fn levenshtein_second_empty() {
 568         assert_eq!(6, levenshtein("kitten", ""));
 569     }
 570
 571     #[test]
 572     fn normalized_levenshtein_diff_short() {
 573         assert!((normalized_levenshtein("kitten", "sitting") - 0.57142).abs() < 0.00001);
 574     }
 575
 576     #[test]
 577     fn normalized_levenshtein_for_empty_strings() {
 578         assert!((normalized_levenshtein("", "") - 1.0).abs() < 0.00001);
 579     }
 580
 581     #[test]
 582     fn normalized_levenshtein_first_empty() {
 583         assert!(normalized_levenshtein("", "second").abs() < 0.00001);
 584     }
 585
 586     #[test]
 587     fn normalized_levenshtein_second_empty() {
 588         assert!(normalized_levenshtein("first", "").abs() < 0.00001);
 589     }
 590
 591     #[test]
 592     fn normalized_levenshtein_identical_strings() {
 593         assert!((normalized_levenshtein("identical", "identical") - 1.0).abs() < 0.00001);
 594     }
 595
 596     #[test]
 597     fn osa_distance_empty() {
 598         assert_eq!(0, osa_distance("", ""));
 599     }
 600
 601     #[test]
 602     fn osa_distance_same() {
 603         assert_eq!(0, osa_distance("damerau", "damerau"));
 604     }
 605
 606     #[test]
 607     fn osa_distance_first_empty() {
 608         assert_eq!(7, osa_distance("", "damerau"));
 609     }
 610
 611     #[test]
 612     fn osa_distance_second_empty() {
 613         assert_eq!(7, osa_distance("damerau", ""));
 614     }
 615
 616     #[test]
 617     fn osa_distance_diff() {
 618         assert_eq!(3, osa_distance("ca", "abc"));
 619     }
 620
 621     #[test]
 622     fn osa_distance_diff_short() {
 623         assert_eq!(3, osa_distance("damerau", "aderua"));
 624     }
 625
 626     #[test]
 627     fn osa_distance_diff_reversed() {
 628         assert_eq!(3, osa_distance("aderua", "damerau"));
 629     }
 630
 631     #[test]
 632     fn osa_distance_diff_multibyte() {
 633         assert_eq!(3, osa_distance("öঙ香", "abc"));
 634         assert_eq!(3, osa_distance("abc", "öঙ香"));
 635     }
 636
 637     #[test]
 638     fn osa_distance_diff_unequal_length() {
 639         assert_eq!(6, osa_distance("damerau", "aderuaxyz"));
 640     }
 641
 642     #[test]
 643     fn osa_distance_diff_unequal_length_reversed() {
 644         assert_eq!(6, osa_distance("aderuaxyz", "damerau"));
 645     }
 646
 647     #[test]
 648     fn osa_distance_diff_comedians() {
 649         assert_eq!(5, osa_distance("Stewart", "Colbert"));
 650     }
 651
 652     #[test]
 653     fn osa_distance_many_transpositions() {
 654         assert_eq!(4, osa_distance("abcdefghijkl", "bacedfgihjlk"));
 655     }
 656
 657     #[test]
 658     fn osa_distance_diff_longer() {
 659         let a = "The quick brown fox jumped over the angry dog.";
 660         let b = "Lehem ipsum dolor sit amet, dicta latine an eam.";
 661         assert_eq!(36, osa_distance(a, b));
 662     }
 663
 664     #[test]
 665     fn osa_distance_beginning_transposition() {
 666         assert_eq!(1, osa_distance("foobar", "ofobar"));
 667     }
 668
 669     #[test]
 670     fn osa_distance_end_transposition() {
 671         assert_eq!(1, osa_distance("specter", "spectre"));
 672     }
 673
 674     #[test]
 675     fn osa_distance_restricted_edit() {
 676         assert_eq!(4, osa_distance("a cat", "an abct"));
 677     }
 678
 679     #[test]
 680     fn damerau_levenshtein_empty() {
 681         assert_eq!(0, damerau_levenshtein("", ""));
 682     }
 683
 684     #[test]
 685     fn damerau_levenshtein_same() {
 686         assert_eq!(0, damerau_levenshtein("damerau", "damerau"));
 687     }
 688
 689     #[test]
 690     fn damerau_levenshtein_first_empty() {
 691         assert_eq!(7, damerau_levenshtein("", "damerau"));
 692     }
 693
 694     #[test]
 695     fn damerau_levenshtein_second_empty() {
 696         assert_eq!(7, damerau_levenshtein("damerau", ""));
 697     }
 698
 699     #[test]
 700     fn damerau_levenshtein_diff() {
 701         assert_eq!(2, damerau_levenshtein("ca", "abc"));
 702     }
 703
 704     #[test]
 705     fn damerau_levenshtein_diff_short() {
 706         assert_eq!(3, damerau_levenshtein("damerau", "aderua"));
 707     }
 708
 709     #[test]
 710     fn damerau_levenshtein_diff_reversed() {
 711         assert_eq!(3, damerau_levenshtein("aderua", "damerau"));
 712     }
 713
 714     #[test]
 715     fn damerau_levenshtein_diff_multibyte() {
 716         assert_eq!(3, damerau_levenshtein("öঙ香", "abc"));
 717         assert_eq!(3, damerau_levenshtein("abc", "öঙ香"));
 718     }
 719
 720     #[test]
 721     fn damerau_levenshtein_diff_unequal_length() {
 722         assert_eq!(6, damerau_levenshtein("damerau", "aderuaxyz"));
 723     }
 724
 725     #[test]
 726     fn damerau_levenshtein_diff_unequal_length_reversed() {
 727         assert_eq!(6, damerau_levenshtein("aderuaxyz", "damerau"));
 728     }
 729
 730     #[test]
 731     fn damerau_levenshtein_diff_comedians() {
 732         assert_eq!(5, damerau_levenshtein("Stewart", "Colbert"));
 733     }
 734
 735     #[test]
 736     fn damerau_levenshtein_many_transpositions() {
 737         assert_eq!(4, damerau_levenshtein("abcdefghijkl", "bacedfgihjlk"));
 738     }
 739
 740     #[test]
 741     fn damerau_levenshtein_diff_longer() {
 742         let a = "The quick brown fox jumped over the angry dog.";
 743         let b = "Lehem ipsum dolor sit amet, dicta latine an eam.";
 744         assert_eq!(36, damerau_levenshtein(a, b));
 745     }
 746
 747     #[test]
 748     fn damerau_levenshtein_beginning_transposition() {
 749         assert_eq!(1, damerau_levenshtein("foobar", "ofobar"));
 750     }
 751
 752     #[test]
 753     fn damerau_levenshtein_end_transposition() {
 754         assert_eq!(1, damerau_levenshtein("specter", "spectre"));
 755     }
 756
 757     #[test]
 758     fn damerau_levenshtein_unrestricted_edit() {
 759         assert_eq!(3, damerau_levenshtein("a cat", "an abct"));
 760     }
 761
 762     #[test]
 763     fn normalized_damerau_levenshtein_diff_short() {
 764         assert!((normalized_damerau_levenshtein("levenshtein", "löwenbräu") - 0.27272).abs() < 0.00001);
 765     }
 766
 767     #[test]
 768     fn normalized_damerau_levenshtein_for_empty_strings() {
 769         assert!((normalized_damerau_levenshtein("", "") - 1.0).abs() < 0.00001);
 770     }
 771
 772     #[test]
 773     fn normalized_damerau_levenshtein_first_empty() {
 774         assert!(normalized_damerau_levenshtein("", "flower").abs() < 0.00001);
 775     }
 776
 777     #[test]
 778     fn normalized_damerau_levenshtein_second_empty() {
 779         assert!(normalized_damerau_levenshtein("tree", "").abs() < 0.00001);
 780     }
 781
 782     #[test]
 783     fn normalized_damerau_levenshtein_identical_strings() {
 784         assert!((normalized_damerau_levenshtein("sunglasses", "sunglasses") - 1.0).abs() < 0.00001);
 785     }
 786 }