Repository: ashvardanian/StringZilla (language: rust)

Issue:
Expose Levenshtein distance and NW to Rust
Unlike C, C++, Swift, and Python, the Rust interface lacks any exposure to `sz_edit_distance` and `sz_alignment_score`, which might be of interest to many users.


Discussion / hints:
I will pick this up. Are these the correct definitions of the above mentioned functions?
- https://github.com/ashvardanian/StringZilla/blob/main/c/lib.c#L258
- https://github.com/ashvardanian/StringZilla/blob/main/c/lib.c#L265
Yes, those are!

Fix patch:
diff --git a/Cargo.lock b/Cargo.lock
index 64ea4388..e97fba7a 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -19,7 +19,7 @@ checksum = "13e3bf6590cbc649f4d1a3eefc9d5d6eb746f5200ffb04e5e142700b8faa56e7"
 
 [[package]]
 name = "stringzilla"
-version = "2.0.4"
+version = "3.0.0"
 dependencies = [
  "cc",
 ]
diff --git a/rust/lib.rs b/rust/lib.rs
index a8cc48ee..fff99606 100644
--- a/rust/lib.rs
+++ b/rust/lib.rs
@@ -5,64 +5,98 @@ use core::ffi::c_void;
 // Import the functions from the StringZilla C library.
 extern "C" {
     fn sz_find(
-        haystack: *mut c_void,
+        haystack: *const c_void,
         haystack_length: usize,
         needle: *const c_void,
         needle_length: usize,
-    ) -> *mut c_void;
+    ) -> *const c_void;
 
     fn sz_rfind(
-        haystack: *mut c_void,
+        haystack: *const c_void,
         haystack_length: usize,
         needle: *const c_void,
         needle_length: usize,
-    ) -> *mut c_void;
+    ) -> *const c_void;
 
     fn sz_find_char_from(
-        haystack: *mut c_void,
+        haystack: *const c_void,
         haystack_length: usize,
         needle: *const c_void,
         needle_length: usize,
-    ) -> *mut c_void;
+    ) -> *const c_void;
 
     fn sz_rfind_char_from(
-        haystack: *mut c_void,
+        haystack: *const c_void,
         haystack_length: usize,
         needle: *const c_void,
         needle_length: usize,
-    ) -> *mut c_void;
+    ) -> *const c_void;
 
     fn sz_find_char_not_from(
-        haystack: *mut c_void,
+        haystack: *const c_void,
         haystack_length: usize,
         needle: *const c_void,
         needle_length: usize,
-    ) -> *mut c_void;
+    ) -> *const c_void;
 
     fn sz_rfind_char_not_from(
-        haystack: *mut c_void,
+        haystack: *const c_void,
         haystack_length: usize,
         needle: *const c_void,
         needle_length: usize,
-    ) -> *mut c_void;
+    ) -> *const c_void;
+
+    fn sz_edit_distance(
+        haystack1: *const c_void,
+        haystack1_length: usize,
+        haystack2: *const c_void,
+        haystack2_length: usize,
+        bound: usize,
+        allocator: *const c_void,
+    ) -> usize;
+
+    fn sz_alignment_score(
+        haystack1: *const c_void,
+        haystack1_length: usize,
+        haystack2: *const c_void,
+        haystack2_length: usize,
+        matrix: *const c_void,
+        gap: i8,
+        allocator: *const c_void,
+    ) -> isize;
 }
 
