Zwei Zeichenketten zeichenweise vergleichen in Python

Manchmal reicht ein einfacher Gleichheitstest nicht aus: Sie müssen wissen, an wie vielen Positionen zweier Strings das gleiche Zeichen steht, oder wo genau sie beginnen, sich zu unterscheiden. Python hat kein einzelnes Built-in, das eine positionsbezogene Trefferzahl zurückgibt, aber zip() und ein Generatorausdruck machen daraus eine Ein-Zeilen-Lösung.

Dieser Artikel zeigt zuerst den zip()-Ansatz, danach eine Indexschleife für den Fall, dass die Positionen selbst wichtig sind, den Umgang mit Strings unterschiedlicher Länge und mit Nicht-String-Eingaben, wie eine Trefferzahl zu == und der Hamming-Distanz in Beziehung steht und was der Vergleich kostet.

Zwei Strings Zeichen für Zeichen mit zip() vergleichen

Der kürzeste Weg, zwei Strings Position für Position zu vergleichen, besteht darin, die Zeichen mit zip() zu paaren und die übereinstimmenden Paare zu zählen. zip(first, second) liefert die Tupel (first[0], second[0]), (first[1], second[1]) und so weiter und stoppt, sobald der kürzere String aufgebraucht ist; das Ergebnis ist daher immer eine Zählung über das gemeinsame Präfix.

Werden diese Paare durch einen Generatorausdruck in sum() geleitet, zählt jeder True-Vergleich als eins. Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

def count_matching_positions(first, second):
    return sum(a == b for a, b in zip(first, second))


print(count_matching_positions("apple", "apricot"))
print(count_matching_positions("homophones", "homonyms"))
print(count_matching_positions("apple", "applepie"))

2
4
5

"apple" und "apricot" stimmen nur in den ersten beiden Positionen überein, "homophones" und "homonyms" stimmen in vier der acht Positionen überein, die zip() erzeugt, und "apple" stimmt mit allen fünf Zeichen des Präfixes überein, das es mit "applepie" teilt. Dieses letzte Ergebnis ist wichtig: Fünf übereinstimmende Positionen bedeuten nicht, dass die Strings gleich sind, sondern nur, dass alles übereinstimmte, was zip() verglichen hat.

Ein Hinweis dazu, was hier ein „Zeichen“ bedeutet: Python iteriert einen String nach Unicode-Codepoint, nicht nach dem, was ein Leser als einen Buchstaben wahrnimmt. Ein "é", das als e gefolgt von einem kombinierenden Akzent geschrieben wird, besteht aus zwei Codepoints; zwei visuell identische Strings können daher unterschiedliche Zählwerte liefern, bis sie mit unicodedata.normalize() normalisiert werden.

Eine Indexschleife verwenden, wenn Sie die Positionen brauchen

zip() sagt Ihnen, ob Zeichen übereinstimmen, verwirft aber den Index. Wenn Sie wissen müssen, welche Position abweicht – etwa um die erste Abweichung zu melden oder den Vergleich auf einen Slice zu beschränken –, steuern Sie die Schleife mit range() über die kürzere Länge:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

def compare_with_positions(first, second):
    size = min(len(first), len(second))
    matches = 0
    for i in range(size):
        if first[i] == second[i]:
            matches += 1
        else:
            print(f"position {i}: {first[i]!r} versus {second[i]!r}")
    return matches


print("matches:", compare_with_positions("homophones", "homonyms"))

position 4: 'p' versus 'n'
position 5: 'h' versus 'y'
position 6: 'o' versus 'm'
position 7: 'n' versus 's'
matches: 4

Eine while-Schleife erledigt dieselbe Aufgabe, wenn Sie explizite Kontrolle über den Index wünschen: Initialisieren Sie i = 0, schleifen Sie while i < size und erhöhen Sie i selbst. enumerate(zip(first, second)) ist eine dritte Option, die Ihnen (index, (char1, char2))-Tupel ohne manuellen Zähler liefert.

Unterschiedliche Längen und Nicht-String-Eingaben behandeln

Die zip()-Beispiele teilen einen Vertrag: Beide Argumente werden als Strings erwartet, und der Vergleich umfasst nur das gemeinsame Präfix. Zwei Konsequenzen lohnen eine bewusste Behandlung.

