我有两个类似的字符串。如何在Python中找到这两个字符串之间最可能的单词对齐方式？
输入示例：
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'
对齐很棘手。spaCy可以做到这一点(请参阅对齐标记化(，但AFAIK假设两个底层字符串是相同的，而这里的情况并非如此。
几年前，我曾使用Bio.pairwise2来解决类似的问题。我不太记得确切的设置，但以下是默认设置给你的：
from Bio import pairwise2
from Bio.pairwise2 import format_alignment
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.'
alignments = pairwise2.align.globalxx(string1.split(),
string2.split(),
gap_char=['-']
)
由此产生的对齐-已经非常接近：
>>> format_alignment(*alignments[0])
my channel is youtube dot com slash example - and then I also do live streaming - on twitch.
| | | | | | | | | |
my channel is - - - - - youtube.com/example and then I also do - - livestreaming on twitch.
Score=10
您可以提供自己的匹配函数，这将使fuzzywuzzy成为一个有趣的添加。
以前的答案提供了基于生物学的比对方法，也有基于NLP的比对方法。最标准的是Levenstein编辑距离。有一些变体，通常认为这个问题与文本相似性度量(也称为模糊匹配等(的问题密切相关。特别是，在单词和字符的级别上混合对齐是可能的。以及不同的措施(例如SoftTFIDF，请参阅此答案(。
Needleman Wunch算法
生物学家有时试图将两种不同植物或动物的DNA比对，看看它们有多少基因组是共同的。
MOUSE: A A T C C G C T A G
RAT: A A A C C C T T A G
+ + - + + - - + + +
上面的"；CCD_ 2"；意味着DNA片段匹配
以上"CCD_ 3"；意味着DNA片段不匹配。
您可以使用完整的ASCII字符集(128个字符(，而不是生物学家使用的字母ATCG。
我建议使用Needleman-Wunsch算法
Needle Wunsch是而不是世界上最快的算法
然而，Needle Wunsch很容易理解。
在英语文本的一个字符串完全缺少另一个文本中存在的单词的情况下，Needleman Wunsch将该单词与特殊的"匹配；GAP"；性格
+-------+--------+-------+---+------+----+-----+-------+-----+----+-----+-------+------+
| The | reason | that | I | went | to | the | store | was | to | buy | some | food |
+-------+--------+-------+---+------+----+-----+-------+-----+----+-----+-------+------+
| <GAP> | reason | <GAP> | I | went | 2 | te | store | wuz | 2 | buy | <GAP> | fud |
+-------+--------+-------+---+------+----+-----+-------+-----+----+-----+-------+------+
特殊的GAP字符很好。
然而，Needle Wunsch的有效之处在于，编写算法的人认为间隙字符的顺序很重要。以下两种情况分别计算：
对齐一
+---+-------+-------+---+---+
| A | 1 | <GAP> | R | A |
+---+-------+-------+---+---+
| A | <GAP> | B | R | A |
+---+-------+-------+---+---+
对齐二
+---+-------+-------+---+---+
| A | <GAP> | 1 | R | A |
+---+-------+-------+---+---+
| A | B | <GAP> | R | A |
+---+-------+-------+---+---+
然而，若一行中有两个或多个间隙，那个么间隙的顺序应该无关紧要。
Needleman-Wunch算法多次计算相同的东西，因为无论是谁编写算法，都认为顺序比实际情况更重要。
以下两条路线的分数相同。
此外，两种排列在"；真实世界"；(计算机外部(。
然而，Needleman-Wunch算法将两次计算两个示例比对的分数，而不是只计算一次。