如何计算两个数字列表的带权Levenshtein距离？

方案一：自定义动态规划实现（最灵活可控） #

因为你需要以整个数字元素为单位计算编辑成本，而非拆分字符，自定义动态规划是最直接的解决方案。核心逻辑是构建DP表，每个状态dp[i][j]代表第一个列表前i个元素与第二个列表前j个元素的最小带权编辑距离，通过递推插入、删除、替换三种操作的成本完成计算。

实现步骤：

1. 定义成本映射：用字典存储单个数字的删除/插入成本，也可自定义特定数字对的替换成本。
2. 初始化DP表：第一行/列分别对应其中一个列表为空时的全插入/全删除累计成本。
3. 填充DP表：对每个位置计算三种操作的成本，取最小值更新当前状态。

示例代码：

def weighted_levenshtein(list1, list2, cost_map):
    # cost_map结构：{数字: 删除/插入成本, (数字a, 数字b): 替换成本}
    # 未定义的替换成本默认取两个数字成本的最大值
    n, m = len(list1), len(list2)
    dp = [[0]*(m+1) for _ in range(n+1)]
    
    # 初始化：删除list1所有元素的累计成本
    for i in range(1, n+1):
        dp[i][0] = dp[i-1][0] + cost_map.get(list1[i-1], 1)
    # 初始化：插入list2所有元素的累计成本
    for j in range(1, m+1):
        dp[0][j] = dp[0][j-1] + cost_map.get(list2[j-1], 1)
    
    # 填充DP表
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 处理替换成本
            if list1[i-1] == list2[j-1]:
                replace_cost = 0
            else:
                replace_cost = cost_map.get(
                    (list1[i-1], list2[j-1]),
                    max(cost_map.get(list1[i-1], 1), cost_map.get(list2[j-1], 1))
                )
            # 计算三种操作的总成本
            total_replace = dp[i-1][j-1] + replace_cost
            total_delete = dp[i-1][j] + cost_map.get(list1[i-1], 1)
            total_insert = dp[i][j-1] + cost_map.get(list2[j-1], 1)
            # 取最小值作为当前状态的结果
            dp[i][j] = min(total_replace, total_delete, total_insert)
    
    return dp[n][m]

# 测试用例
cost_config = {
    **{num: 1 for num in range(1, 21)},
    98: 10,
    99: 15,
    (9, 98): 12,  # 可选：自定义特定数字对的替换成本
    (98, 9): 12
}
list_x = [1, 9, 20, 99]
list_y = [2, 98, 20]
print(weighted_levenshtein(list_x, list_y, cost_config))

方案二：改造现有库适配数字列表 #

如果你不想从零编写DP逻辑，可以基于textdistance这类库的基础框架扩展，但本质还是需要封装自己的成本计算逻辑，工作量和自定义实现相差不大，因此更推荐方案一。

结论 #

目前没有专门支持数字列表带权Levenshtein距离的主流Python库，多数编辑距离库都是针对字符串设计的。自定义动态规划实现是最直接、可控的解决方案，能灵活适配数字元素的整体比较需求，完全满足你对成本规则的自定义要求。

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