Clasele 9-10 lecția 11 - 26 nov 2014

From Algopedia
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Căutări în șiruri de caractere, partea a doua

Recapitulare: exemple de automate finite

Reluăm trei exemple din lecția trecute care au legătură cu căutarea. Proiectați automate care acceptă:

  • șiruri care conțin 001
  • șiruri care conțin 0101
  • șiruri care conțin abacaba

Căutări de șiruri folosind automate finite

De ce sunt bune automatele la căutare? Pentru că, odată calculată funcția de tranziție, căutarea decurge în mod banal în O(1) per caracter citit:

  • Citim caracterul și schimbăm starea curentă.
  • De câte ori automatul este în starea finală (de acceptare), înseamnă că am găsit o apariție a lui P în S.

Să vedem cum putem calcula în mod programatic funcția de tranziție. Observăm că putem stoca această funcție foarte convenabil într-o matrice cu m + 1 linii și |Σ| coloane. Fiecare săgeată în desenul automatului este o valoare în această matrice: săgeata din starea q în starea r pe caracterul a înseamnă că δ(q, a) = r. Așadar, cum calculăm δ(q, a)?

Să pornim de la automatul finit determinist care recunoaște șirurile care conțin subșirul abacaba. Observăm că tranzițiile (atât cele înainte, cât și cele înapoi) au forma

δ(q, a) = r, unde r este starea maximă pentru care Pr ⊐ Pqa

Putem generaliza această observație într-un algoritm de construire a DFA pentru orice pattern P, astfel:

  • Definim funcția de sufix: Pentru un pattern P fixat, σ(x) = max {k | Pkx}
    • σ(x) este minim 0 și maxim m când Px
  • Construim automatul folosind funcția de tranziție: δ(q, a) = σ(Pqa).

Hai să arătăm că automatul definit mai sus se comportă corect. Ideea demonstrației este să arătăm că automatul este în starea σ(Si) ori de câte ori ultimele i caractere citite corespund cu primele i caractere din S. Atunci automatul va fi în starea m (de acceptare) ori de câte ori găsește șablonul P (și numai atunci). Demonstrația riguroasă se face în trei pași.

Săgețile automatului merg cel mult cu un pas spre dreapta

(Încă nu am făcut legătura între σ și stările automatului, dar ne pregătim pentru asta)

Propoziție: Pentru orice șir x și orice caracter a, σ(xa) ≤ σ(x) + 1

Demonstrație: fie r = σ(xa). Atunci Pr ⊐ xa, deci Pr-1 ⊐ x, deci r - 1 ≤ σ(x).

Starea automatului nu depinde de tot șirul S, ci doar de ultimele caractere relevante

Propoziție: Pentru orice șir x și orice caracter a, dacă q = σ(x), atunci σ(xa) = σ(Pqa)

Demonstrație: grafică, cu șirurile xa, Pqa și Pr.

Rezultă că automatul nu are nevoie de multă memorie. El trebuie să rețină doar câte caractere (cele mai recente) sunt prefix al lui P.

După citirea primelor i caractere din S, automatul este în starea σ(Si)

Propoziție: Fie Φ(Si) starea automatului după citirea a i caractere din S"'. Atunci Φ(Si) = σ(Si).

Demonstrație: prin inducție după i.


Cum construim automatul? Mergând după definiție, pentru fiecare q = 0, 1, ..., m și pentru fiecare aΣ, trebuie să calculăm cel mai lung prefix al lui P care este sufix al lui Pqa. Implementarea naivă rulează în O(m3 |Σ|).

Există o metodă de a reduce această complexitate la O(m |Σ|), despre care vom vorbi după algoritmul KMP. Ea ne oferă, așadar un timp total de O(m |Σ| + n) pentru preprocesare + căutare. Deoarece algoritmul KMP este O(n), el este net superior, iar metoda cu DFA prezintă un interes pur teoretic.

Algoritmul Knuth-Morris-Pratt (KMP)

Algoritmul KMP pornește de la teoria automatelor finite, dar îmbunătățește mult algoritmul de căutare cu DFA. El ignoră funcția de tranziție δ, ceea ce înseamnă că nu mai depinde de mărimea alfabetului, |Σ|.

Care este scopul căutărilor cu automate? Este să evite să verifice shift-uri (deplasări) care sunt garantat invalide. Dacă automatul este în starea q, iar următorul caracter nu se potrivește, automatul va trece în starea maximă posibilă k unde ultimele k caractere citite se potrivesc. Toate stările între k și q corespund, în mod necesar, unor deplasări invalide, din modalitatea de construire a automatului.

De aceea, ne este util să răspundem la întrebarea: dacă primele q caractere din P se potrivesc la deplasarea curentă (fie ea i), care este următoarea deplasare j pe care are rost să o încercăm? Desigur, numărul de caractere potrivite la poziția j respectă relația i + q = j + k. Dorim deci să minimizăm valoarea j sau, echivalent, să maximizăm valoarea k. În mod natural, Pk ⊏ Pq. Dorim și ca Pk ⊐ Pq.

