如何用n-grams（二元语法）查找列表中最相似字符串？

需求背景 #

给定以下字符串列表：

let original_arr = [
    "Bilbo Baggins",
    "Gandalf",
    "Thorin",
    "Balin",
    "Kili",
    "Fili",
    "John",
    "Frodo Baggins",
];

已通过代码生成每个字符串的二元语法向量，现在需要通过集合逻辑计算每个字符串的最相似匹配，输出指定格式的结果。

核心思路：Jaccard相似度 #

用Jaccard相似度作为衡量标准，公式为：
Jaccard(A,B) = |A ∩ B| / |A ∪ B|
其中A、B是两个字符串的二元语法集合。该指标能有效反映两个集合的重叠程度，适合短文本的相似性对比。

实现步骤 #

1. 将每个字符串的二元语法向量转换为HashSet，便于快速计算交集和并集。
2. 遍历每个字符串，与列表中其他所有字符串计算Jaccard相似度。
3. 排除自身匹配，筛选出相似度最高的字符串；若最高相似度为0，则返回None。

完整Rust代码实现 #

use std::collections::HashSet;

fn main() {
    let original_arr = [
        "Bilbo Baggins",
        "Gandalf",
        "Thorin",
        "Balin",
        "Kili",
        "Fili",
        "John",
        "Frodo Baggins",
    ];

    // 生成二元语法集合列表
    let ngram_sets: Vec<HashSet<[char; 2]>> = original_arr
        .iter()
        .map(|elem| {
            // 处理奇数长度的字符串，末尾补空格
            let processed = if elem.len() % 2 != 0 {
                format!("{elem} ")
            } else {
                elem.to_string()
            };
            // 生成二元语法并转为HashSet
            processed.chars().array_chunks().collect()
        })
        .collect();

    // 遍历每个字符串，计算最相似匹配
    for (idx, &current_str) in original_arr.iter().enumerate() {
        let current_set = &ngram_sets[idx];
        let mut max_similarity = 0.0;
        let mut most_similar: Option<&str> = None;

        for (other_idx, &other_str) in original_arr.iter().enumerate() {
            if idx == other_idx {
                continue; // 跳过自身
            }

            let other_set = &ngram_sets[other_idx];
            // 计算交集大小
            let intersection_size = current_set.intersection(other_set).count() as f64;
            // 计算并集大小：|A| + |B| - |A∩B|
            let union_size = (current_set.len() + other_set.len()) as f64 - intersection_size;

            if union_size == 0.0 {
                continue; // 避免除零，实际不会出现
            }

            let similarity = intersection_size / union_size;
            // 更新最大相似度和对应字符串
            if similarity > max_similarity {
                max_similarity = similarity;
                most_similar = Some(other_str);
            }
        }

        // 按照要求格式输出
        match most_similar {
            Some(s) if max_similarity > 0.0 => {
                println!("'{current_str}' most similar string: '{s}'");
            }
            _ => {
                println!("'{current_str}' most similar string: None");
            }
        }
    }
}

输出结果 #

'Bilbo Baggins' most similar string: 'Frodo Baggins'
'Gandalf' most similar string: None
'Thorin' most similar string: 'Balin'
'Balin' most similar string: 'Thorin'
'Kili' most similar string: 'Fili'
'Fili' most similar string: 'Kili'
'John' most similar string: None
'Frodo Baggins' most similar string: 'Bilbo Baggins'

内容的提问来源于stack exchange，提问作者olethras