logo标签列表

Python字符串比较指向结果

python
3

我正在尝试比较两个1000字节的字符串，并想知道区别开始的位置，也就是说，哪个字节是不同的...是否有函数可以确定它？

1
好像这种东西应该在 difflib 中，但我找不到。 - mgilson
1
@mgilson，我用difflib给出了一个答案，但我认为与生成器表达式相比，它使用起来相当笨拙。 - John La Rooy
6个回答
9
也许可以使用next和生成器(generator)？
next(idx for idx,c in enumerate(your_string1) if c != your_string2[idx])

这将给你一个不同之处开始的索引，并在它们相等时引发StopIteration。

如果使用itertools.izip，可能会更加优雅：

next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)

例子：

>>> from itertools import izip
>>> s1 = 'stop at the bus'
>>> s2 = 'stop at the car'
>>> next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
12
>>> s1[12]
'b'
>>> s2[12]
'c'
我最喜欢的 Python 模式之一。我经常想知道这是否是在引入 genexes 时预见到的，还是只是良好设计的自然结果。 - senderle
@senderle -- 是的，我不是完全确定。我猜想这是预见到的，但要确定我们需要问Guido和Python开发人员。这也成为了我最喜欢的模式之一。非常有用。 - mgilson
4

我尝试测试了这里提供的答案，并且找到了另一种解决方案，通常情况下更快，虽然不太优雅。

首先让我们看看提出的解决方案有多快：

In [15]: def check_genexp(a, b):
    ...:     return next(idx for idx, c in enumerate(a) if c != b[idx])

In [16]: %timeit check_genexp("a"*9999 + "b", "a"*9999 + "c")
1000 loops, best of 3: 1.04 ms per loop

In [17]: from difflib import SequenceMatcher

In [18]: def check_matcher(a, b):
    ...:     return next(SequenceMatcher(a=a, b=b).get_matching_blocks())
    ...: 

In [19]: %timeit check_matcher("a"*9999+"b", "a"*9999+"c")
100 loops, best of 3: 11.5 ms per loop

正如您所看到的，genexp比difflib快得多，但这可能是因为SequenceMatcher做了比找到第一个不相等字符更多的工作。
那么，我们该如何加速呢？我们可以使用“二分查找”！其思想是，如果两个字符串不相等，则前半部分或后半部分不同（或两者都不同，在这种情况下，我们只关心第一半部分，因为我们想要第一个不同的索引）。
因此，我们可以这样做：
def binary_check(a, b):
    len_a, len_b = len(a), len(b)
    if len_a == len_b:
        return binary_check_helper(a, b)
    min_length, max_length = min(len_a, len_b), max(len_a, len_b)
    res = binary_check_helper(a[:min_length], b[:min_length])
    return res if res >= 0 else min_length

def binary_check_helper(a, b):
    if a == b:
        return -1
    length = len(a)

    if length == 1:
        return int(a[0] == b[0])
    else:
        half_length = length // 2
        r = binary_check_helper(a[:half_length], b[:half_length])
        if r >= 0:
            return r
        r = binary_check(a[half_length:], b[half_length:])
        if r >= 0:
            return r + half_length
        return r

结果如下：
In [34]: %timeit binary_check("a"*9999 + "b", "a"*9999 + "c")
10000 loops, best of 3: 28.4 µs per loop

这比genexp快了35倍以上！

为什么会这样呢？显然，比较操作需要线性时间，所以看起来我们做的工作比之前多得多...确实如此，但是它是在"C级别"完成的， 因此结果是这种方法实际上更快。

需要注意的是，这在某种程度上是“实现特定”的，因为像PyPy这样的实现可能会将genexp优化为单个C-for循环，并且这将超越任何东西； 而在像Jython或IronPython这样的实现中，速度可能比CPython慢得多。

该方法具有与其他方法相同的渐近复杂度，即O(n)。字符串最多分成一半log_2(n)次，每次进行相等性测试，这需要线性时间。乍一看，它可能是一个Θ(n * logn)算法，但事实并非如此。递归方程为：

