Clasele 9-10 lecția 10 - 19 nov 2014
Căutări în șiruri de caractere
Căutarea unui subșir P într-un șir S înseamnă găsirea tuturor pozițiilor din S unde apare P.
Generalități
Când vorbim despre șiruri de caractere, folosim următorii termeni și notații:
- Σ este alfabetul datelor de intrare
- lungimea unui șir x se notează cu |x|
- Vom nota cu P șablonul (subșirul căutat, numit și pattern). Fie |P| = m.
- Vom nota cu S șirul în care căutăm. Fie |S| = n.
- shift (deplasare, translatare): un shift k suprapune șablonul P[0...m-1] cu bucata din șir S[k...k+m-1]
- Un shift se numește valid dacă cele două șiruri suprapuse sunt egale.
- Un șir A este prefix al lui B dacă |A| = n și A[0...n-1] = B[0...n-1] (notație: A ⊏ B).
- Similar definim noțiunea de sufix (notație: A ⊐ B)
- Cu aceste notații, formulăm problema căutării unui subșir în șir: ea constă din găsirea tuturor shifturilor valide.
Proprietăți interesante:
- tranzitivitatea: dacă b ⊐ a și c ⊐ b, atunci c ⊐ a
- dacă a ⊐ b, atunci ax ⊐ bx pentru orice caracter sau șir x
- dacă x ⊐ z și y ⊐ z, atunci:
- x ⊐ y dacă |x| < |y|
- y ⊐ x dacă |y| < |x|
- x = y dacă |x| = |y|
Algoritmul naiv
- Încercăm pe rând toate shifturile. Există n - m + 1 shifturi, iar verificarea unuia durează
- complexitate
- Problema algoritmului naiv este că ignoră niște informații utile despre șablon.
- exemplu: dacă șablonul este abcdef, iar literele abcd s-au potrivit în shiftul curent, dar litera e nu, atunci am putea sări următoarele trei shifturi, căci sunt garantat invalide
Există două cazuri în care algoritmul naiv se comportă bine:
Toate literele din șablon sunt diferite
Complexitatea este (de ce?).
Șirul de intrare este aleator
Fie |Σ| = d. Atunci fiecare comparație va eșua cu probabilitatea .
Aceasta înseamnă că, pentru fiecare deplasare, numărul așteptat de comparații nu va depăși (de ce?). Valoarea este chiar ceva mai mică, deoarece ne limităm la maxim m comparații (suma nu este infinită).
Această fracție are valoarea maximă (2) când d = 2 și tinde către 1 pe măsură ce alfabetul crește.
Algoritmul Rabin-Karp
Întâi, câteva generalități despre checksums (sume de control). Când descărcăm un fișier mare (de ordinul gigabyților), cum știm că l-am descărcat corect? Nu ne permitem să-l descărcăm de 2-3 ori și să ne asigurăm că toate copiile sunt identice. O soluție mai economică este cu un checksum. Aceasta este o funcție matematică cu următoarele proprietăți:
- trebuie să producă un rezultat relativ mic (32-64-128 de biți), oricât de mare ar fi fișierul de intrare
- trebuie să fie ușor de calculat
- preferabil, trebuie să fie greu de inversat (dându-se o valoare checksum, să fie greu de găsit un fișier care produce acea valoare)
- trebuie să fie „cât mai aproape de un generator de numere aleatoare”: două fișiere apropiate trebuie să producă valori checksum diferite.
Autorul fișierului îl uploadează împreună cu suma de control. Noi descărcăm fișierul și îi calculăm, local, suma de control, care trebui să corespundă. Altfel, știm că s-a petrecut o eroare (la descărcare sau, posibil, cineva de pe fir a încercat să substituie fișierul).
Este important să observăm că funcțiile checksum nu sunt injective. Nici nu ar avea cum, căci spațiul fișierelor este infinit, pe când spațiul sumelor de control are valori (de exemplu). Ce înseamnă aceasta? Dacă valoarea checksumului nu corespunde, știm sigur că am descărcat fișierul greșit. Dar, dacă checksumul corespunde, nu avem nicio garanție. Este posibil să fi descărcat un fișier greșit care, întâmplător, are aceeași valoare checksum (această situație se numește conflict).
Algoritmul Rabin-Karp aplică această tehnică la căutarea de șiruri. Pentru simplitate, să considerăm un exemplu pentru alfabetul cifrelor, { 0 ... 9 }. Asociem șirului P o valoare de control egală cu interpretarea zecimală a șirului P. Similar, asociem fiecărei poziții din S o valoare de control egală cu interpretarea zecimală a celor m cifre anterioare:
P | 2 | 8 | 2 | ||||||||||
S | 3 | 7 | 2 | 8 | 2 | 4 | 7 | 2 | 8 | 2 | 8 | 2 | 5 |
checksum | --- | --- | 372 | 728 | 282 | 824 | 247 | 472 | 728 | 282 | 828 | 282 | 825 |
Apoi, putem spune că P apare în S la pozițiile la care checksumul în S are valoarea (282).
De ce ne avantajează această abordare? Pentru că putem calcula un checksum din cer anterior: 728 = (372 - 300) * 10 + 8. Astfel, generarea a n - m + 1 checksumuri durează .
În cazul general al unui alfabet cu d simboluri, checksum-ul la poziția k se calculează din cel anterior cu formula:
Pentru a obține timp trebuie să precalculăm valoarea .
Acest algoritm este rapid și nu are conflicte, dar nu poate fi folosit ca atare. În baza 10, nu putem reprezenta checksumul numeric dacă |P| > 18. În alte baze (cum ar fi 26 pentru alfabetul latin) limita de lungime a lui P este și mai mică. De aceea, vom opera modulo o valoare q. În general, alegem q prim astfel încât să fie cât mai mare, dar reprezentabil pe tipul de date cu care lucrăm.
Odată cu restrângerea valorilor sumelor de control, vor apărea conflictele. Când , nu știm dacă este doar o coincidență sau chiar l-am găsit pe P în S. În această situație, recurgem la o comparare naivă.
Complexitatea este tot , dar algoritmul este mai bun în practică. Și la concurs sunt greu de găsit teste împotriva acestui algoritm, întrucât voi alegeți valoarea lui q. Cum ar arăta un exemplu ales cu rea intenție?
Automate finite
Pentru a înțelege următorul algoritm de căutare (Knuth-Morris-Pratt), avem nevoie să învățăm câte ceva despre automatele finite.
Vă recomand cu căldură cartea Introduction to the Theory of Computation de Michael Sipser pentru tot ce ține de automate, gramatici, computabilitate etc. Este o carte fascinantă, din care cel puțin primul capitol vă este accesibil.
Un automat finit determinist (DFA) este un calculator cu foarte puțină memorie, care știe să ia decizii foarte simple pe baza datelor de intrare. Exemple: liftul, alarma de la casă, cuptorul cu microunde. Să considerăm un lift (din cele mai primitive). El are câte un buton pentru fiecare etaj, un buton de apel la fiecare etaj, un senzor de ușă la fiecare etaj și un senzor de încărcare care se apasă când în lift este cineva. Liftul se comportă astfel:
- Dacă este chemat la un etaj și este gol și toate ușile sunt închise, mergi la acel etaj
- Dacă este chemat la un etaj, dar este cineva înăuntru, ignoră apelul
- Dacă este chemat la un etaj, dar una dintre ușile de la un etaj este deschisă, ignoră apelul
- etc.
Ce face următorul automat?
Dar următorul?
Definiție formală: un automat este un tuplu format din:
- Σ (alfabetul)
- Q (mulțimea de stări)
- q0 (starea inițială)
- F (mulțimea de stări finale)
- δ : Q x Σ → Q (funcția de tranziție)
Un automat acceptă un șir S = s[1] ... s[n] dacă există un șir de stări r0, r1, ..., rn cu proprietățile:
- r0 = q0
- δ(ri, s[i]) = ri + 1 pentru i = 0, ..., n - 1
- rn ∈ F
Un automat decide un limbaj dacă acceptă toate șirurile din limbaj și le respinge pe toate celelalte. Un limbaj se numește limbaj regulat dacă există un DFA care îl decide.
Care este procedura de creare a unui automat? Dându-ni-se un limbaj regulat, trebuie să înțelegem care este esența acelui limbaj și ce trebuie să memorăm despre șirul de până acum. Fiecare stare a automatului reține o astfel de informație. Primul automat de mai sus are două stări, suficiente pentru a reține paritatea ultimelor zerouri întâlnite (o cifră de 1 resetează această paritate). Al doilea automat se bazează pe faptul că un număr se divide cu trei dacă suma cifrelor lui se divide cu 3 și reține suma modulo 3 a cifrelor întâlnite până atunci.
Arta proiectării de automate pentru diverse limbaje constă tocmai în înțelegerea esenței unui limbaj
Exerciții
Să se proiecteze automate finite deterministe pentru limbajele de mai jos. Alfabetul este cel minim necesar ({ 0, 1 } sau { a, b, c } etc.).
- peste alfabetul unar, șiruri de forma 0k, unde k este multiplu de 2 sau de 3
- șiruri în care pe orice poziție impară există un 1
- șiruri care conțin un număr par de 1
- șiruri care conțin cel puțin 3 de 1
- șiruri terminate în 0
- șiruri terminate în 001
- peste alfabetul binar { 0, 1 }, șiruri care încep și se termină cu același simbol
- șiruri care nu conțin 11 nici 101
- șiruri care conțin cel puțin doi de 0 și cel mult un 1. Acest exercițiu ne învață despre operația de intersecție a limbajelor.
- automatul care acceptă orice șir în afară de 11 și 111. Acest exercițiu ne învață despre operația de complementare a limbajelor.
- șiruri care conțin subșirul 001
- șiruri care conțin subșirul 0101
- șiruri care conțin subșirul abacaba. Acest exercițiu ne arată calea spre algoritmul Knuth-Morris-Pratt.