Proiect Analiza Algoritmilor
Deseori, datele dorite spre procesare nu se descompun logic īn īnregistrari independente cu părţi mici uşor identificabile. Acest tip de date este caracterizat numai de faptul că poate fi considerat şir: o secvenţă liniară (de obicei foarte lungă) de caractere.
Şirurile sunt evident obiectul principal al sistemelor de prelucrare de text care pun la dispoziţie o varietate de opţiuni pentru manipularea textelor. Asemenea sisteme procesează şiruri text , care pot fi definite, nu foarte riguros, drept secvenţe de litere, numere şi caractere speciale. Aceste obiecte pot fi destul de mari şi algoritmi eficienţi sunt necesari pentru manipularea lor.
Un alt tip de şir este şirul binar , o secvenţă simplă de valori 0 şi 1. Acesta este, īntr-un fel, doar un caz particular de şir text, dar merită făcută distinţia datorită faptului că anumiţi algoritmi sunt mai potriviţi şi de asemenea şirurile binare apar natural īn multe aplicaţii. De exemplu, un sistem de prelucrare grafică poate reprezenta imaginile ca şiruri binare.
Pe de o parte, şirurile text sunt esenţial diferite de şirurile binare, din moment ce sunt alcătuite din caractere dintr-un alfabet mai mare [1] . Pe de altă parte, cele două tipuri de şiruri sunt totuşi echivalente, din moment ce fiecare caracter de text se poate reprezenta, de exemplu, pe 8 biţi iar un şir binar poate fi văzut ca un şir text tratānd secvenţe de cāte 8 biţi ca pe un caracter. Mărimea alfabetului din care sunt preluate caracterele este un factor important īn proiectarea algoritmilor de procesare a şirurilor.
O operaţie fundamentală pe şiruri este potrivirea şabloanelor (modelelor): fiind dat un şir de lungime N şi un şablon de lungime M, să se găsească o apariţie a şablonului īn text. Cei mai mulţi algoritmi pentru această problemă pot fi uşor extinşi pentru a găsi toate apariţiile, din moment ce ei parcurg textul secvenţial şi pot fi reporniţi din momentul īn care s-a găsit o apariţie;
[1] Prin alfabet īnţelegem aici mulţimea simbolurilor folosite īn alcătuirea unui şir.