Apostoliko–Đijankarlov algoritam

Из Википедије, слободне енциклопедије

U računarstvu, Apostoliko–Đijankarlov 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-Murpvog 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–Đijankarlov algoritam je potpuno jednak po funcionalnosti sa Bojer-Murovim algoritmom. Korisnost Apostoliko–Đijankarlovog 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–Đijankarlov 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[уреди]

  • 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.