Python-两个字符串之间的区别

问题描述：

我想在一个列表中存储很多单词。其中很多单词非常相似。例如，我有单词afrykanerskojęzyczny和很多单词，如afrykanerskojęzycznym，，afrykanerskojęzyczni。nieafrykanerskojęzyczni有什么有效的（快速且差异较小的）解决方案可以找到两个字符串之间的差异并从第一个字符串和差异中恢复第二个字符串？

解决方案 1：

您可以使用difflib 模块中的ndiff来执行此操作。它具有将一个字符串转换为另一个字符串所需的所有信息。

一个简单的例子：

import difflib

cases=[('afrykanerskojęzyczny', 'afrykanerskojęzycznym'),
       ('afrykanerskojęzyczni', 'nieafrykanerskojęzyczni'),
       ('afrykanerskojęzycznym', 'afrykanerskojęzyczny'),
       ('nieafrykanerskojęzyczni', 'afrykanerskojęzyczni'),
       ('nieafrynerskojęzyczni', 'afrykanerskojzyczni'),
       ('abcdefg','xac')] 

for a,b in cases:     
    print('{} => {}'.format(a,b))  
    for i,s in enumerate(difflib.ndiff(a, b)):
        if s[0]==' ': continue
        elif s[0]=='-':
            print(u'Delete "{}" from position {}'.format(s[-1],i))
        elif s[0]=='+':
            print(u'Add "{}" to position {}'.format(s[-1],i))    
    print()      

印刷：

afrykanerskojęzyczny => afrykanerskojęzycznym
Add "m" to position 20

afrykanerskojęzyczni => nieafrykanerskojęzyczni
Add "n" to position 0
Add "i" to position 1
Add "e" to position 2

afrykanerskojęzycznym => afrykanerskojęzyczny
Delete "m" from position 20

nieafrykanerskojęzyczni => afrykanerskojęzyczni
Delete "n" from position 0
Delete "i" from position 1
Delete "e" from position 2

nieafrynerskojęzyczni => afrykanerskojzyczni
Delete "n" from position 0
Delete "i" from position 1
Delete "e" from position 2
Add "k" to position 7
Add "a" to position 8
Delete "ę" from position 16

abcdefg => xac
Add "x" to position 0
Delete "b" from position 2
Delete "d" from position 4
Delete "e" from position 5
Delete "f" from position 6
Delete "g" from position 7

解决方案 2：

我喜欢 ndiff 答案，但如果你想将其全部放入仅包含更改的列表中，你可以执行以下操作：

import difflib

case_a = 'afrykbnerskojęzyczny'
case_b = 'afrykanerskojęzycznym'

output_list = [li for li in difflib.ndiff(case_a, case_b) if li[0] != ' ']

解决方案 3：

您可以查看正则表达式模块（模糊部分）。我不知道您是否可以获得实际差异，但至少您可以指定允许的不同类型的更改数量，例如插入、删除和替换：

import regex
sequence = 'afrykanerskojezyczny'
queries = [ 'afrykanerskojezycznym', 'afrykanerskojezyczni', 
            'nieafrykanerskojezyczni' ]
for q in queries:
    m = regex.search(r'(%s){e<=2}'%q, sequence)
    print 'match' if m else 'nomatch'

解决方案 4：

您所要求的是一种特殊形式的压缩。xdelta3 是为这种特殊类型的压缩而设计的，并且有一个 python 绑定，但您可能可以直接使用 zlib。您可能希望使用zlib.compressobj并将zlib.decompressobj参数zdict设置为您的“基本词”，例如afrykanerskojęzyczny。

需要注意的是zdict，只有 python 3.3 及更高版本才支持，并且如果您的所有差异都有相同的“基本词”，则编码最容易，这可能是也可能不是您想要的。

解决方案 5：

您可能会发现NLTK库中提供的工具对于计算不同单词之间的差异很有用。

nltk.metrics.distance.edit_distance()是一个成熟的（非标准）库实现，用于计算Levenshtein 距离

一个简单的例子可能是：

from nltk.metrics.distance import *

w1 = 'wordone'
w2 = 'wordtwo'
edit_distance(w1, w2)

Out: 3

附加参数允许对输出进行加权，具体取决于不同操作（替换/插入）的成本和不同字符差异（例如，键盘上更近的字符的成本较低）。

解决方案 6：

我对上述原始问题的评论的回答让我认为这就是他想要的：

loopnum = 0
word = 'afrykanerskojęzyczny'
wordlist = ['afrykanerskojęzycznym','afrykanerskojęzyczni','nieafrykanerskojęzyczni']
for i in wordlist:
    wordlist[loopnum] = word
    loopnum += 1

这将执行以下操作：

对于单词表中的每个值，将单词表的该值设置为原始代码。

您所要做的就是将这段代码放在您需要更改单词表的地方，确保您将需要更改的单词存储在单词表中，并且原始单词是正确的。

解决方案 7：

我发现这个问题很有趣，即使这是一个老问题，我也想尝试开发一个不使用任何外部库的解决方案。

import pytest

@pytest.mark.parametrize(
    "s1,s2,expected",
    [
        ("", "", ["", ""]),
        ("a", "a", ["", ""]),
        ("a", "b", ["a", "b"]),
        ("ac", "bc", ["a", "b"]),
        ("ca", "cb", ["a", "b"]),
        ("this is a message", "this is b message", ["a", "b"]),
        ("this is a huge message", "this is b message", ["a huge", "b"]),
    ],
)
def test_string_diff(s1, s2, expected):
    assert string_diff(s1, s2) == expected


def string_diff(s1: str, s2: str) -> str:
    d1, d2 = [], []
    i1 = i2 = 0
    l1 = len(s1)
    l2 = len(s2)
    while True:
        if i1 >= len(s1) or i2 >= len(s2):
            d1.extend(s1[i1:])
            d2.extend(s2[i2:])
            break
        if s1[i1] != s2[i2]:
            e1 = l1 - i1
            e2 = l2 - i2
            if e1 > e2:
                d1.append(s1[i1])
                i2 -= 1
            elif e1 < e2:
                d2.append(s2[i2])
                i1 -= 1
            else:
                d1.append(s1[i1])
                d2.append(s2[i2])
        i1 += 1
        i2 += 1
    return ["".join(d1), "".join(d2)]