Апостолико–Ђанкарлов алгоритам
У рачунарству, Апостолико–Ђанкарлов алгоритам је варијанта Бојер-Муровог алгоритма за тражење стринга, чија основна примена је тражење појављивања шаблона у тексту . Као и код других поређења на бази стринг претраге, ово се извршава тако што се намести на одређени индекс и проверава да ли постоји поклапање на том индексу. се онда помера до у складу са правилима Бојер-Мурвог алгоритма, и процес се понавља док се не дође до краја . Применом Бојер-Муровог померања обично доводи до тога да се велики делови текста прескачу.
Што се тиче операција померања, Апостолико–Ђанкарлов алгоритам је потпуно једнак по фунционалности са Бојер-Муровим алгоритмом. Корисност Апостолико–Ђанкарловог алгоритма је да се убрза операција проверавања поклапања индекса на било ком индексу. Са Бојер-Муром, тражење појављивања у захтева да се свих карактера из експлицитно поклапа. За одређене шаблоне и тексове, ово је врло неефикасно - прост пример је када се и шаблон и текст састоје из истог понављања карактера, у овом случају Бојер-Муров алгоритам има сложеност где је (матх)м(/матх) дужина карактера из . Апостолико–Ђанкарлов алгоритам убрзава ово тако сто чува број карактера који се поклапају на поравнатим местима из у табелу, и то се спаја са подацима скупљених током предпроцесирања да би се избегла сувишна поредјења секвенци карактера за које се зна да се поклапају.
Литература[уреди | уреди извор]
- Apostolico A., Giancarlo R., 1986, The Boyer-Moore-Galil string searching strategies revisited, SIAM Journal on Computing. . 15 (1): 98—105. Недостаје или је празан параметар
|title=
(помоћ). - 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=
(помоћ).