dam_lev implements the Damerau–Levenshtein diff algorithm. That is, it will take two sequences and determine the minimum number of transpositions, substitutions, insertions, and deletions needed to transform the first sequence into the second.

Usage

dam_lev::diff takes two vectors (of some type T which implements Clone + PartialEq) and returns a vector of dam_lev::Mutation objects. This is an enum type with four variants corresponding to the four types of transformations. For example,

use dam_lev::Mutation;

let seq1 = String::from("abcdef");
let seq2 = String::from("bcedxy");
let diffs = dam_lev::diff(&seq1.chars().collect(), &seq2.chars().collect());
assert_eq!(diffs, vec![Mutation::Deletion(0), Mutation::Transposition(3), Mutation::Substitution(5, 4), Mutation::Insertion(6, 5)]);

We see that the sequence of transformations is

• Delete the item at index 0 ('a').
• Transpose the item at index 3 ('d') with its successor.
• Substitute the item at index 5 ('f') with the item from the second sequence at index 4 ('x').
• Insert at index 6 the item from the second sequence at index 5 ('y').

Note the index for the transposition. Even though, after the deletion, the 'd' is at index 2, it's at index 3 in the original version of the sequence. Likewise for the successive mutations.

Key function

If you want to customize how the items are compared, you can use diff_with_key:

let seq1 = vec![1, 2, 3];
let seq2 = vec![91, 92, 93];
let key = |num: &u32| num % 3;
let diffs = dam_lev::diff_with_key(&seq1, &seq2, key);
assert_eq!(diffs.len(), 0);

In this case, the items must only implement Clone and key must be of type FnMut(&T) -> U where U implements PartialEq.