[−][src]Module spatium::edit_based::levenshtein

Levenshtein recursive implementation

Levenshtein distance

The Levenshtein distance between two strings In simple case number of operations for transforming one sequence to another. The edit operations allowed are:

  1. deletion: ABC -> BC, AC, AB
  2. insertion: ABC -> ABCD, EABC, AEBC..
  3. substitution: ABC -> ABE, ADC, FBC..

Examples

use spatium::edit_based::levenshtein;

// Get default algorithm for calc levenshtein distance.
let alg = levenshtein::Default::default();
let x = [1, 2, 3];
let y = [1, 2, 4];
let distance = alg.distance(&x, &y).unwrap();
assert_eq!(distance, 1.0);

// On &str.
let x = "Hello-МИР";
let y = "Hello-ПИР";
let xc = x.chars().collect::<Vec<char>>();
let yc = y.chars().collect::<Vec<char>>();
let distance = alg.distance(&xc, &yc).unwrap();
assert_eq!(distance, 1.0);

// With normaliztion (normalized distance = distance / x.len())
let alg = levenshtein::Default::default().normalize_result(true);
let x = [1, 2, 3];
let y = [1, 2, 4];
let distance = alg.distance(&x, &y).unwrap();
assert_eq!(distance, 1.0 / 3.0);

// Use obviously algorithm (for example recursive version)

let alg = levenshtein::Recursive::default();
let x = [1, 2, 3];
let y = [1, 2, 4];
let distance = alg.distance(&x, &y).unwrap();
assert_eq!(distance, 1.0);

References:

Some implementation

Re-exports

pub use recursive::Recursive;
pub use wagner_fisher::WagnerFisher;

Modules

recursive

Recursive algorithm

wagner_fisher

Wagner-Fisher algorithm

Type Definitions

Default

Default algorithm