寻求高效的句子相似度百分比算法及单句与字符串向量相似度计算方案

Hey there! Let's ditch that slow, naive character-by-character comparison and use smarter, faster approaches that actually capture meaningful text overlap—perfect for your two similarity needs.

First, let's call out why your original plan falls short:

原方案的局限性：逐字符比对只统计字符重合度，完全忽略语义、词序或局部文本模式，而且时间复杂度为 O(n*m)（n、m 为两个文本长度），对于长文本或批量计算效率极低。

核心高效算法推荐 #

Here are the top alternatives tailored for speed and accuracy:

• N-Gram 相似度（字符/词双级别）
  这是逐字符比对的升级：提取文本中连续的 n 个字符（字符级，适合短句子）或 n 个词（词级，适合长文本），计算两个文本的 n-gram 集合的Jaccard 系数（交集大小/并集大小），再转换成百分比。用哈希集合存储 n-gram 能把查找/比对效率拉到 O(1)，整体时间复杂度优化到 O(n + m)。
  比如，对句子 "hello world" 提取 3-gram，会得到 {"hel", "ell", "llo", "lo ", "o w", " wo", "wor", "orl", "rld"}，比对时直接用集合运算就能快速算出重合度。

• 归一化编辑距离（优化版 Levenshtein）
  编辑距离计算两个文本互相转换的最少操作数（插入、删除、替换），归一化后就能得到百分比：(1 - 编辑距离 / max(len(s1), len(s2))) * 100。普通 Levenshtein 是 O(n*m)，但用滚动数组优化能把空间复杂度降到 O(min(n,m))，对于短文本足够快，而且比逐字符比对更贴合文本的实际差异。

• 词级 Jaccard/余弦相似度
  先把句子分词，转换成词集合（Jaccard）或词频向量（TF-IDF），再计算相似度。这个方法关注语义层面的词重合，适合长句子或段落。用哈希表统计词频，整体时间复杂度 O(n + m)，批量计算时效率极高。

适配你的两个需求实现 #

1. 单个句子与字符串向量的批量相似度计算 #

Pick any of the above algorithms (n-gram or word-level Jaccard works best here) and follow these steps:

• 预处理目标句子：生成 n-gram 集合/词集合，用哈希表存储
• 遍历字符串向量中的每个句子，重复预处理
• 批量计算每个句子与目标句子的相似度，还可以用多线程并行处理向量中的句子进一步提速
• 若向量规模极大，用近似最近邻算法（比如 Annoy）快速筛选最相似的句子，避免逐个计算

2. 两句相似度百分比输出 #

Here's a practical, fast implementation using character 3-gram (adjust n based on your text length):

def calculate_similarity_percent(s1: str, s2: str, n: int = 3) -> float:
    # 统一小写，忽略大小写差异
    s1_lower = s1.lower().strip()
    s2_lower = s2.lower().strip()
    
    def generate_ngrams(text: str) -> set:
        ngrams = set()
        text_len = len(text)
        if text_len < n:
            return {text}
        for i in range(text_len - n + 1):
            ngrams.add(text[i:i+n])
        return ngrams
    
    ngrams1 = generate_ngrams(s1_lower)
    ngrams2 = generate_ngrams(s2_lower)
    
    # 处理空文本情况
    if not ngrams1 and not ngrams2:
        return 100.0
    if not ngrams1 or not ngrams2:
        return 0.0
    
    intersection = len(ngrams1 & ngrams2)
    union = len(ngrams1 | ngrams2)
    return round((intersection / union) * 100, 2)

This implementation uses set operations (fast hash lookups) and handles edge cases like short or empty text.

内容的提问来源于stack exchange，提问作者Jose Luis Montalvo Ferreiro