Back

ⓘ Apostoliko–Đankarlov algoritam




                                     

ⓘ Apostoliko–Dankarlov algoritam

U računarstvu, Apostoliko–Dankarlov algoritam je varijanta Bojer-Murovog algoritma za traženje stringa, čija osnovna primena je traženje pojavljivanja šablona P {\displaystyle P} u tekstu T {\displaystyle T}. Kao i kod drugih poredenja na bazi string pretrage, ovo se izvršava tako što se T {\displaystyle T} namesti na odredeni indeks T {\displaystyle T} i proverava da li postoji poklapanje na tom indeksu. P {\displaystyle P} se onda pomera do T {\displaystyle T} u skladu sa pravilima Bojer-Murvog algoritma, i proces se ponavlja dok se ne dode do kraja T {\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–Dankarlov algoritam je potpuno jednak po funcionalnosti sa Bojer-Murovim algoritmom. Korisnost Apostoliko–Dankarlovog algoritma je da se ubrza operacija proveravanja poklapanja indeksa na bilo kom indeksu. Sa Bojer-Murom, traženje pojavljivanja P {\displaystyle P} u T {\displaystyle T} zahteva da se svih n {\displaystyle n} karaktera iz P {\displaystyle P} eksplicitno poklapa. Za odredene š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 n m {\displaystyle Onm} gde je mathm/math dužina karaktera iz T {\displaystyle T}. Apostoliko–Dankarlov algoritam ubrzava ovo tako sto čuva broj karaktera koji se poklapaju na poravnatim mestima iz T {\displaystyle T} u tabelu, i to se spaja sa podacima skupljenih tokom predprocesiranja P {\displaystyle P} da bi se izbegla suvišna poredjenja sekvenci karaktera za koje se zna da se poklapaju.

Users also searched:

...