如何在Python中实现两个相似字符串间的最可能单词对齐？

问题描述 #

我有两个相似的字符串，需要找到它们之间最合理的单词对齐关系——比如将第一个字符串中的多个拆分单词（如youtube、dot、com、slash、example）对应到第二个字符串中的复合词youtube.com/example，或者将live、streaming对应到livestreaming。

输入示例 #

string1 = 'my channel is youtube dot com slash example and then I also do live streaming on twitch.'
string2 = 'my channel is youtube.com/example and then I also do livestreaming on twitch.'

期望输出 #

最终得到一个字典，每个键是第一个字符串的单词，值是其在第二个字符串中对应的单词：

alignment['my']        = 'my'
alignment['channel']   = 'channel'
alignment['is']        = 'is'
alignment['youtube']   = 'youtube.com/example'
alignment['dot']       = 'youtube.com/example'
alignment['com']       = 'youtube.com/example'
alignment['slash']     = 'youtube.com/example'
alignment['example']   = 'youtube.com/example'
alignment['and']       = 'and'
alignment['then']      = 'then'
alignment['I']         = 'I'
alignment['also']      = 'also'
alignment['do']        = 'do'
alignment['live']      = 'livestreaming'
alignment['streaming'] = 'livestreaming'
alignment['on']        = 'on'
alignment['twitch']    = 'twitch'

实现方案 #

我们可以基于**动态规划（DP）**实现单词级的序列对齐，核心是计算两个单词序列的最优匹配路径，允许一对多的映射。以下是具体代码：

def word_alignment(str1, str2):
    # 拆分字符串为单词列表，同时去除标点
    def split_words(s):
        return [word.strip('.,!?') for word in s.split()]
    
    words1 = split_words(str1)
    words2 = split_words(str2)
    
    len1, len2 = len(words1), len(words2)
    
    # 初始化DP表：dp[i][j]表示words1前i个单词和words2前j个单词的最小对齐代价
    dp = [[float('inf')] * (len2 + 1) for _ in range(len1 + 1)]
    dp[0][0] = 0
    
    # 定义代价函数：两个单词的相似度越高，代价越低
    def get_cost(word1, word2):
        # 用字符重叠度计算相似度，可替换为Levenshtein距离等更精准算法
        common_chars = set(word1.lower()) & set(word2.lower())
        return 1 - len(common_chars) / max(len(word1), len(word2))
    
    # 填充DP表
    for i in range(len1 + 1):
        for j in range(len2 + 1):
            if i > 0 and j > 0:
                # 一对一匹配或开启新的多对一匹配
                cost = get_cost(words1[i-1], words2[j-1])
                if dp[i-1][j-1] + cost < dp[i][j]:
                    dp[i][j] = dp[i-1][j-1] + cost
            if i > 0:
                # 将words1当前单词映射到已有目标单词（多对一），给较低代价鼓励合并
                if dp[i-1][j] + 0.1 < dp[i][j]:
                    dp[i][j] = dp[i-1][j] + 0.1
            if j > 0:
                # 跳过words2当前单词，设高代价避免优先选择
                if dp[i][j-1] + 1 < dp[i][j]:
                    dp[i][j] = dp[i][j-1] + 1
    
    # 回溯得到对齐关系
    alignment = {}
    i, j = len1, len2
    current_target = None
    while i > 0 or j > 0:
        if i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + get_cost(words1[i-1], words2[j-1]):
            current_target = words2[j-1]
            alignment[words1[i-1]] = current_target
            i -= 1
            j -= 1
        elif i > 0 and dp[i][j] == dp[i-1][j] + 0.1:
            # 多对一映射，沿用之前的目标单词
            alignment[words1[i-1]] = current_target
            i -= 1
        elif j > 0:
            j -= 1
    
    # 反转恢复原单词顺序
    return dict(reversed(list(alignment.items())))

# 测试示例
string1 = 'my channel is youtube dot com slash example and then I also do live streaming on twitch.'
string2 = 'my channel is youtube.com/example and then I also do livestreaming on twitch.'
alignment = word_alignment(string1, string2)

# 格式化输出
for word in alignment:
    print(f"alignment['{word}']        = '{alignment[word]}'")

代码说明 #

1. 单词拆分：将字符串拆分为单词列表，同时去除末尾标点，避免标点干扰匹配。
2. DP表设计：用二维数组记录不同长度单词序列的最小对齐代价，为后续回溯提供依据。
3. 代价函数：通过字符重叠度衡量单词相似度，相似度越高，匹配代价越低；也可替换为Levenshtein编辑距离等更精准的算法。
4. DP表填充：考虑三种匹配场景，通过设置不同代价，优先选择合理的多对一合并或一对一匹配。
5. 回溯对齐：从DP表末尾反向推导，记录每个单词的对应关系，最终恢复原单词顺序。

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