Rilasciato · in miglioramento
Algorithm
Gli algoritmi sulle stringhe cercano pattern nei testi e parole per prefisso; KMP, Rabin-Karp, i trie e l'algoritmo Z sono le tecniche principali.
Gli algoritmi sulle stringhe sono metodi per confrontare e cercare sequenze di caratteri in modo rapido e corretto. Il problema centrale è la ricerca di pattern: trovare tutte le posizioni in cui un pattern breve compare in un testo lungo. Ne fanno parte anche la ricerca di tutte le parole di un dizionario che iniziano con un certo prefisso e la ricerca di molti pattern contemporaneamente. L'approccio ingenuo, che controlla ogni posizione, può richiedere un tempo proporzionale al prodotto tra la lunghezza del testo e quella del pattern.
La ricerca negli editor, la ricerca nei log, il completamento automatico, il rilevamento delle intrusioni, la sincronizzazione dei file e l'analisi dei genomi si basano tutti su algoritmi sulle stringhe. KMP riutilizza i confronti già fatti tramite una tabella di fallimento e garantisce tempo lineare, Rabin-Karp fa scorrere un hash sul testo per evitare la maggior parte dei confronti, e un trie condivide i prefissi comuni, così la ricerca per prefisso dipende solo dalla lunghezza della parola. È anche un argomento frequente nei colloqui tecnici.
Conviene partire dal lessico di prefissi, suffissi e bordi e verificare a mano perché la ricerca ingenua è lenta. Poi si calcola da sé la funzione prefisso di un pattern piccolo, si implementano la ricerca KMP e un trie e si confrontano i risultati con la libreria standard. Infine vale la pena esaminare le trappole che rendono errati i risultati nella pratica, come le collisioni di hash e la normalizzazione Unicode.
Si precalcola il bordo più lungo di ogni prefisso del pattern; in caso di mancata corrispondenza si passa a un bordo più corto senza tornare indietro nel testo, con una ricerca in O(n + m).
Rabin-Karp aggiorna in O(1) l'hash di ogni finestra di lunghezza m, lo confronta con quello del pattern e verifica i caratteri solo quando gli hash coincidono.
Un albero percorso carattere per carattere; i prefissi comuni sono memorizzati una sola volta, quindi la ricerca per prefisso e il completamento automatico dipendono solo dalla lunghezza della parola.
L'array Z fornisce, per ogni posizione e in tempo lineare, il prefisso comune più lungo con l'intera stringa. Con testi reali bisogna considerare anche la normalizzazione e le unità di indice.
prefix_function calcola il bordo più lungo di ogni prefisso del pattern, e kmp_search usa questa tabella per leggere il testo una sola volta, da sinistra a destra, raccogliendo tutte le posizioni iniziali. Poiché dopo ogni corrispondenza k torna a pi[k - 1], vengono trovate anche le occorrenze sovrapposte, come quelle in 0 e 2. Eseguite python string_search.py per stampare entrambi i risultati.
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.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Algoritmi sulle stringhe.
Fai domande, condividi la tua esperienza e scambia opinioni su Algoritmi sulle stringhe.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.