Сравнение строк Python, указывающее на результат

Я пытаюсь сравнить 2 1000 байтов строки и хотел бы знать, где именно начинается разница, т.е. от какого байта отличается строка .. Есть ли какая-нибудь функция для ее определения?

 mgilson11 окт. 2012 г., 15:31
Кажется, что-то вроде этого должно быть вdifflib, Но я могу'не могу найти это.
 John La Rooy11 окт. 2012 г., 15:41
@mgilson, я дал ответ, используя difflib, но я думаю, чтодовольно неуклюжий в использовании по сравнению с генератором выражения I '

Ответы на вопрос(6)

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

Если a или b не 't 0, строки отличаются с самого начала

 jlengrand11 окт. 2012 г., 15:58
@gnibbler Хам, понял. Спасибо за ответ
 jlengrand11 окт. 2012 г., 15:41
В самом деле. Этот вопрос заставил меня открыть для себя действительно интересную тему.
 jlengrand11 окт. 2012 г., 15:49
@gnibbler Забавно, что парень с большим количеством очков получает +1, хотя другой уже публиковал с тем же решением: D. Почему вы бы назвали это нечистым? Лучше использовать стандартную библиотеку, чем пользовательский код, который может содержать ошибки, не так ли?не так ли?
 John La Rooy11 окт. 2012 г., 15:43
@jlengrand, да, это такочень мощный, но не очень чистый для этого конкретного вопроса.
 John La Rooy11 окт. 2012 г., 15:57
@jlengrand, потому что в этом случае вы можетепросто проверьте размер, чтобы получить результат. ты должен сделать что-то вродеmatch.size if match.a==match.b==0 else 0
 mgilson11 окт. 2012 г., 15:47
@gnibbler - ямы не использовалиdifflib так многоПриятно видеть этот пример. Благодарю. (и +1 - я думаю, что этоДостаточно чистый - Конечно, не намного хуже, чем)next( ... enumerate(izip(s1,s2)) ...)
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.')

zip() возвращает список кортежей, а не итератор. Как указал Гнибблер, если выВы используете Python 2.x, возможно, стоит потратить время на его использованиеizip скорее, чем (zipizip возвращает хороший итератор с эффективным использованием памяти, который позволяет избежать оценки всех значений одновременно). Как я уже сказал в комментариях, в Python 3izip был переименованzip и старыйzip ушел

 Joel Cornett11 окт. 2012 г., 22:58
@gnibbler: Выверно. Я первоначально проверил это в Python 3, где.zip==izip
 John La Rooy11 окт. 2012 г., 15:59
Может быть стоит использоватьizip поскольку строки довольно длинные, если только вы не ожидаете, что различия всегда будут ближе к концу
 mgilson11 окт. 2012 г., 15:26
Я думаю, вам нужно круглые скобкиx,y поскольку перечисление приведет к кортежу вида(idx, (aval,bval))

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. , ,

Для таких больших струн, как ваша, это может быть очень интересно. :)

использоватьnext плюс генератор?

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'
 user105061911 окт. 2012 г., 15:55
Большое спасибо .. это сработало
 mgilson11 окт. 2012 г., 18:35
@senderle - Да, яЯ не совсем уверен. Я'Я предполагаю, что это было предвидено, но я полагаю, что мы точно знаем,Мне нужно спросить Гвидо и разработчиков Python. Это'быстро становится одним из моих любимых моделей. Очень полезно.
 senderle11 окт. 2012 г., 17:47
Один из моих любимых паттернов в Python. Я'Мы часто задавались вопросом, было ли это предвидено, когда были введены гены, илиЭто просто естественный результат хорошего дизайна.

но так как вы, похоже, беспокоитесь о скорости, вы можете рассмотреть возможность использования 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

Для различий в конце, это намного быстрее, чем genx:

>>> %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»ответ.

 Bakuriu11 окт. 2012 г., 17:50
Ницца! Хотя для этого решения требуется сторонняя библиотека.
Решение Вопроса

приведенные здесь, и ямы придумали другого,Быстрее(в обычных случаях) решение, хотя оно и не так элегантно.

Прежде всего, давайтеПосмотрим, насколько быстрыми являются предлагаемые решения:

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

Тот'больше чемтридцать пять раз быстрее, чем genxp!

Почему это работает? Сравнения, очевидно, занимают линейное время, поэтому похоже, что мы делаем гораздо больше работы, чем раньше ... и это 'правда, но это правдасделано на "С уровень "и, следовательно, в результате этот метод на самом деле быстрее.

Обратите внимание, что это как-токонкретная реализация " потому что реализации, такие как 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

Как видите, даже с огромными строками этот метод все еще примерно в тридцать раз быстрее.

Замечания: Недостатком этого решения является то, что оно ϴ(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. Использование байтов вместо строк Юникода не делаетзначительно изменить результаты

 Bakuriu11 окт. 2012 г., 17:47
@senderle: много. Я'мы добавили ещепрофилирование» работает, и вы можете видеть, что этоДовольно сложно сделать это менее чем в 8 раз быстрее.
 senderle11 окт. 2012 г., 17:41
+1 - умный! То, что это работает так хорошо, меня забавляет. Интересно, сколько времени может пройти строка, прежде чем эта стратегия станет медленнее.
 0xc0de30 дек. 2016 г., 06:15
Большой! Хотя он менее питоничен, чем экспрессия генов, и тот факт, что OP нея специально просил о производительности, мне нравится этот подход, поскольку онs показал мне лучший способ для кодирования многих вещей. Ну, не совсем новый, этоЭто то, что я уже знал!

Ваш ответ на вопрос