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 ${\displaystyle P}$ in un testo ${\displaystyle T}$. Come con altre ricerche di stringhe basate sul confronto, questo viene fatto allineando ${\displaystyle P}$ ad un certo indice di ${\displaystyle T}$ e controllando se si verifica una corrispondenza in quell'indice. ${\displaystyle P}$ viene quindi spostato rispetto a ${\displaystyle T}$ secondo le regole dell'algoritmo Boyer-Moore, e il processo si ripete fin quando la fine di ${\displaystyle 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 ${\displaystyle P}$ in ${\displaystyle T}$ richiede che tutti gli ${\displaystyle n}$ caratteri di ${\displaystyle 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 ${\displaystyle O(nm)}$, dove ${\displaystyle m}$ è la lunghezza in caratteri di ${\displaystyle T}$. Apostolico-Giancarlo lo accelera salvando il numero di caratteri abbinati agli allineamenti di ${\displaystyle T}$ in una tabella, la quale viene combinata con i dati raccolti durante la pre-elaborazione di ${\displaystyle 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

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica