Note de curs, clasele 9-10, 9 ianuarie 2014

From Algopedia
Jump to navigationJump to search

Căutări pe stringuri

Generalități

  • Σ este alfabetul datelor de intrare
  • Vom nota cu P șablonul (subșirul căutat, numit și pattern). Fie m lungimea lui.
  • Vom nota cu S șirul în care căutăm. Fie n lungimea lui.
  • lungimea unui șir x se notează cu |x|
  • 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.
  • Definiție pentru prefix (notație: ab).
  • Definiție pentru 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ă O(m)
  • complexitate O(m(n - m + 1)
  • Problema algoritmului naiv este că ignoră niște informații utile despre șăblon.
    • exemplu: dacă șablonul este abcdef, iar literele abcd s-au potrivit în shiftul curent (dar litera e nu), atunci aș putea sări următoarele trei shifturi, căci sunt garantat invalide

Există două cazuri în care algoritmul naiv se comportă bine:

  • Dacă toate literele din șablon sunt diferite, complexitatea este O(n) (de ce?).
  • Dacă șirul de intrare este aleator, notând cu d = |Σ|, complexitatea este

Algoritmul Rabin-Karp

  • generalități despre checksums, descărcări de fișiere, conflicte
  • exemplu pentru alfabetul Σ = [0-9]
  • interpretăm șablonul ca pe un număr de m cifre în baza 10
  • calculăm checksumul pentru primele m caractere din S, apoi îl translatăm în O(1)

Acest algoritm naiv are două probleme pe cazul general:

  • În baza 10, pe long long, nu ne putem descurca 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 lucra modulo un număr ales k.

  • Alegem k astfel încât kd să încapă pe un tip de date întreg.
  • Precalculăm 10m-1 mod k.
  • Când semnătura șablonului și semnătura shiftului curent sunt egale, recurgem la comparația caracter cu caracter
  • Tot O(mn) în cazul cel mai rău, dar mai bun în practică, cât timp datele de test nu sunt alese intenționat împotriva acestui algoritm.
  • Cum ar arăta un exemplu ales cu rea intenție?

Automate 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ă.
  • Exemplu: Un automat care acceptă șirurile de 0 și 1 terminate într-un număr par de 0.
  • Ce face următorul automat? (am desenat un automat cu trei stări care acceptă șiruri de cifre divizibile cu 3)

Definiția 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.

  • Revizităm exemplele de mai sus și subliniem informația despre șir.
  • Să se deseneze un automat care acceptă șiruri terminate în 01.
  • Să se deseneze un automat care acceptă șiruri care conțin subșirul 001.
  • Să se deseneze un automat care acceptă șiruri care conțin subșirul abacaba. Acest exercițiu ne arată calea spre algoritmul Knuth-Morris-Pratt.

Teme

Să se creeze DFA pentru limbajele (sper că mi le amintesc)

  • șiruri care conțin subșirul 0101
  • șiruri care nu conțin 11 nici 101
  • șiruri în care pe orice poziție impară există un 1
  • peste alfabetul unar, șiruri de forma 0k unde k este multiplu de 2 sau de 3