+/// The [StringZilla] trait provides a collection of string searching and manipulation functionalities.
 pub trait StringZilla<N>
 where
     N: AsRef<[u8]>,
 {
-    /// Generic function to find the first occurrence of a substring or a subarray.
+    /// Locates first matching substring. Equivalent to `memmem(haystack, h_length, needle, n_length)` in LibC. Similar
+    /// to `strstr(haystack, needle)` in LibC, but requires known length.
     fn sz_find(&self, needle: N) -> Option<usize>;
-    /// Generic function to find the last occurrence of a substring or a subarray.
+
+    /// Locates the last matching substring.
     fn sz_rfind(&self, needle: N) -> Option<usize>;
-    /// Generic function to find the first occurrence of a character/element from the second argument.
+
+    /// Finds the first character in the haystack, that is present in the needle.
     fn sz_find_char_from(&self, needles: N) -> Option<usize>;
-    /// Generic function to find the last occurrence of a character/element from the second argument.
+
+    /// Finds the last character in the haystack, that is present in the needle.
     fn sz_rfind_char_from(&self, needles: N) -> Option<usize>;
-    /// Generic function to find the first occurrence of a character/element from the second argument.
+
+    /// Finds the first character in the haystack, that is __not__ present in the needle.
     fn sz_find_char_not_from(&self, needles: N) -> Option<usize>;
-    /// Generic function to find the last occurrence of a character/element from the second argument.
+
+    /// Finds the last character in the haystack, that is __not__ present in the needle.
     fn sz_rfind_char_not_from(&self, needles: N) -> Option<usize>;
+
+    /// Computes the Levenshtein edit-distance between two strings using the Wagner-Fisher algorithm.
+    /// Similar to the Needleman-Wunsch alignment algorithm. Often used in fuzzy string matching.
+    fn sz_edit_distance(&self, needle: N) -> usize;
+
+    /// Computes Needleman–Wunsch alignment score for two strings. Often used in bioinformatics and cheminformatics.
+    /// Similar to the Levenshtein edit-distance, parameterized for gap and substitution penalties.
+    fn sz_alignment_score(&self, needle: N, matrix: [[i8; 256]; 256], gap: i8) -> isize;
 }
 
 impl<T, N> StringZilla<N> for T
