zeph_memory/graph/
string_similarity.rs

1// SPDX-FileCopyrightText: 2026 Andrei G <bug-ops>
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Shared char-level Levenshtein edit distance and normalized similarity.
5//!
6//! Used by [`implicit_conflict`](crate::graph::implicit_conflict) (STALE/CUPMem predicate
7//! conflict detection) and [`belief_revision`](crate::graph::belief_revision) (Kumiho
8//! relation-domain check) to compare relation/predicate strings.
9//!
10//! Only [`levenshtein_distance`] is shared with `belief_revision`: its `relation_similarity`
11//! normalizes by **byte** length (not char length like [`normalized_similarity`] below) to
12//! preserve its original pre-existing behavior. Do not consolidate the two normalizations —
13//! they diverge for non-ASCII input and each caller's threshold was tuned against its own
14//! normalization.
15
16/// Char-level Levenshtein edit distance between two strings.
17///
18/// # Examples
19///
20/// ```
21/// use zeph_memory::graph::string_similarity::levenshtein_distance;
22///
23/// assert_eq!(levenshtein_distance("kitten", "sitting"), 3);
24/// assert_eq!(levenshtein_distance("", "abc"), 3);
25/// ```
26#[must_use]
27pub fn levenshtein_distance(a: &str, b: &str) -> usize {
28    let a_chars: Vec<char> = a.chars().collect();
29    let b_chars: Vec<char> = b.chars().collect();
30    let m = a_chars.len();
31    let n = b_chars.len();
32
33    let mut prev: Vec<usize> = (0..=n).collect();
34    let mut curr = vec![0usize; n + 1];
35
36    for i in 1..=m {
37        curr[0] = i;
38        for j in 1..=n {
39            let cost = usize::from(a_chars[i - 1] != b_chars[j - 1]);
40            curr[j] = (prev[j] + 1).min(curr[j - 1] + 1).min(prev[j - 1] + cost);
41        }
42        std::mem::swap(&mut prev, &mut curr);
43    }
44
45    prev[n]
46}
47
48/// Normalized Levenshtein similarity between two strings, in `[0.0, 1.0]`.
49///
50/// `1.0` means identical; the distance is normalized by the longer string's char count.
51/// Returns `1.0` if both strings are empty, `0.0` if only one is empty.
52///
53/// # Examples
54///
55/// ```
56/// use zeph_memory::graph::string_similarity::normalized_similarity;
57///
58/// assert!((normalized_similarity("uses", "uses") - 1.0).abs() < f64::EPSILON);
59/// assert!(normalized_similarity("uses", "xyz_unrelated_value") < 0.5);
60/// ```
61#[must_use]
62pub fn normalized_similarity(a: &str, b: &str) -> f64 {
63    if a == b {
64        return 1.0;
65    }
66    let len_a = a.chars().count();
67    let len_b = b.chars().count();
68    if len_a == 0 && len_b == 0 {
69        return 1.0;
70    }
71    if len_a == 0 || len_b == 0 {
72        return 0.0;
73    }
74    let dist = levenshtein_distance(a, b);
75    let max_len = len_a.max(len_b);
76    #[allow(clippy::cast_precision_loss)]
77    let result = 1.0 - (dist as f64 / max_len as f64);
78    result
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn levenshtein_distance_empty_strings() {
87        assert_eq!(levenshtein_distance("", ""), 0);
88    }
89
90    #[test]
91    fn levenshtein_distance_one_empty() {
92        assert_eq!(levenshtein_distance("abc", ""), 3);
93        assert_eq!(levenshtein_distance("", "xyz"), 3);
94    }
95
96    #[test]
97    fn levenshtein_distance_single_substitution() {
98        assert_eq!(levenshtein_distance("works_at", "work_at"), 1);
99    }
100
101    #[test]
102    fn normalized_similarity_identical() {
103        assert!((normalized_similarity("uses", "uses") - 1.0).abs() < f64::EPSILON);
104    }
105
106    #[test]
107    fn normalized_similarity_empty_both() {
108        assert!((normalized_similarity("", "") - 1.0).abs() < f64::EPSILON);
109    }
110
111    #[test]
112    fn normalized_similarity_empty_one() {
113        assert!((normalized_similarity("", "abc") - 0.0).abs() < f64::EPSILON);
114        assert!((normalized_similarity("abc", "") - 0.0).abs() < f64::EPSILON);
115    }
116
117    #[test]
118    fn normalized_similarity_completely_different() {
119        let sim = normalized_similarity("uses", "xyz_unrelated_value");
120        assert!(sim < 0.5, "expected low similarity, got {sim}");
121    }
122
123    #[test]
124    fn normalized_similarity_partial_overlap() {
125        // "works_at" vs "work_at" — 1 char diff out of 8 → ~0.875
126        let s = normalized_similarity("works_at", "work_at");
127        assert!(s > 0.5, "expected > 0.5, got {s}");
128    }
129}
zeph_memory/graph/string_similarity.rs

zeph_memory/graph/
string_similarity.rs
