Python模糊字符串匹配双表索引时如何避免重复匹配并最大化匹配度

问题场景 #

在Python环境中合并两张数据表时，常遇到两表行键表述不一致的问题。通常可以通过jellyfish等字符串相似度计算库生成跨表键的候选匹配对及对应相似度分数，但朴素的逐行取最高相似度匹配逻辑，会出现同一个目标表键被多个源表键重复占用的问题。我们需要实现一套匹配逻辑，满足两个核心要求：

• 所有匹配结果中，目标表（table_2）的键唯一不重复
• 所有匹配对的相似度总和最高，即达到全局最优而非局部最优

问题复现 #

测试样例数据 #

table_1 = [['t1_key_1', ['t1_value_1']],
           ['t1_key_2', ['t1_value_2']],
           ['t1_key_n', ['t1_value_n']]]


table_2 = [['t2_key_1', 't2_value_1'],
           ['t2_key_2', 't2_value_2'],
           ['t2_key_n', 't2_value_n']] 

match_list = [['t1_key_1',
                    [['t2_key_1', 0.9],
                     ['t2_key_2', 0.9],
                     ['t2_key_n', 0.6]]],
              ['t1_key_2',
                   [['t2_key_1', 0.9],
                    ['t2_key_2', 0.8],
                    ['t2_key_n', 0.2]]],
              ['t1_key_n',
                   [['t2_key_1', 0.7],
                    ['t2_key_2', 0.9],
                    ['t2_key_n', 0.8]]]
            ]

错误实现与问题 #

逐行选取最高相似度的实现代码如下：

result = []
for row in match_list:
    row[1].sort(key=lambda x: x[1], reverse=True)
    result.append([row[0],row[1][0]])

print(result)

运行返回结果：

[['t1_key_1', ['t2_key_1', 0.9]],
 ['t1_key_2', ['t2_key_1', 0.9]], 
 ['t1_key_n', ['t2_key_2', 0.9]]]

上述结果中t2_key_1同时被匹配给t1_key_1和t1_key_2，出现重复匹配，不符合业务要求。

期望输出 #

在键唯一的前提下总相似度最高的匹配结果：

[['t1_key_1', ['t2_key_2', 0.9]],
 ['t1_key_2', ['t2_key_1', 0.9]], 
 ['t1_key_n', ['t2_key_n', 0.8]]]

解决方案 #

该问题本质是二分图最大权匹配问题：左侧节点为源表所有键，右侧节点为目标表所有键，边的权重为两个键的相似度，目标是选出一组无公共节点的边，使得边的权重总和最大。不需要暴力枚举所有合法组合（组合数随键数量增长呈阶乘级上升，性能极差），直接使用成熟的线性分配算法（匈牙利算法/ KM算法）即可高效求解。

实现代码 #

借助科学计算库内置的线性分配求解器实现，逻辑简单且性能优异：

from scipy.optimize import linear_sum_assignment
import numpy as np

# 提取源表、目标表所有键
t1_keys = [item[0] for item in match_list]
t2_keys = list({match_pair[0] for t1_item in match_list for match_pair in t1_item[1]})
t1_len, t2_len = len(t1_keys), len(t2_keys)

# 构建相似度矩阵，无候选匹配的位置默认填0
sim_matrix = np.zeros((t1_len, t2_len))
t2_idx_map = {key: idx for idx, key in enumerate(t2_keys)}
for row_idx, t1_item in enumerate(match_list):
    for t2_key, score in t1_item[1]:
        col_idx = t2_idx_map[t2_key]
        sim_matrix[row_idx][col_idx] = score

# 求解最大权匹配（求解器默认求最小权，传入负相似度矩阵转换为最大权问题）
row_indices, col_indices = linear_sum_assignment(-sim_matrix)

# 整理为要求的结果格式
optimal_result = []
for i, j in zip(row_indices, col_indices):
    optimal_result.append([
        t1_keys[i],
        [t2_keys[j], sim_matrix[i][j]]
    ])

print(optimal_result)

扩展说明 #

• 如果需要设置最低匹配阈值（比如相似度低于0.5的配对不允许成立），可以在构建相似度矩阵时，将低于阈值的分数设置为极小的负数（如-1e9），算法会自动避开这类低质量匹配。
• 当两张表的键数量不一致时，算法会自动选择总权重最高的匹配子集，不需要额外适配。

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