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

• (EN) Alberto Apostolico e Raffaele Giancarlo, The Boyer–Moore–Galil String Searching Strategies Revisited, in SIAM Journal on Computing, vol. 15, 1986, pp. 98–105, DOI:10.1137/0215007.
• (EN) Maxime Crochemore e Thierry Lecroq, Tight bounds on the complexity of the Apostolico-Giancarlo algorithm (PDF), in Information Processing Letters, vol. 63, n. 4, 1997, pp. 195–203, DOI:10.1016/S0020-0190(97)00107-5.
• (EN) Maxime Crochemore e Wojciech Rytter, Text Algorithms, Oxford University Press, 1994.
• (EN) Dan Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997, ISBN 0-521-58519-8.
• (FR) Thierry Lecroq, Recherches de Mots (Ph. D. Thesis), University of Orléans, 1992.
• (EN) Thierry Lecroq, Experimental results on string matching algorithms, in Software:Practice and Experience, vol. 25, n. 7, 1995, pp. 727–765, DOI:10.1002/spe.4380250703.

Voci correlate

• Algoritmo di Boyer-Moore