Python大规模字符串列表文本相似度匹配：优化与精准性提升

需求描述 #

现有两个字符串列表：lemmas是标准词形（词典条目），forms是某语言（跨5个世纪、涵盖多方言）历时语料中的拼写变体，需要为每个form匹配最接近的lemma。

初始问题 #

基于textdistance库的嵌套循环代码在小测试集可正常运行，但处理约19万条的真实大列表时，运行时长超2小时且导致系统卡顿，被迫终止程序。初始代码如下：

import textdistance
from textdistance import hamming
from textdistance import cosine
from textdistance import jaro_winkler
import heapq

# 'lemmas' 是包含大量词典条目的列表
# 'forms' 是从数百篇文本中提取的大量单词拼写变体列表

distances = {}

processed_pairs = set() # 记录已处理的词对
for lemma in lemmas:
    if lemma is None:
        continue
    lemma_lower = lemma.lower()
    for form in forms:
        if form is None:
            continue        
        form_lower = form.lower()
        pair = (lemma_lower, form_lower) # 生成小写词对的元组
        if pair not in processed_pairs: # 检查词对是否已处理
            processed_pairs.add(pair)
            if textdistance.hamming.normalized_similarity(lemma_lower, form_lower) > 0.34 and textdistance.jaro_winkler(lemma_lower, form_lower) > 0.7 and textdistance.cosine(lemma_lower, form_lower) > 0.5:             
                dist = hamming.normalized_similarity(lemma_lower, form_lower)
                distances.setdefault(form_lower, []).append((dist, lemma_lower))

# 查找最匹配的词对
closest_pairs = {}
for form, dist_lemmas in distances.items():
    closest_pairs[form] = heapq.nsmallest(2, dist_lemmas)

with open(ROOT / 'potential_lemmas.txt', 'w') as f:
    for form, pairs in closest_pairs.items():
        for dist, lemma in pairs:
            f.write(f"{form} ➝  {lemma}: {dist}\n")

优化后情况 #

集成自定义距离计算方案与joblib并行化建议后，处理19万条列表的运行时长降至118分钟，优化后代码如下：

from itertools import zip_longest
from bisect import insort
from joblib import Parallel, delayed
import line_profiler

profile = line_profiler.LineProfiler()

lemmas = ['gran', 'vermell', 'groc', 'atens', 'Do', 'dOne', 'PUrpose', 'can', 'be', 'use', 'for', 'cannon', 'amuse', 'useful', 'user', 'become', 'downtown', 'develop', 'fulminate', 'deduce', 'de', 'bezant']

forms = ['preriarenos', 'Marinara', 'Grand', 'Gran', 'Grans', 'Grands', 'Grandeses', 'Grandullons', 'grand', 'grandissisimus', 'gran', 'grans', 'grands', 'grandeses', 'grandullons', 'grandullon', 'grandullones', 'uermell', 'uermells', 'vermell', 'vermells', 'vermella', 'vermelles', 'varmellíssimes', 'uarmellíssimes', 'uermellíssimes', 'uarnellíssimes', 'varmellíssima', 'uermella', 'uarmella', 'uarnella', 'varnella', 'uarnellas', 'varnellas', 'varmella', 'uermelles', 'grog', 'grogues', 'doNE', 'donE', 'doIng', 'purposeful', 'canonical', 'becareful', 'being', 'berate', 'best', 'bezant', 'full', 'fulmination', 'predict', 'downgrade', 'down', 'developing', 'deduct', 'deducing']

distances = {}

@delayed
def calc_distances(form, lemmas_low):
    form_distances = []
    for lemma in lemmas_low:
        char_matches = [c1 != c2 for c1, c2 in zip_longest(lemma, form)]
        dist = 1 - (sum(char_matches)/len(char_matches))
        if dist > 0.25:
            insort(form_distances, (dist, lemma))
    return (form, form_distances)

@profile
def profile_distance_calcs():
    lemmas_low = [lemma.lower() for lemma in lemmas]
    forms_low = [form.lower() for form in forms]
    results = Parallel(n_jobs=-1, prefer="threads")(calc_distances(form, lemmas_low) for form in forms_low)
    for form, form_distances in results:
        distances[form] = form_distances

    with open("potential_lemmas_hamming-like.txt", "w") as f:
        for form, form_distances in distances.items():
            for dist, lemma in reversed(form_distances[-2:]):
                f.write(f"{form} ➝  {lemma}: {dist}\n")

if __name__ == "__main__":
    profile_distance_calcs()
    profile.print_stats()

当前问题：匹配精准性不足 #

优化后的代码虽提升了效率，但出现匹配结果不符合语言形态逻辑的问题。例如中世纪加泰罗尼亚语的beatriç被匹配到tectriu、teatral，而非预期的beat类词形，现寻求适配历时语料拼写特征的NLP算法或改进方案。

针对性改进方案 #

1. 替换通用距离算法为语言专属编辑距离

通用的Hamming/Jaro-Winkler距离不考虑历时拼写的规则性变化（比如加泰罗尼亚语中b/v、ç/s的历史变体，或者词缀变化），建议：

• 使用加权编辑距离：为符合目标语言历时演变规则的字符替换（如b↔v、ç↔s、u↔v）设置更低的权重，随机替换设置高权重。
• 集成Levenshtein距离的语言定制版本，比如针对加泰罗尼亚语历史拼写的预定义替换矩阵。

2. 引入形态学过滤与前缀/后缀匹配

历时语料的拼写变体往往共享词干，可先做粗过滤减少无效匹配：

• 提取form的词干（可使用针对该语言的历史形态分析工具，或简单的前缀/后缀截断规则，比如去掉中世纪加泰罗尼亚语常见的词尾-ç、-s、-issimus），只在共享相同或相似词干的lemma中计算距离。
• 对长度差异过大的词对直接跳过（比如beatriç长度为6，与长度差超过2的lemma直接排除）。

3. 结合n-gram相似度过滤

使用**字符n-gram（如trigram）**计算相似度，比单个字符匹配更能捕捉词干的连续性，避免因个别字符差异导致的错误匹配。比如beatriç的trigram是bea、eat、atr、tri、riç，而beat类词形会共享前几个trigram，与tectriu的trigram无重叠，可快速排除无效候选。

4. 优化候选集生成策略

当前代码仍遍历所有lemma，效率和精准性都有问题，建议：

• 使用倒排索引：将lemma按字符n-gram建立索引，每个form生成n-gram后，只检索包含相同n-gram的lemma，大幅减少需要计算距离的候选数量。
• 用**BK树（Burkhard-Keller Tree）**存储lemma，可快速检索与目标form编辑距离在阈值内的候选，避免全量遍历。

5. 多特征融合排序

不要单一依赖距离值，可融合多个特征排序候选：

• 加权编辑距离
• n-gram相似度
• 词干匹配度
• 历史语料中该lemma与form的共现频率（如果有统计数据）
  通过线性加权或简单投票机制，选出最符合语言逻辑的匹配结果。

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