Erstens untersucht zip() niemals den Rest des längeren Strings. Soll ein nachfolgender Rest gegen das Ergebnis zählen – wie es bei der Gleichheit der Fall ist –, prüfen Sie die Längen selbst oder paaren Sie die Strings mit itertools.zip_longest(first, second, fillvalue=...), das die kürzere Eingabe auffüllt, sodass jede Position besucht wird.

Zweitens ist die Übergabe von None oder eines anderen Nicht-Strings ein Programmierfehler, kein Vergleich, der zufällig keine Treffer findet. 0 für count_matching_positions("apple", None) zurückzugeben, verwechselt einen fehlerhaften Aufruf mit einem echten Ergebnis. Weisen Sie die Eingabe stattdessen zurück, damit der Aufrufer es erfährt:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

def count_matching_positions(first, second):
    if not isinstance(first, str) or not isinstance(second, str):
        raise TypeError("expected two strings")
    return sum(a == b for a, b in zip(first, second))


try:
    count_matching_positions("apple", None)
except TypeError as exc:
    print("TypeError:", exc)

print(count_matching_positions("apple", "applepie"))

TypeError: expected two strings
5

Ob auch len(first) != len(second) zurückgewiesen werden sollte, hängt von der Aufgabe ab: Eine Zählung über das gemeinsame Präfix ist für sich legitim, während ein gleichheitsartiger Test unterschiedliche Längen als unterschiedliche Strings behandeln sollte.

Treffer zählen, Gleichheit prüfen oder die Hamming-Distanz berechnen

Eine positionsbezogene Trefferzahl beantwortet eine andere Frage als ein String-Vergleich, und die falsche Wahl verursacht subtile Fehler:

• first == second prüft die Gleichheit des gesamten Strings: Jede Position stimmt überein und die Längen sind gleich. "apple" == "applepie" ist False, obwohl ihr gemeinsames Präfix vollständig übereinstimmt.
• all(a == b for a, b in zip(first, second)) sieht ähnlich aus, beweist aber nur, dass das gemeinsame Präfix gleich ist – es liefert True für "apple" und "applepie". Ergänzen Sie len(first) == len(second), um daraus einen echten Gleichheitstest zu machen, oder verwenden Sie einfach ==.
• Die Hamming-Distanz geht in die andere Richtung: Sie zählt die Positionen, die sich unterscheiden, und ist nur für Strings gleicher Länge definiert. Bei gleich langen Eingaben ist sie genau len(first) minus der Trefferzahl.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

def hamming_distance(first, second):
    if len(first) != len(second):
        raise ValueError("Hamming distance needs strings of equal length")
    return sum(a != b for a, b in zip(first, second))


first, second = "apple", "applepie"
print(first == second)
print(sum(a == b for a, b in zip(first, second)))
print(hamming_distance("karolin", "kathrin"))

False
5
3

"karolin" und "kathrin" unterscheiden sich an den Positionen 2, 3 und 4, ihre Hamming-Distanz beträgt also 3 – und weil die Strings gleich lang sind, entspricht sie 7 - 4.

Zeit- und Speicherkomplexität verstehen

Sowohl die zip()-Zählung als auch die Indexschleife untersuchen höchstens min(len(first), len(second)) Zeichenpaare; die Laufzeit beträgt daher O(min(len(first), len(second))) – linear in der kürzeren Eingabe. Der schlimmste Fall tritt ein, wenn die Strings über ihr gesamtes gemeinsames Präfix übereinstimmen; eine Schleife, die bei der ersten Abweichung stoppt, kann früher enden.

Der zusätzliche Speicherbedarf ist O(1): zip() und der Generatorausdruck sind träge (lazy) Iteratoren, die jeweils nur ein Paar vorhalten, und der Zähler ist eine einzelne Ganzzahl. Die Paare mit list(zip(first, second)) zu materialisieren würde stattdessen O(min(len(first), len(second))) Speicher ohne Nutzen kosten – behalten Sie also die Generatorform bei.

Zum Vergleich: first == second ist im schlimmsten Fall ebenfalls linear, obwohl der Vergleich stoppen kann, sobald eine Differenz gefunden wird.