T(n) = T(n//2) + Θ(n) = Σ_{i=0}^{logn}(n/2^i)
     = Θ(n(1 + 1/2 + 1/4 + ...)) <= Θ(2n) = Θ(n)
一些更多的结果：
In [37]: %timeit binary_check("a"*10**6 + "b", "a"*10**6 + "c")
100 loops, best of 3: 2.84 ms per loop

In [38]: %timeit check_genexp("a"*10**6 + "b", "a"*10**6 + "c")
10 loops, best of 3: 101 ms per loop

In [39]: %timeit binary_check(15 * "a"*10**6 + "b", 15 * "a"*10**6 + "c")
10 loops, best of 3: 53.3 ms per loop

In [40]: %timeit check_genexp(15 * "a"*10**6 + "b", 15 * "a"*10**6 + "c")
1 loops, best of 3: 1.5 s per loop

您可以看到，即使是处理巨大字符串，这种方法仍然快大约30倍。

注意：该解决方案的缺点是它是ϴ(n)而不是O(n)，也就是说，它总是需要读取整个字符串才能返回结果。即使第一个字符已经不同。实际上：

In [49]: a = "b" + "a" * 15 * 10**6
    ...: b = "c" + "a" * 15 * 10**6
    ...: 

In [50]: %timeit binary_check(a, b)
100 loops, best of 3: 10.3 ms per loop

In [51]: %timeit check_genexp(a, b)
1000000 loops, best of 3: 1.3 µs per loop

这是可以预料的。然而，只需很少的改进，该解决方案就可以比显式循环更有效：

In [59]: a = "a" * 2 * 10**5 + "b" + "a" * 15*10**6
    ...: b = "a" * 2 * 10**5 + "c" + "a" * 15*10**6

In [60]: %timeit check_genexp(a, b)
10 loops, best of 3: 20.3 ms per loop

In [61]: %timeit binary_check(a, b)
100 loops, best of 3: 17.3 ms per loop

根据这个简单基准，如果大字符串的差异超过总长度的约1.3%，则二进制检查更好。

还可以引入一些启发式算法。例如，如果两个字符串的最小长度大于某个截止值，则首先仅检查该截止处的前缀是否不同，如果它们不同，则可以忽略其后的所有内容，从而避免比较整个字符串。这可以轻松地实现：

def binary_check2(a, b, cutoff=1000):
    len_a, len_b = len(a), len(b)
    if min(len_a, len_b) > cutoff:
        small_a, small_b = a[:cutoff], b[:cutoff]
        if small_a != small_b:
            return binary_check_helper(a[:cutoff], b[:cutoff])
    # same as before

根据应用程序，您可以选择一个截止点以最小化平均时间。无论如何，这是一种特别的启发式方法，可能效果好也可能效果差，因此，如果您处理的是只有短公共前缀的非常长字符串，则应使用“快速失败”算法，如 genexp 方法。

在python3.4上执行时间。使用字节而不是Unicode字符串不会显著改变结果

+1 -- 聪明！这个方法如此有效让我感到很有趣。我想知道在这种策略变慢之前，字符串可以变得多长。 - senderle
@senderle：很多。我添加了一些更多的“分析”运行，你可以看到它很难使它比8倍更快。 - Bakuriu
太好了！虽然这种方法不如生成表达式那么Pythonic，而且OP并没有特别要求性能，但我喜欢这种方法，因为它向我展示了更好的编码方式。嗯，其实并不是新的，这是我已经知道的东西！ - 0xc0de
2
for i, (x, y) in enumerate(zip(a, b)):
    if x != y:
        print('First index where strings are different:', i)
        break
else:
    print('Strings are identical.')

在Python 2.x中，zip()返回一个元组列表而不是迭代器。正如gnibbler所指出的那样，如果你在使用Python 2.x，使用izip而不是zip可能是值得的（izip返回一个漂亮的、内存高效的迭代器，避免一次性评估所有值）。但是正如我在评论中所说的，在Python 3中，izip已经被重命名为zip，而旧的zip已经不存在了。
3
我认为你需要在 x，y 周围加上括号，因为 enumerate 会生成形式为 (idx，(aval，bval)) 的元组。 - mgilson
1
值得考虑使用izip，因为字符串相当长，除非您预计差异总是接近结尾。 - John La Rooy
@gnibbler：你说得对。我最初是在Python 3中测试的，其中zip==izip。 - Joel Cornett
2
如果您想要更复杂的东西，可以看看SequenceMatcher。
它有点棘手，但非常强大。如果您只是想回答您的问题，则：
from  difflib import SequenceMatcher

s1 = 'stop at the bus'
s2 = 'stop at the car'

s = SequenceMatcher(None, s1, s2)

print s.get_matching_blocks()[0].size

返回解决方案 :)
但如果你想要所有匹配项：
小例子：
from  difflib import SequenceMatcher

