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 u tekstu . Kao i kod drugih poređenja na bazi string pretrage, ovo se izvršava tako što se namesti na određeni indeks i proverava da li postoji poklapanje na tom indeksu. se onda pomera do u skladu sa pravilima Bojer-Murvog algoritma, i proces se ponavlja dok se ne dođe do kraja . 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 u zahteva da se svih karaktera iz 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 gde je (math)m(/math) dužina karaktera iz . Apostoliko–Đankarlov algoritam ubrzava ovo tako sto čuva broj karaktera koji se poklapaju na poravnatim mestima iz u tabelu, i to se spaja sa podacima skupljenih tokom predprocesiranja da bi se izbegla suvišna poredjenja sekvenci karaktera za koje se zna da se poklapaju.
Literatura
- Apostolico, Alberto; Giancarlo, Raffaele (1986). „The Boyer–Moore–Galil String Searching Strategies Revisited”. SIAM Journal on Computing. 15 (1): 98—105. doi:10.1137/0215007. .
- Crochemore, M., Lecroq, T., 1997, Tight bounds on the complexity of the Apostolico–Giancarlo algorithm, Information Processing Letters. 63 (4): 195—203. Недостаје или је празан параметар
|title=
(помоћ). - 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, Software - Practice & Experience. 25 (7): 727—765. Недостаје или је празан параметар
|title=
(помоћ).