Clasele 9-10 lecția 10 - 19 nov 2014

From Algopedia
Revision as of 11:00, 17 November 2014 by Cata (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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: AB).
  • Similar definim noțiunea de sufix (notație: AB)
  • 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ă ba și cb, atunci ca
  • dacă ab, atunci axbx pentru orice caracter sau șir x
  • dacă xz și yz, atunci:
    • xy dacă |x| < |y|
    • yx 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.

Temă