s1 = 'stop at the bus'
s2 = 'stop at the car'

s = SequenceMatcher(None, s1, s2)

print s.get_matching_blocks()

返回
[Match(a=0, b=0, size=12), Match(a=15, b=15, size=0)]

这意味着你的字符串中最长的匹配长度为12，并且从开头（0）开始。但是还有另一个匹配项，从s1 [15]开始，大小为0......对于像你这样的大字符串来说，这可能非常有趣。 :)
1
>>> s1 = 'stop at the bus'
>>> s2 = 'stop at the car'
>>> import difflib
>>> next(difflib.SequenceMatcher(a=s1, b=s2).get_matching_blocks())
Match(a=0, b=0, size=12)

这意味着第一个匹配块长度为12个字符。

如果a或b中任意一个不为0，则字符串从一开始就不同。

确实。这个问题让我发现了一个非常有趣的库。 - jlengrand
@jlengrand，是的，它非常强大，但对于这个特定的问题来说不太干净。 - John La Rooy
@gnibbler -- 我很少使用difflib，所以很高兴看到这个例子。谢谢。(并+1 -- 我认为它相当干净 -- 当然不比next( ... enumerate(izip(s1,s2)) ...)更糟) - mgilson
有趣的是拥有更多积分的人得到了+1，尽管另一个人先发布了相同的解决方案:D。你为什么要称其为不干净？使用标准库比使用可能存在漏洞的自定义代码更好，是吧？ - jlengrand
@jlengrand，因为在这种情况下，您不能仅通过检查大小来获取结果。您必须执行类似于match.size if match.a==match.b==0 else 0的操作。 - John La Rooy
1

这可能有点过度，但既然您似乎关心速度，您可以考虑使用numpy。可能还有改进的空间（由于某种原因，内联对我产生了25微秒的差异），但这是第一步：

>>> def diff_index(s1, s2):
...     s1 = numpy.fromstring(s1, dtype=numpy.uint8)
...     s2 = numpy.fromstring(s2, dtype=numpy.uint8)
...     return (~(s1 == s2)).nonzero()[0][0]
... 
>>> base = string.lowercase * 385
>>> s1 = base + 'a'
>>> s2 = base + 'z'
>>> diff_index(s1, s2)
10010

针对结尾处的差异，这比genex快得多：

>>> %timeit next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
1000 loops, best of 3: 1.46 ms per loop
>>> %timeit diff_index(s1, s2)
10000 loops, best of 3: 87.6 us per loop

在最开始的差异处速度会慢很多...

>>> s1 = 'a' + base
>>> s2 = 'z' + base
>>> %timeit next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
100000 loops, best of 3: 2.12 us per loop
>>> %timeit diff_index(s1, s2)
10000 loops, best of 3: 87.5 us per loop

但平均而言，它的胜率高达一个数量级：

>>> s1 = base[:5000] + 'a' + base[5000:]
>>> s2 = base[:5000] + 'z' + base[5000:]
>>> %timeit next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
1000 loops, best of 3: 724 us per loop
>>> %timeit diff_index(s1, s2)
10000 loops, best of 3: 87.2 us per loop

如果速度不是问题，那么我个人会选择mgilson的答案。
不错！尽管这个解决方案需要使用第三方库。 - Bakuriu
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接