Python - 两个字符串之间的差异

Question

我想在列表中存储很多单词。其中许多词非常相似。例如，我有单词

afrykanerskojęzyczny

和许多单词，如

afrykanerskojęzycznym

、

afrykanerskojęzyczni

、

nieafrykanerskojęzyczni

。找到两个字符串之间的差异并从第一个字符串和差异恢复第二个字符串的有效（快速且差异大小较小）解决方案是什么？

Answer 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

Answer 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] != ' ']

Answer 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'

Answer 4

您要求的是一种特殊形式的压缩。 xdelta3 是为这种特殊类型的压缩而设计的，并且有一个针对它的 python 绑定，但您可能可以直接使用 zlib 。 您需要使用

zlib.compressobj

和

zlib.decompressobj

，并将

zdict

参数设置为“基本词”，例如

afrykanerskojęzyczny

。

注意事项是

zdict

仅在 python 3.3 及更高版本中受支持，如果所有差异都具有相同的“基本词”，那么编码是最容易的，这可能是也可能不是您想要的。

Answer 5

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

nltk.metrics.distance.edit_distance()

是一个成熟的（非标准）库实现，用于计算

Levenshtein距离

一个简单的例子可能是：

from nltk.metrics.distance import *

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

Out: 3

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

Answer 6

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

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

这将执行以下操作：

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

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

Answer 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)]

Answer 8

如果有人需要更简单的东西，我已经写了：

  def diffstr( a, b, withspaces=1):
  la = len(a)
  lb = len(b)
  if la > lb:
    while len(b) < la:
      b += ' '
  elif la < lb:
    while len(a) < lb:
      a += ' '
  # compute:
  ls=''
  for i in range( 0, len(a)):
    if a[i] == b[i]:
      ls += ' '
    else:
      if b[i] != ' ':
        ls += b[i]
      else:
        ls += a[i]
        
  if withspaces:
    return ls
  else:
    return ls.replace(' ', '')