## levenshtein-diff

Generic implementation of Levenshtein's algorithm that also allows you to generate the edits required to convert a source sequence to a target, and apply them to the source sequence to regenerate the target

### 8 releases

 0.2.4 Nov 15, 2022 Jun 27, 2022 Oct 7, 2021 Feb 7, 2021 Jan 1, 2021

#426 in Algorithms

Used in liff

21KB
277 lines

# Levenshtein Algorithm and a Bit More

The Levenshtein algorithm is a technique traditionally used to calculate the Levenshtein distance (i.e. edit distance) between two strings. However, nothing about the algorithm restricts it to strings. The algorithm works just as well to find the edit distance between any two sequences whose elements have an equivalence relation defined (i.e. for elements `a` and `b` in the sequence, you can tell if `a == b` and `a != b` are true or false).

This crate implements a generic Levenshtein's algorithm that works for any sequence of types that can be compared and cloned.

In addition to that, it let's you generate a sequence of `Edit` values that represent the transformations that, when applied to the source sequence, will convert it into the target sequence. A function that applies the edits to the source sequence and reconstructs the target sequence is also supplied.

## Features

• Three implementations of Levenshtein's algorithm: naive recursive, DP with tabulation and DP with memoization. Useful if you want to analyze and compare performance.
• Generate the sequence of edits that, when applied to the source sequence, will regenrate the target sequence. Useful when you want to sync with a remote copy of your sequence efficiently.
• Function to apply edits to a sequence in order to generate the target sequence.
• Generic: works on a sequence of any type that implements `PartialEq` (though the sequence will also have to implement `Clone` if you want to use the features related to generating and applying edits).

## Usage

In your `Cargo.toml`:

``````[dependencies]
levenshtein-diff = "0.2.4"
``````

``````    use levenshtein_diff as levenshtein;

// This example uses strings
let source = "SATURDAY";
let target = "SUNDAY";

let expected_leven = 3;

// dist: usize is the Levenshtein distance, and the mat is the distance matrix
let (dist, mat) = levenshtein::distance(source.as_bytes(), target.as_bytes());

assert_eq!(expected_leven, dist);

// Generate a sequence of edits (i.e. differences between source and target)
let edits = levenshtein::generate_edits(source.as_bytes(), target.as_bytes(), &mat)
.unwrap_or_else(|err| panic!(err));

// Apply edits to source to regenerate target. This results in a Vec
let generated_target_vec = levenshtein::apply_edits(source.as_bytes(), &edits);

// Convert the vector from above into a string
let generated_target = match std::str::from_utf8(&generated_target_vec) {
Ok(v) => v,
Err(e) => panic!("Invalid UTF-8 sequence: {}", e),
};

assert_eq!(target, generated_target);
``````