INNER CODE UNIT · Rust
hamming
David-OConnor/plascad · src/alignment.rs:70
fn hamming(alpha: &[u8], beta: &[u8]) -> u64 {
alpha.iter().zip(beta).filter(|(a, b)| a != b).count() as u64
}
/// The minimum number of substitutions, insertions, and deletions to turn one sequence into the
/// other.
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);
}