text-fx 0.4.0

/// Computes a normalized similarity score between two strings, with an optional lower bound for early exit.
///
/// This function implements a fast, bounded version of the "fstrcmp" similarity metric,
/// which is based on the Levenshtein (edit) distance. It returns a value in the range `[0.0, 1.0]`,
/// where `1.0` means the strings are identical and `0.0` means they are completely different.
///
/// If `lower_bound` is greater than zero, the function may return early with `0.0` if it can
/// determine that the similarity cannot reach the bound, using quick upper-bound heuristics.
///
/// # Arguments
///
/// * `a` - The first string to compare.
/// * `b` - The second string to compare.
/// * `lower_bound` - An optional lower bound for similarity; if the score cannot reach this value,
///   the function returns `0.0` early.
///
/// # Returns
///
/// A floating-point value between `0.0` and `1.0` representing the similarity.
///
/// # Examples
///
/// ```
/// use text_fx::similarity::fstrcmp_bounded;
///
/// let score = fstrcmp_bounded("kitten", "sitting", 0.5);
/// assert!(score > 0.57 && score < 0.58);
/// ```
pub fn fstrcmp_bounded(a: &str, b: &str, lower_bound: f64) -> f64 {
    let len_1 = a.len();
    let len_2 = b.len();
    let len_min = len_1.min(len_2);
    let len_max = len_1.max(len_2);
    let len_sum = len_1 + len_2;

    if len_min == 0 {
        return if len_max == 0 { 1.0 } else { 0.0 };
    }
    if lower_bound > 0.0 {
        /* Compute a quick upper bound.
          Each edit is an insertion or deletion of an element, hence modifies
          the length of the sequence by at most 1.
          Therefore, when starting from a sequence X and ending at a sequence Y,
          with N edits,  | yvec_length - xvec_length | <= N.  (Proof by
          induction over N.)
          So, at the end, we will have
            edit_count >= | xvec_length - yvec_length |.
          and hence
            result
              = (xvec_length + yvec_length - edit_count)
                / (xvec_length + yvec_length)
              <= (xvec_length + yvec_length - | yvec_length - xvec_length |)
                 / (xvec_length + yvec_length)
              = 2 * min (xvec_length, yvec_length) / (xvec_length + yvec_length).
        */
        let upper_bound = 2.0 * len_min as f64 / len_sum as f64;
        if upper_bound < lower_bound {
            return 0.0;
        }

        if len_sum >= 20 {
            let mut occ_diff: [isize; 256] = [0; 256];
            for &c in a.as_bytes() {
                occ_diff[c as usize] += 1;
            }
            for &c in b.as_bytes() {
                occ_diff[c as usize] -= 1;
            }
            let occ_diff_sum = occ_diff.map(|i| i.abs() as usize).iter().sum::<usize>();
            let upper_bound = 1.0 - occ_diff_sum as f64 / len_sum as f64;
            if upper_bound < lower_bound {
                return 0.0;
            }
        }
    }
    let dist = edit_distance_1d(a, b);
    1.0 - (dist as f64 / len_max as f64)
}

/// Compute the Levenshtein distance between two strings using optimized 1D dynamic programming.
///
/// This function returns the minimum number of single-character edits (insertions, deletions,
/// or substitutions) required to change one string into the other.
///
/// # Arguments
///
/// * `a` - The first string.
/// * `b` - The second string.
///
/// # Returns
///
/// The Levenshtein distance as an integer.
///
/// # Examples
///
/// ```
/// use text_fx::similarity::edit_distance_1d;
///
/// let dist = edit_distance_1d("kitten", "sitting");
/// assert_eq!(dist, 3);
/// ```
pub fn edit_distance_1d(a: &str, b: &str) -> usize {
    let (shorter, longer) = if a.len() < b.len() { (a, b) } else { (b, a) };
    let s: Vec<char> = shorter.chars().collect();
    let l: Vec<char> = longer.chars().collect();

    let len_s = s.len();
    let len_l = l.len();

    let mut prev = (0..=len_s).collect::<Vec<usize>>();
    let mut curr = vec![0; len_s + 1];

    for (i, lc) in l.iter().enumerate() {
        curr[0] = i + 1;
        for (j, sc) in s.iter().enumerate() {
            let cost = if sc == lc { 0 } else { 1 };
            curr[j + 1] = *[
                prev[j + 1] + 1, // deletion
                curr[j] + 1,     // insertion
                prev[j] + cost,  // substitution
            ]
            .iter()
            .min()
            .unwrap();
        }
        std::mem::swap(&mut prev, &mut curr);
    }

    prev[len_s]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fstrcmp() {
        let a = "kitten";
        let b = "sitting";
        let r = fstrcmp_bounded(a, b, 0.5);
        assert!(r > 0.57 && r < 0.58);
    }
}