HOWTO · Python

Comparer deux chaînes caractère par caractère en Python

Apprenez à comparer deux chaînes caractère par caractère en Python.

Sur cette page

Une simple vérification d’égalité ne suffit pas toujours : il arrive que vous deviez savoir combien de positions de deux chaînes contiennent le même caractère, ou précisément où elles commencent à différer. Python ne propose pas de fonction intégrée unique qui renvoie un nombre de positions correspondantes, mais zip() et une expression génératrice permettent de l’écrire en une seule ligne.

Cet article présente d’abord l’approche avec zip(), puis une boucle d’index pour les cas où les positions elles-mêmes comptent, la manière de traiter des chaînes de longueurs différentes et des entrées qui ne sont pas des chaînes, le rapport entre un nombre de correspondances et == ou la distance de Hamming, et enfin le coût de la comparaison.

Comparer deux chaînes caractère par caractère avec zip()

La façon la plus courte de comparer deux chaînes position par position consiste à apparier les caractères avec zip() et à compter les paires égales. zip(first, second) produit des tuples (first[0], second[0]), (first[1], second[1]), et ainsi de suite, en s’arrêtant dès que la chaîne la plus courte est épuisée : le résultat est donc toujours un comptage sur le préfixe commun.

En passant ces paires dans une expression génératrice fournie à sum(), chaque comparaison True compte pour un. Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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" et "apricot" ne coïncident qu’aux deux premières positions, "homophones" et "homonyms" coïncident sur quatre des huit positions que produit zip(), et "apple" correspond aux cinq caractères du préfixe qu’il partage avec "applepie". Ce dernier résultat est important : cinq positions correspondantes ne signifient pas que les chaînes sont égales, seulement que tout ce que zip() a comparé correspondait.

Une précision sur ce que « caractère » signifie ici : Python parcourt une chaîne par point de code Unicode, et non selon ce qu’un lecteur perçoit comme une seule lettre. Un "é" écrit comme e suivi d’un accent combinant compte pour deux points de code, si bien que deux chaînes visuellement identiques peuvent donner des comptages différents tant qu’elles ne sont pas normalisées avec unicodedata.normalize().

Utiliser une boucle d’index lorsque vous avez besoin des positions

zip() indique si les caractères correspondent, mais il abandonne l’index. Quand vous devez savoir quelle position diffère — pour signaler la première divergence ou limiter la comparaison à une tranche — pilotez la boucle avec range() sur la longueur la plus courte :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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

Une boucle while fait le même travail quand vous voulez un contrôle explicite de l’index : initialisez i = 0, bouclez avec while i < size et incrémentez i vous-même. enumerate(zip(first, second)) est une troisième option qui vous donne des tuples (index, (char1, char2)) sans compteur manuel. Les intitulés affichés par cet exemple, comme « matches: 4 », restent en anglais car le bloc de code est reproduit tel quel.

Gérer les longueurs différentes et les entrées qui ne sont pas des chaînes

Les exemples avec zip() partagent un même contrat : les deux arguments sont censés être des chaînes, et la comparaison ne porte que sur le préfixe commun. Deux conséquences méritent d’être traitées délibérément.

Premièrement, zip() n’examine jamais la fin de la chaîne la plus longue. Si un reste final doit peser sur le résultat — comme c’est le cas pour l’égalité — vérifiez les longueurs vous-même, ou appariez les chaînes avec itertools.zip_longest(first, second, fillvalue=...), qui complète l’entrée la plus courte pour que chaque position soit visitée.

Deuxièmement, passer None ou une valeur qui n’est pas une chaîne est une erreur de programmation, pas une comparaison qui trouve simplement aucune correspondance. Renvoyer 0 pour count_matching_positions("apple", None) confond un mauvais appel avec un résultat réel. Rejetez plutôt l’entrée pour que l’appelant soit informé :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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

La question de savoir si len(first) != len(second) doit aussi être rejetée dépend de la tâche : un comptage sur le préfixe commun est légitime en soi, tandis qu’un test de type égalité doit traiter des longueurs différentes comme des chaînes différentes. Le message visible dans cet exemple reste en anglais dans le bloc de code : la sortie affiche « TypeError: expected two strings » avant le compte 5.

Compter les correspondances, tester l’égalité ou calculer la distance de Hamming

Un comptage des positions correspondantes répond à une question différente d’une comparaison de chaînes, et choisir le mauvais outil provoque des bogues subtils :

  • first == second teste l’égalité des chaînes entières : chaque position correspond et les longueurs sont identiques. "apple" == "applepie" vaut False même si leur préfixe commun correspond entièrement.
  • all(a == b for a, b in zip(first, second)) semble proche mais prouve seulement que le préfixe commun est égal — il renvoie True pour "apple" et "applepie". Ajoutez len(first) == len(second) pour en faire un vrai test d’égalité, ou utilisez simplement ==.
  • La distance de Hamming va dans l’autre sens : elle compte les positions qui diffèrent, et elle n’est définie que pour des chaînes de même longueur. Pour des entrées de même longueur, elle vaut exactement len(first) moins le nombre de correspondances.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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" et "kathrin" diffèrent aux positions 2, 3 et 4, donc leur distance de Hamming est 3 — et comme les chaînes ont la même longueur, elle vaut 7 - 4.

Comprendre la complexité en temps et en espace

Le comptage avec zip() comme la boucle d’index examinent au plus min(len(first), len(second)) paires de caractères, donc le temps d’exécution est O(min(len(first), len(second))) — linéaire dans l’entrée la plus courte. Le pire cas est atteint quand les chaînes correspondent sur tout leur préfixe commun ; une boucle qui s’arrête à la première différence peut terminer plus tôt.

L’espace auxiliaire est O(1) : zip() et l’expression génératrice sont des itérateurs paresseux qui ne conservent qu’une paire à la fois, et le compteur est un simple entier. Matérialiser les paires avec list(zip(first, second)) coûterait au contraire O(min(len(first), len(second))) en espace sans aucun bénéfice, donc conservez la forme génératrice.

Pour situer le contexte, first == second est aussi linéaire dans le pire cas, même si la comparaison peut s’arrêter dès qu’une différence est trouvée.