@@ -73,9 +107,9 @@ where
     fn sz_find(&self, needle: N) -> Option<usize> {
         let haystack_ref = self.as_ref();
         let needle_ref = needle.as_ref();
-        let haystack_pointer = haystack_ref.as_ptr() as *mut c_void;
+        let haystack_pointer = haystack_ref.as_ptr() as _;
         let haystack_length = haystack_ref.len();
-        let needle_pointer = needle_ref.as_ptr() as *const c_void;
+        let needle_pointer = needle_ref.as_ptr() as _;
         let needle_length = needle_ref.len();
         let result = unsafe {
             sz_find(
@@ -96,9 +130,9 @@ where
     fn sz_rfind(&self, needle: N) -> Option<usize> {
         let haystack_ref = self.as_ref();
         let needle_ref = needle.as_ref();
-        let haystack_pointer = haystack_ref.as_ptr() as *mut c_void;
+        let haystack_pointer = haystack_ref.as_ptr() as _;
         let haystack_length = haystack_ref.len();
-        let needle_pointer = needle_ref.as_ptr() as *const c_void;
+        let needle_pointer = needle_ref.as_ptr() as _;
         let needle_length = needle_ref.len();
         let result = unsafe {
             sz_rfind(
@@ -119,9 +153,9 @@ where
     fn sz_find_char_from(&self, needles: N) -> Option<usize> {
         let haystack_ref = self.as_ref();
         let needles_ref = needles.as_ref();
-        let haystack_pointer = haystack_ref.as_ptr() as *mut c_void;
+        let haystack_pointer = haystack_ref.as_ptr() as _;
         let haystack_length = haystack_ref.len();
-        let needles_pointer = needles_ref.as_ptr() as *const c_void;
+        let needles_pointer = needles_ref.as_ptr() as _;
         let needles_length = needles_ref.len();
         let result = unsafe {
             sz_find_char_from(
@@ -141,9 +175,9 @@ where
     fn sz_rfind_char_from(&self, needles: N) -> Option<usize> {
         let haystack_ref = self.as_ref();
         let needles_ref = needles.as_ref();
-        let haystack_pointer = haystack_ref.as_ptr() as *mut c_void;
+        let haystack_pointer = haystack_ref.as_ptr() as _;
         let haystack_length = haystack_ref.len();
-        let needles_pointer = needles_ref.as_ptr() as *const c_void;
+        let needles_pointer = needles_ref.as_ptr() as _;
         let needles_length = needles_ref.len();
         let result = unsafe {
             sz_rfind_char_from(
@@ -163,9 +197,9 @@ where
     fn sz_find_char_not_from(&self, needles: N) -> Option<usize> {
         let haystack_ref = self.as_ref();
         let needles_ref = needles.as_ref();
-        let haystack_pointer = haystack_ref.as_ptr() as *mut c_void;
+        let haystack_pointer = haystack_ref.as_ptr() as _;
         let haystack_length = haystack_ref.len();
-        let needles_pointer = needles_ref.as_ptr() as *const c_void;
+        let needles_pointer = needles_ref.as_ptr() as _;
         let needles_length = needles_ref.len();
         let result = unsafe {
             sz_find_char_not_from(
@@ -185,9 +219,9 @@ where
     fn sz_rfind_char_not_from(&self, needles: N) -> Option<usize> {
         let haystack_ref = self.as_ref();
         let needles_ref = needles.as_ref();
-        let haystack_pointer = haystack_ref.as_ptr() as *mut c_void;
+        let haystack_pointer = haystack_ref.as_ptr() as _;
         let haystack_length = haystack_ref.len();
-        let needles_pointer = needles_ref.as_ptr() as *const c_void;
+        let needles_pointer = needles_ref.as_ptr() as _;
         let needles_length = needles_ref.len();
         let result = unsafe {
             sz_rfind_char_not_from(
@@ -203,6 +237,49 @@ where
             Some(unsafe { result.offset_from(haystack_pointer) } as usize)
         }
     }
+
+    fn sz_edit_distance(&self, needle: N) -> usize {
+        let haystack_ref = self.as_ref();
+        let needle_ref = needle.as_ref();
+        let haystack_length = haystack_ref.len();
+        let needle_length = needle_ref.len();
+        let haystack_pointer = haystack_ref.as_ptr() as _;
+        let needle_pointer = needle_ref.as_ptr() as _;
+        unsafe {
+            sz_edit_distance(
+                haystack_pointer,
+                haystack_length,
+                needle_pointer,
+                needle_length,
+                // Upper bound on the distance, that allows us to exit early. If zero is
+                // passed, the maximum possible distance will be equal to the length of
+                // the longer input.
+                0,
+                // Uses the default allocator
+                core::ptr::null(),
+            )
+        }
+    }
+
+    fn sz_alignment_score(&self, needle: N, matrix: [[i8; 256]; 256], gap: i8) -> isize {
+        let haystack_ref = self.as_ref();
+        let needle_ref = needle.as_ref();
+        let haystack_length = haystack_ref.len();
+        let needle_length = needle_ref.len();
+        let haystack_pointer = haystack_ref.as_ptr() as _;
+        let needle_pointer = needle_ref.as_ptr() as _;
+        unsafe {
+            sz_alignment_score(
+                haystack_pointer,
+                haystack_length,
+                needle_pointer,
+                needle_length,
+                matrix.as_ptr() as _,
+                gap,
+                core::ptr::null(),
+            )
+        }
+    }
 }
 
 #[cfg(test)]
@@ -211,6 +288,44 @@ mod tests {
 
     use crate::StringZilla;
 
+    fn unary_substitution_costs() -> [[i8; 256]; 256] {
+        let mut result = [[0; 256]; 256];
+
+        for i in 0..256 {
+            for j in 0..256 {
+                result[i][j] = if i == j { 0 } else { -1 };
+            }
+        }
+
+        result
+    }
+
+    #[test]
+    fn levenshtein() {
+        assert_eq!("hello".sz_edit_distance("hell"), 1);
+        assert_eq!("hello".sz_edit_distance("hell"), 1);
+        assert_eq!("abc".sz_edit_distance(""), 3);
+        assert_eq!("abc".sz_edit_distance("ac"), 1);
+        assert_eq!("abc".sz_edit_distance("a_bc"), 1);
+        assert_eq!("abc".sz_edit_distance("adc"), 1);
+        assert_eq!("ggbuzgjux{}l".sz_edit_distance("gbuzgjux{}l"), 1);
+        assert_eq!("abcdefgABCDEFG".sz_edit_distance("ABCDEFGabcdefg"), 14);
+        assert_eq!("fitting".sz_edit_distance("kitty"), 4);
+        assert_eq!("smitten".sz_edit_distance("mitten"), 1);
+    }
+
+    #[test]
+    fn needleman() {
+        let costs_vector = unary_substitution_costs();
+        assert_eq!("listen".sz_alignment_score("silent", costs_vector, -1), -4);
+        assert_eq!(
+            "abcdefgABCDEFG".sz_alignment_score("ABCDEFGabcdefg", costs_vector, -1),
+            -14
+        );
+        assert_eq!("hello".sz_alignment_score("hello", costs_vector, -1), 0);
+        assert_eq!("hello".sz_alignment_score("hell", costs_vector, -1), -1);
+    }
+
     #[test]
     fn basics() {
         let my_string: String = String::from("Hello, world!");


Test patch: