在Python中找到两个字符串之间最有可能的单词对齐方式

Question

我有 2 个相似的字符串。如何在 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'

Answer 1

对齐很棘手。 spaCy 可以做到这一点（请参阅对齐标记化），但据我所知，它假设两个底层字符串是相同的，但这里的情况并非如此。

几年前我使用

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 成为一个有趣的补充。

Answer 2

之前的答案提供了基于生物学的比对方法，也有基于NLP的比对方法。最标准的是Levenshtein 编辑距离。有一些变体，通常这个问题被认为与“文本相似性度量”（又名模糊匹配等）问题密切相关。特别是可以在单词和字符级别混合对齐。以及不同的措施（例如 SoftTFIDF，请参阅这个答案）。

Answer 3

生物学家有时会尝试比对两种不同植物或动物的 DNA，以了解它们的基因组有多少共同点。

MOUSE: A  A  T  C  C  G  C  T  A  G  
RAT:   A  A  A  C  C  C  T  T  A  G  
       +  +  -  +  +  -  -  +  +  + 

上面的“

+

”表示

DNA

片段匹配。 上面的“-
”表示

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 算法将计算两个示例比对的分数两次，而不是只计算一次。

Answer 4

difflib

 库。

它不是概率性的，但在我第一次使用它时它使用了很好的启发式方法。我用它来可视化差异，

get_opcodes

方法为我提供了一种很好的方法来构建从一个到另一个所需的编辑的各种可视化。