Apostoliko–Đankarlov algoritam

U računarstvu, Apostoliko–Đankarlov algoritam je varijanta Bojer-Murovog algoritma za traženje stringa, čija osnovna primena je traženje pojavljivanja šablona $P$ u tekstu $T$. Kao i kod drugih poređenja na bazi string pretrage, ovo se izvršava tako što se $T$ namesti na određeni indeks $T$ i proverava da li postoji poklapanje na tom indeksu. $P$ se onda pomera do $T$ u skladu sa pravilima Bojer-Murvog algoritma, i proces se ponavlja dok se ne dođe do kraja $T$. Primenom Bojer-Murovog pomeranja obično dovodi do toga da se veliki delovi teksta preskaču.

Što se tiče operacija pomeranja, Apostoliko–Đankarlov algoritam je potpuno jednak po funcionalnosti sa Bojer-Murovim algoritmom. Korisnost Apostoliko–Đankarlovog algoritma je da se ubrza operacija proveravanja poklapanja indeksa na bilo kom indeksu. Sa Bojer-Murom, traženje pojavljivanja $P$ u $T$ zahteva da se svih $n$ karaktera iz $P$ eksplicitno poklapa. Za određene šablone i teksove, ovo je vrlo neefikasno - prost primer je kada se i šablon i tekst sastoje iz istog ponavljanja karaktera, u ovom slučaju Bojer-Murov algoritam ima složenost $O(nm)$ gde je (math)m(/math) dužina karaktera iz $T$. Apostoliko–Đankarlov algoritam ubrzava ovo tako sto čuva broj karaktera koji se poklapaju na poravnatim mestima iz $T$ u tabelu, i to se spaja sa podacima skupljenih tokom predprocesiranja $P$ da bi se izbegla suvišna poredjenja sekvenci karaktera za koje se zna da se poklapaju.

Literatura

Шаблон:Литература-{

• Шаблон:Cite journal.
• Crochemore, M., Lecroq, T., 1997, Tight bounds on the complexity of the Apostolico–Giancarlo algorithm, Шаблон:Cite journal.
• Crochemore, M., Wojciech Rytter, 1994, Text Algorithms, Oxford University Press.
• Gusfield, D., 1997, Algorithms on strings, trees, and sequences: Computer Science and Computational Biology, Cambridge University Press.
• Lecroq, T., 1992, Recherches de mot, Ph. D. Thesis, University of Orléans, France.
• Lecroq, T., 1995, Experimental results on string matching algorithms, Шаблон:Cite journal.

}-Шаблон:Литература крај