Publié · en amélioration
Algorithm
Les algorithmes sur les chaînes recherchent des motifs dans un texte et des mots par préfixe ; KMP, Rabin-Karp, les tries et l'algorithme Z en sont la base.
Les algorithmes sur les chaînes de caractères servent à comparer et à rechercher des suites de caractères rapidement et correctement. Le problème central est la recherche de motif : trouver toutes les positions où un motif court apparaît dans un long texte. La recherche de tous les mots d'un dictionnaire commençant par un préfixe donné et la recherche simultanée de nombreux motifs en font aussi partie. L'approche naïve, qui teste chaque position, peut prendre un temps proportionnel au produit de la longueur du texte et de celle du motif.
La recherche dans un éditeur, la recherche dans les journaux, l'autocomplétion, la détection d'intrusion, la synchronisation de fichiers et l'analyse de génomes reposent toutes sur ces algorithmes. KMP réutilise les comparaisons déjà faites grâce à une table d'échec et garantit un temps linéaire, Rabin-Karp fait glisser un hachage roulant sur le texte pour éviter la plupart des comparaisons, et un trie partage les préfixes communs, si bien qu'une recherche par préfixe ne dépend que de la longueur du mot. Le sujet revient souvent en entretien technique.
Commencez par le vocabulaire des préfixes, suffixes et bords, et vérifiez à la main pourquoi la recherche naïve est lente. Calculez ensuite vous-même la fonction préfixe d'un petit motif, implémentez la recherche KMP et un trie, puis comparez les résultats avec la bibliothèque standard. Pour finir, examinez les pièges qui faussent les résultats en pratique, comme les collisions de hachage et la normalisation Unicode.
On précalcule le plus long bord de chaque préfixe du motif ; en cas de différence, on passe à un bord plus court sans revenir en arrière dans le texte, pour une recherche en O(n + m).
Rabin-Karp met à jour en O(1) le hachage de chaque fenêtre de longueur m, le compare à celui du motif et ne vérifie les caractères que lorsque les hachages sont égaux.
Un arbre parcouru caractère par caractère ; les préfixes communs ne sont stockés qu'une fois, donc la recherche par préfixe et l'autocomplétion ne dépendent que de la longueur du mot.
Le tableau Z donne, pour chaque position et en temps linéaire, le plus long préfixe commun avec la chaîne entière. Sur du texte réel, il faut aussi tenir compte de la normalisation et des unités d'indexation.
prefix_function calcule le plus long bord de chaque préfixe du motif, et kmp_search s'appuie sur cette table pour lire le texte une seule fois, de gauche à droite, en relevant toutes les positions de départ. Comme k repasse à pi[k - 1] après chaque occurrence, les occurrences qui se chevauchent, comme en 0 et 2, sont aussi trouvées. Lancez python string_search.py pour afficher les deux résultats.
string_search.py
def prefix_function(p: str) -> list[int]:
"""pi[i] = length of the longest proper border of p[:i + 1]."""
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text: str, pattern: str) -> list[int]:
"""Start positions of every (possibly overlapping) occurrence."""
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
hits, k = [], 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = pi[k - 1]
return hits
if __name__ == "__main__":
print(prefix_function("ababaca")) # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("abababcabab", "abab")) # [0, 2, 7]
python string_search.pySix chapitres pour aller de l'installation aux notions essentielles de Algorithmes sur les chaînes.
Posez vos questions, partagez votre expérience et échangez vos avis sur Algorithmes sur les chaînes.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.