INNER CODE UNIT · Rust

levenshtein

David-OConnor/plascad · src/alignment.rs:76

fn levenshtein(alpha: &[u8], beta: &[u8]) -> u32 {
    let mut prev: Vec<u32> = (0..=beta.len() as u32).collect();
    let mut cur = vec![0; beta.len() + 1];

    for (i, a) in alpha.iter().enumerate() {
        cur[0] = i as u32 + 1;

        for (j, b) in beta.iter().enumerate() {
            let substitution = prev[j] + (a != b) as u32;
            cur[j + 1] = substitution.min(prev[j + 1] + 1).min(cur[j] + 1);
        }

        std::mem::swap(&mut prev, &mut cur);
    }

    prev[beta.len()]
}

View source record →