Calculate edit distance (or Levenshtein edit distance) between two strings.
The library is inspired by algorithms of Ukkonen and Landau, Myers, and Schmidt. The running time of algorithm is $O(d*min(n,m))$ (where $d$ is the edit distance between strings and $n$ and $m$ are lengths of strings).
The initial goal of this library is to create a fast implementation for the bounded version of the edit distance problem ( given a threshold, $k$ return the edit distance $d$ if it is at most $k$ or return that it is more than $k$). Typically, the classic edit distance algorithm is slow in such cases.
Add to Cargo.toml
toml
[dependecies]
editdistancek = "0.1.0"
rust
edit_distance("kitten".as_bytes(), "sitting".as_bytes()); // => 3
edit_distance_k("kitten".as_bytes(), "sitting".as_bytes(), 3); // => Some(3)
edit_distance_k("kitten".as_bytes(), "sitting".as_bytes(), 2); // => None
MIT License