Algoritmo Apostolico-Giancarlo

In informatica, l'algoritmo Apostolico-Giancarlo è una variante dell'algoritmo di ricerca di stringhe di Boyer-Moore, la cui applicazione di base è la ricerca di occorrenze di un pattern $P$ in un testo $T$. Come con altre ricerche di stringhe basate sul confronto, questo viene fatto allineando $P$ ad un certo indice di $T$ e controllando se si verifica una corrispondenza in quell'indice. $P$ viene quindi spostato rispetto a $T$ secondo le regole dell'algoritmo Boyer-Moore, e il processo si ripete fin quando la fine di $T$ è stata raggiunta. L'applicazione delle regole di spostamento di Boyer-Moore spesso fa sì che grandi parti del testo vengano interamente saltate.

Per quanto riguarda l'operazione di spostamento, Apostolico-Giancarlo è equivalente come funzionalità a Boyer–Moore. L'utilità di Apostolico-Giancarlo è quella di velocizzare l'operazione di match-checking a qualsiasi indice. Con Boyer-Moore, trovare un'occorrenza di $P$ in $T$ richiede che tutti gli $n$ caratteri di $P$ corrispondano. Per alcuni pattern e testi, questo è molto inefficiente, per esempio quando sia il pattern che il testo sono costituiti dallo stesso carattere ripetuto, nel qual caso Boyer-Moore viene eseguito in $O(nm)$, dove $m$ è la lunghezza in caratteri di $T$. Apostolico-Giancarlo lo accelera salvando il numero di caratteri abbinati agli allineamenti di $T$ in una tabella, la quale viene combinata con i dati raccolti durante la pre-elaborazione di $P$ per evitare controlli di uguaglianza ridondanti per sequenze di caratteri che si sa che corrispondono. Può essere visto come una generalizzazione della regola di Galil.

Bibliografia

• Template:En Template:Cita pubblicazione
• Template:En Template:Cita pubblicazione
• Template:En Template:Cita libro
• Template:En Template:Cita libro
• Template:Fr Thierry Lecroq, Recherches de Mots (Ph. D. Thesis), University of Orléans, 1992.
• Template:En Template:Cita pubblicazione

Voci correlate

• Algoritmo di Boyer-Moore