Увод¶
Алгоритми текста су још једна значајна област рачунарства, како у теорији, тако и у пракси (примени). Велики део примене рачунарства се бави различитим врстама обраде текста. Као најпознатији и сасвим једноставан пример обраде текста поменимо тражење одређене секвенце карактера у датом тексту.
Mогућност претраге текста смо вероватно сви већ користили у разним програмима за уређивање и/или обраду текста (едитори, текст процесори), прегледачима веба и разним другим програмима (нпр. окружења за развој софтвера).
Свеприсутност могућности претраге текста у разним апликацијама оставља утисак да је у питању веома једноставан задатак. Утисак је утолико јачи што скоро свако ко зна бар мало програмирања има идеју како може да се напише функција која проналази позицију тражене секвенце у тексту (а то је поређењем сваког карактера тражене секвенце са сваким карактером текста у двострукој петљи). Међутим, многи који ово умеју нису ни свесни да постоје и знатно ефикаснија решења, која није било лако смислити. На срећу, та ефикаснија решења овог и сличних проблема су уграђена у готове функције, које су део стандардне библиотеке у већини савремених програмских језика.
Није неопходно да као програмери знамо детаље алгоритама библиотечких функција за рад са стринговима, као што ни возачи не морају да знају како тачно раде њихови аутомобили. Ипак, што више знамо о тим функцијама, бићемо у стању да их адекватније користимо (а исто важи и за аутомобил). На пример:
Најмање што треба да знамо је да су библиотечка решења по правилу ефикаснија (а често и поузданија) од оних која сами напишемо. Према томе, што боље познајемо функције које постоје у библиотеци и начин њихове употребе, бићемо у стању да пишемо краће, јасније, брже и поузданије програме.
Када знамо и временску сложеност функција из библиотеке, или имамо добру представу о тој сложености, јасније нам је у каквом случају можемо да изгубимо перформансе због непримерене употребе.
У случају да нам је позната и идеја алгоритма, можемо да је искористимо када решавамо сличне проблеме, за које нема одговарајућих готових функција.
Због свега тога, прва целина у овом поглављу је управо преглед неких често коришћених функција за обраду текста (стрингова), уз илустрације неких типичних примена. На крају ове целине говори се и о томе када употреба библиотечких функција може да доведе до неефикасних решења и како их у таквим случајевима треба користити.
Друга целина се бави регуларним изразима, захваљујући којима обрада текста постаје још моћнија, а при томе једнако удобна. Између осталог, регуларни изрази нам омогућавају да у тексту на ефикасан начин истовремено тражимо разне међусобно сличне секвенце, тако што уместо самих секвенци задамо њихов прецизан, заједнички опис.
Трећа целина објашњава једну технику анализе текста, која се назива рекурзивни спуст. Ова техника је погодна нпр. за израчунавање вредности израза задатог текстом, али и за сложеније задатке, као што је почетна фаза превођења програма написаног на неком вишем програмском језику у машински језик (синтаксна анализа, парсирање, односно токенизација).
У петом поглављу, Одабрани алгоритми и структуре података, детаљније је објашњено неколико напредних (ефикасних), а веома важних и често коришћених алгоритама за обраду текста, као што су претраживање текста и замена једне секвенце у тексту другом секвенцом.