Definim funcția de prefix, π astfel: π[q] = max{k | k < q și PkPq }

În cuvinte, π[q] este lungimea cel mai lung prefix care este și sufix al lui Pq.

Din nou, algoritmul naiv de construcție al lui π este O(m3). Totuși, algoritmul KMP construiește π în O(n):

  function preprocesare(P) {
    π[0] = 0;
    k = 0;
    for (q = 1; q < m; q++) {
      while ((k > 0) && (P[k] != P[q])) {
        k = π[k - 1];
      }
      if (P[k] == P[q]) {
        k++;
      }
      π[q] = k;
    }
  }

Se demonstrează ușor că complexitatea totală a algoritmului este O(m): k este incrementat de cel mult m ori, deci și numărul de decrementări este O(m).

Algoritmul de căutare este:

  function KMP(S, P) {
    q = 0; // starea curentă
    for (i = 0; i < n; i++) {
      while ((q > 0) && (P[q] != S[i])) {
        q = π[q - 1];
      }
      if (P[q] == S[i]) {
        q++;
      }
      if (q == m) {
        print "Am găsit P în S la poziția ''i''" // i este poziția de final
      }
    }
  }

Ca fapt divers, putem folosi vectorul π pentru a calcula matricea de tranziție în O(m |Σ|) pentru algoritmul de căutare cu DFA. Linia q din matrice se obține copiind linia π[q], mai puțin δ(q, P[q]) = q + 1.

Aplicații ale algoritmului KMP

  • Să se determine dacă un șir este permutare circulară a altui șir
  • Discuție liberă: să se găsească rotația circulară minimă dpdv lexicografic a unui șir
  • Problema Source de la RMI (căutare de șiruri cu substituire bijectivă)
  • probleme Campion
  • probleme Infoarena

Automate finite, încheiere

Automatele finite deterministe nu sunt o unealtă atotputernică. Ele pot decide anumite limbaje, dar nu pe toate. Iată cum putem demonstra această limitare.

Limbaje neregulate

Nu toate limbajele sunt regulate. Cu alte cuvinte, unele limbaje nu pot fi decise de niciun DFA. Să considerăm, de exemplu, limbajul șirurilor de forma 0n1n. Intuitiv, ce ar trebui să rețină un automat despre șirul citit până atunci? Ar trebui să rețină cel puțin numărul de zerouri văzute. Dar, pentru a stoca numărul n, este nevoie de O(log n) biți, iar n poate fi arbitrar de mare. Din această cauză, și numărul de stări ale automatului va fi arbitrar de mare, ceea ce contrazice condiția de finitudine a automatului.

Intuiția noastră despre care limbaje sunt sau nu regulate ne poate păcăli. De exemplu:

  • L = { w | w palindrom } este neregulat
  • L = { w | w are un număr egal de 0 și 1 } este neregulat
  • Dar L = { w | w are un număr egal de 01 și 10 } este regulat! (de ce?)

Pentru a facilita depistarea limbajelor neregulate, prezentăm lema de pompare.

Lema de pompare pentru limbaje regulate

Lema de pompare prezintă o proprietate comună tuturor limbajelor regulate. Dacă putem demonstra că un limbaj nu are această proprietate, atunci el nu este regulat (și deci nu poate fi decis de niciun DFA).

Lema de pompare: Dacă A este un limbaj regulat, atunci există un număr p (numit lungime de pompare) astfel încât, pentru orice șir sA de lungime cel puțin p, atunci s poate fi împărțit în trei bucăți, s = xyz, care respectă condițiile:

  1. Pentru orice i≥ 0, xyizA
  2. |y| > 0
  3. |xy| ≤ p

Demonstrație (neriguroasă): fie M un DFA care decide limbajul A. Atunci alegem p ca fiind numărul de stări al lui M. Orice șir din A indică o cale de la starea inițială la o stare finală. Pentru șirurile care au lungime cel puțin p, calea trece prin cel puțin p + 1 stări, deci există o stare repetată. Definim x, y și z ca fiind bucata din șir dinaintea stării repetate, dintre prima și ultima apariție a stării repetate, respectiv de după ultima apariție a stării repetate.

Acum putem demonstra că limbajul L = { 0n1n | n ≥ 0 } nu este regulat. Fie p lungimea de pompare. Alegem s = 0p1p. Atunci s nu poate fi pompat, deoarece, oricum am alege s = xyz, șirul s′ = xyyz nu va avea un număr egal de 0 și de 1.

Exemple: Să demonstrăm împreună că următoarele limbaje sunt neregulate:

  • L = { w | w are un număr egal de 0 și 1 }. Hint: aici avem nevoie și de condiția 3 a lemei de pompare.
  • L = { w | w palindrom }. Hint: alegem s = 0p10p.
  • L = { ww | w ∈ {0, 1}* }. Hint: alegem s = 0p10p1.
  • L = { 1n2 | n ≥ 0 }. Hint: șirul pătratelor perfecte nu conține progresii aritmetice infinite.
  • L = { 0i1j | i ≥ j }. Hint: aici pompăm în jos (din prima condiție de pompare folosim cazul i = 0).

Temă