bk_tree/
metrics.rs

1//! This is a collection of string metrics that are suitable for use with a
2//! BK-tree.
3
4#[cfg(feature = "serde")]
5extern crate serde;
6
7use Metric;
8
9extern crate triple_accel;
10use self::triple_accel::{levenshtein, levenshtein::levenshtein_simd_k};
11
12/// This calculates the Levenshtein distance between two strings.
13///
14/// The [distance metric itself][1] is calculated using the [Wagner-Fischer][2]
15/// dynamic programming algorithm.
16///
17/// # Examples
18///
19/// ```
20/// use bk_tree::Metric;
21/// use bk_tree::metrics::Levenshtein;
22///
23/// assert_eq!(Levenshtein.distance("bar", "baz"), 1);
24/// assert_eq!(Levenshtein.distance("kitten", "sitting"), 3);
25/// ```
26///
27/// [1]: https://en.wikipedia.org/wiki/Levenshtein_distance
28/// [2]: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
29#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
30pub struct Levenshtein;
31
32impl<K: AsRef<str> + ?Sized> Metric<K> for Levenshtein {
33    fn distance(&self, a: &K, b: &K) -> u32 {
34        let a_bytes = a.as_ref().as_bytes();
35        let b_bytes = b.as_ref().as_bytes();
36        levenshtein(a_bytes, b_bytes)
37    }
38
39    fn threshold_distance(&self, a: &K, b: &K, threshold: u32) -> Option<u32> {
40        let a_bytes = a.as_ref().as_bytes();
41        let b_bytes = b.as_ref().as_bytes();
42        levenshtein_simd_k(a_bytes, b_bytes, threshold)
43    }
44}
bk_tree/metrics.rs

bk_tree/
metrics.rs
