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 ${\displaystyle P}$ u tekstu ${\displaystyle T}$. Kao i kod drugih poređenja na bazi string pretrage, ovo se izvršava tako što se ${\displaystyle T}$ namesti na određeni indeks ${\displaystyle T}$ i proverava da li postoji poklapanje na tom indeksu. ${\displaystyle P}$ se onda pomera do ${\displaystyle T}$ u skladu sa pravilima Bojer-Murvog algoritma, i proces se ponavlja dok se ne dođe do kraja ${\displaystyle 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 ${\displaystyle P}$ u ${\displaystyle T}$ zahteva da se svih ${\displaystyle n}$ karaktera iz ${\displaystyle 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 ${\displaystyle O(nm)}$ gde je (math)m(/math) dužina karaktera iz ${\displaystyle T}$. Apostoliko–Đankarlov algoritam ubrzava ovo tako sto čuva broj karaktera koji se poklapaju na poravnatim mestima iz ${\displaystyle T}$ u tabelu, i to se spaja sa podacima skupljenih tokom predprocesiranja ${\displaystyle P}$ da bi se izbegla suvišna poredjenja sekvenci karaktera za koje se zna da se poklapaju.

Literatura