Function analiticcl::distance::damerau_levenshtein

pub fn damerau_levenshtein(
    s: &[CharIndexType], 
    t: &[CharIndexType], 
    max_distance: CharIndexType
) -> Option<CharIndexType>

Calculates the Damerau-Levenshtein distance between two strings.

This implementation was adapted from the one in the distance crate by Marcus Brummer (Apache 2 License)

Damerau-Levenshtein distance

The Damerau-Levenshtein distance is the number of per-character changes (insertion, deletion, substitution & transposition) that are neccessary to convert one string into annother. The original Levenshtein distance does not take transposition into account. This implementation does fully support unicode strings.

Complexity

m := len(s) + 2 n := len(t) + 2

Time complexity: O(mn) Space complexity: O(mn + m)