Apostoliko–Đankarlov algoritam

Из Википедије, слободне енциклопедије
(преусмерено са Apostoliko–Đijankarlov 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 A., Giancarlo R., 1986, The Boyer-Moore-Galil string searching strategies revisited, SIAM Journal on Computing 15(1):98-105.
  • Crochemore, M., Lecroq, T., 1997, Tight bounds on the complexity of the Apostolico–Giancarlo algorithm, Information Processing Letters 63(4):195-203.
  • 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.