leven.rs

//! Leveshtein distance
//!
//! Leveshtein distance considers the 3 possibilities strings can differ -
//! addition, subtraction and deletion at each state of iteration and tries all
//! the cases to find the minimum distance.

use std::{collections::HashMap, convert::TryInto};

pub fn levenshtein(a: &str, b: &str) -> i32 {
    cached(a, b, &mut HashMap::new())
}

fn cached<'a>(a: &'a str, b: &'a str, c: &mut HashMap<(&'a str, &'a str), i32>) -> i32 {
    if let Some(k) = c.get(&(a, b)) {
        return *k;
    }

    let result = match (a.chars().next(), b.chars().next()) {
        (None, _) => b.len().try_into().unwrap(),
        (_, None) => a.len().try_into().unwrap(),
        (x, y) if x == y => cached(&a[1..], &b[1..], c),
        _ => 1 + min(cached(&a, &b[1..], c), cached(&a[1..], &b, c), cached(&a[1..], &b[1..], c)),
    };

    c.insert((a, b), result);
    result
}

fn min<T: Ord>(v1: T, v2: T, v3: T) -> T {
    v1.min(v2).min(v3)
}

#[cfg(test)]
fn naive(a: &str, b: &str) -> usize {
    match (a, b) {
        ("", _) => b.len(),
        (_, "") => a.len(),
        (_, _) if a.chars().next() == b.chars().next() => naive(&a[1..], &b[1..]),
        _ => 1 + min(naive(&a[1..], &b[1..]), naive(&a, &b[1..]), naive(&a[1..], &b)),
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    #[ignore]
    fn naive() {
        assert_eq!(8, super::naive("Carthorse", "Orchestra"));
    }

    #[test]
    fn cached() {
        assert_eq!(8, super::cached("Carthorse", "Orchestra", &mut HashMap::new()));

        // assert_eq!(
        //     8,
        //     super::cached("hello world", "a wonder world", &mut HashMap::new())
        // );
    }
}

#[cfg(test)]
mod bench {
    extern crate test;
    use std::collections::HashMap;
    use test::Bencher;

    #[bench]
    fn cached(b: &mut Bencher) {
        test::black_box(b.iter(|| super::cached("hello world", "world", &mut HashMap::new())));
    }

    #[bench]
    #[ignore]
    fn naive(b: &mut Bencher) {
        test::black_box(b.iter(|| super::naive("Carthorse", "Orchestra")));
    }
}