Note de curs, clasele 11-12, 12 decembrie 2013

Sortări de stringuri

Dacă tot discutăm despre stringuri de câteva ședințe, merită să aducem vorba despre reprezentarea și sortarea stringurilor. Ca de obicei, :-) voi folosi acest exemplu ca pe un argument împotriva folosirii fără discriminare a bibliotecilor STL.

Am implementat trei versiuni de program care fac același lucru: generează 1.000.000 de șiruri de caractere, cu lungimi aleatoare între 20 și 50, conținând caractere aleatoare între 'a' și 'd'. Apoi sortează aceste șiruri de caractere.

1. Versiunea 1 reprezintă șirurile folosind STL strings și le sortează cu STL sort().
2. Versiunea 2 reprezintă șirurile folosind char* și le sortează cu STL sort(). Rutina de comparare este un wrapper peste strcmp().
3. Versiunea 3 reprezintă șirurile folosind char* și le sortează cu un quicksort ternar (detalii mai jos).

Am măsurat independent timpii de rulare pentru generarea șirurilor și am obținut, prin diferență, timpii de rulare pentru sortările în sine. Concluziile:

versiune	timp de generare	timp de sortare
STL strings + std::sort()	450 ms	1.200 ms
char* + std::sort() + strcmp	400 ms	500 ms
char* + quicksort ternar	400 ms	330 ms

Rezultatele vorbesc de la sine. În primul rând, implementarea cu char* în loc de string este de peste două ori mai rapidă. În afară de cazuri triviale, feriți-vă de string! În al doilea rând, pentru sortarea unui număr mare de șiruri, folosiți quicksort ternar. Mă voi feri să spun că este „de 1,5 ori mai rapid”, deoarece experimentul meu este incomplet (compară mere cu pere). S-ar fi cuvenit să implementez și propriul meu quicksort bazat pe strcmp().

Quicksort ternar

Ce este quicksort ternar? El încearcă să evite un mare dezavantaj al sortărilor de stringuri bazate exclusiv pe comparații. Spre deosebire de comparările de întregi, care se fac în O(1), comparările de stringuri se fac în O(|s|), unde |s| este lungimea șirurilor. Dorim deci să aflăm informații parțiale, sortând prefixe tot mai lungi ale șirurilor.

Concret, pentru a sorta n stringuri, vom alege un caracter oarecare (echivalent pivotului) și vom împărți vectorul de stringuri în 3 grupe, de la stânga la dreapta: cele al căror prim caracter este mai mic, respectiv egal, respectiv mai mare decât caracterul oarecare. Apoi vom sorta recursiv cele trei bucăți astfel:

• în prima grupă, reapelăm quicksortul ternar, alegând alt prim caracter
• la fel și în a treia grupă
• în grupa a doua, unde toate stringurile încep cu același caracter, reapelăm quicksortul ternar comparând poziția a doua a șirurilor

Observăm că quicksort-ul ternar aduce un pic a radix sort. Algoritmul a fost inventat de Sedgewick. Vezi și acest site.

Codul rezultat este:

void tsort(char **s, int lo, int hi, int pos) {
  if (lo >= hi) {
    return;
  }

  int curr = lo, left = lo, right = hi;
  char mid = (s[lo][pos] + s[hi][pos]) / 2;
  char *tmp;

  // invariant: la fiecare moment,
  // * s[lo ... left - 1] conține elemente unde al pos-lea caracter este mai mic decât mid
  // * s[left ... curr - 1] conține elemente unde al pos-lea caracter este egal cu mid
  // * s[curr] este șirul curent, din care evaluăm al pos-lea caracter
  // * s[curr + 1 ... right] conține elemente încă neevaluate
  // * s[right + 1 ... hi] conține elemente unde al pos-lea caracter este mai mare decât mid
  while (curr <= right) {
    char c = s[curr][pos];
    if (c < mid) {
      tmp = s[curr];
      s[curr] = s[left];
      s[left] = tmp;
      left++;
      curr++;
    } else if (c > mid)  {
      tmp = s[curr];
      s[curr] = s[right];
      s[right] = tmp;
      right--;
    }  else {
      curr++;
    }
  }

  tsort(s, lo, left - 1, pos);
  if (s[left][pos] != '\0' ) {
    tsort(s, left, right, pos + 1);
  }
  tsort(s, right + 1, hi, pos);
}

int main(void) {
  char* s[n];
  ...
  tsort(s, 0, N - 1, 0);
  ...
}

Șiruri de sufixe

Am văzut în ultima lecție că arborii de sufixe sunt o structură utilă în multe probleme cu șiruri de caractere. Arborii de sufixe se pot construi în O(n) cu un algoritm greoi. Algoritmii mai simpli necesită timp O(n²) sau chiar O(n³).

Șirurile de sufixe oferă răspunsuri la aceleași tipuri de întrebări ca și arborii de sufixe, dar sunt mai ușor de implementat. Construcția lor în O(n) este încă greoaie, dar o construcție în O(n) este mult mai la îndemână.

Definiție

Un șir de sufixe este un șir ordonat al tuturor sufixelor unui șir. De exemplu, pentru S = "abracadabra", șirul de sufixe este

A = { "a", "abra", "abracadabra", "acadabra", "adabra", "bra", "bracadabra", "cadabra", "dabra", "ra", "racadabra" }

În practică, nu avem nevoie să stocăm explicit sufixele, căci aceasta necesită memorie O(n²). Întrucât știm că sunt sufixe, avem nevoie să stocăm doar poziția de început în S:

A = { 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 }

Construcție în O(n log n)

Metoda folosită se numește dublarea prefixului. Pornim cu ordinea caracterelor individuale din șir. Din ea, calculăm ordinea prefixelor de lungime 2 ale fiecărui sufix, apoi a celor de lungime 4 etc. Avem nevoie de log n iterații, iar fiecare iterație poate fi completată în O(n).

(exemplu pentru "abracadabra" aici)

Observații:

• Pentru construcția rapidă, nu este necesar să sortăm caracterele prima oară. Putem să le atribuim valorile P[0][i] = S[i] - 'a'
• Matricea intermediară de dimensiuni log n x n poate sau nu să fie necesară, în funcție de natura problemei.
• La sfârșitul construcției, vectorul de pe ultima linie a matricei este indirectarea vectorului de sufixe. Pozițiile elementelor 0, 1, ..., n-1 în acel șir dau vectorul de sufixe
  • Exemplu: pentru "abracadabra", ultima linie a matricei este { 2, 6, 10, 3, 7, 4, 8, 1, 5, 9, 0 }.
• La fiecare pas, informația despre prefixe de lungime 2^k trebuie sortată. Articolul infoarena spune că sort() se comportă mai bine decât radix sort. Ar fi interesant dacă cineva poate să testeze aceasta.

Construcție în O(n), metoda recursivă

Vezi articolul de la infoarena și o prezentare.

(exemplu pentru "abracadabra")

Complexitatea este T(n) = T(2n/3) + n, așadar T(n) = O(n).

Observații:

• de ce alegem grupe de 3 caractere și nu de două?

Cele mai lungi prefixe comune

În general, ne ajută dacă putem răspunde la întrebări de forma „care este cel mai lung prefix comun între sufixul care începe la poziția i și sufixul care începe la poziția j?” Vom nota răspunsul la această întrebare cu LCP(i, j).

LCP(i, j) poate fi calculat în timp O(log n) din matricea P. La fiecare pas k, dacă P[k][i] == P[k][j], atunci prefixul comun are lungime cel puțin 2^k, la care adăugăm LCP(i + 2^k, j + 2^k). În orice caz, trecem la pasul k - 1.

Dacă dorim să reducem timpul la O(1), trebuie să calculăm și să stocăm L[i] = LCP(i -1, i) pentru fiecare i. Apoi, LCP(i, j) = min(L[i], L[i + 1], ..., L[j]). Calculăm acest minim în O(1) cu RMQ (greu de implementat în timp de concurs).

Cum calculăm vectorul L? Algoritmul este simplu și rulează în O(n) odată ce avem vectorul A și inversul său A^-1, dar pornește de la o propoziție neintuitivă.

Să examinăm din nou șirul de sufixe pentru stringul "abracadabra":

A = { "a", "abra", "abracadabra", "acadabra", "adabra", "bra", "bracadabra", "cadabra", "dabra", "ra", "racadabra" }

sau, numeric,

A = { 10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2 }

Fie A^-1 vectorul invers al lui A (sau, echivalent, ultima linie din matricea P). Așadar, A^-1 indică, pentru fiecare sufix S[i...n-1], poziția lui în A:

A^-1 = { 2, 6, 10, 3, 7, 4, 8, 1, 5, 9, 0 }

vectorul L rezultat (cel mai lung prefix comun între fiecare sufix și predecesorul lui) va fi:

L = { 0, 1, 4, 1, 1, 0, 3, 0, 0, 0, 2 }

Propoziție: pentru orice i > 0, L[A^-1[i + 1]] ≥ L[A^-1[i]] - 1

Demonstrație: Pentru sufixul S[i...n-1], să considerăm sufixul imediat anterior lexicografic, S[j...n-1]. Fie l = L[A^-1[i]] = LCP(i, j). Dacă l = 0, atunci propoziția este evident adevărată. Dacă l > 0, atunci S[j] = S[i], T[j+1...n-1] < T[i+1...n-1] și LCP(i + 1, j + 1) = l - 1.

Acum, fie S[k...n-1] sufixul imediat anterior lexicografic al lui S[i+1...n-1]. Atunci fie k = j + 1, fie S[j+1...n-1] < S[k...n-1] < S[i+1...n-1]. De aceea,

L[A^-1[i + 1]] = LCP(i+1, k) ≥ LCP(i + 1, j + 1) = l - 1.

Exemplu: Fie i = 2. Atunci:

• S[2...10] = "racadabra"
• A^-1[2] = 10 ("racadabra" este al 10-lea sufix lexicografic, ultimul)
• j = 9 (S[9...10] = "ra" este sufixul lexicografic anterior lui "racadabra")
• l = L[A^-1[2]] = L[10] = 2 ("racadabra" are două litere în comun cu sufixul anterior, "ra")
• trebuie să verificăm că L[A^-1[3]] ≥ 1
• S[2] = S[9] = "r"
• S[10...10] < S[3...10] ("acadabra" < "a" prin eliminarea lui "r")
• LCP("acadabra", "a") = l - 1 = 1
• k = 0 ("abracadabra" este sufixul lexicografic anterior lui S[i+1...n-1])
• deci avem ordinea S[10...10] < S[0...10] < S[3...10] ("a" < "abracadabra" < "acadabra")
• de aceea, L[A^-1[3]] = LCP("acadabra", "abracadabra") ≥ LCP("acadabra", "a") = 1

Pseudocodul este:

l = 0
for i = 0 to n − 1
  k = A<sup>-1</sup>[i]
  j = A[k − 1]
  while (T[i + l] = T[j + l])
    l = l + 1
  L[k] = l
  if (l > 0)
    l = l - 1

Aplicații

Vom căuta soluții pentru aceste aplicații atât cu arbori de sufixe, cât și cu șiruri de sufixe.

Căutare de subșir în șir

Se face printr-o căutare binară în A. Observăm că arborele de sufixe funcționează într-o manieră complementară algoritmului KMP. Acesta din urmă preprocesează subșirul, apoi poate căuta rapid oricâte șiruri. Vectorul de sufixe necesită o preprocesare a șirului, după care poate căuta rapid oricâte subșiruri.

Numărul de apariții ale unui subșir în șir

Se face prin două căutări binare. Pentru găsirea subșirului "abc", trebuie să găsim prima și ultima apariție a lui "abc" ca prefix în șirul de sufixe. Putem face aceasta cu două căutări binare care diferă ușor. Mai simplu, putem folosi o singură rutină pentru a căuta șirurile "abc" și "abd".

Costul fiecărei căutări binare, dacă o implementăm naiv, este O(P log n), unde P este subșirul căutat. Ea poate fi redusă la O(P + log n) dacă putem răspunde la LCP(i, j) în timp O(1) (vezi mai jos). Iată o explicație digerabilă.

Cel mai lung subșir care apare de cel puțin K ori

După calculul șirului de sufixe și al celor mai lungi prefixe între fiecare două prefixe consecutive, calculăm minimul din LCP pentru fiecare subsecvență de K elemente.

Rotația minimă dpdv lexicografic

Se rezolvă prin concatenarea șirului cu el însuși și construirea șirului de sufixe pentru șirul de lungime 2n.

Al k-lea sufix în ordine lexicografică

Banal, este A[k].

Numărul de subsecvențe distincte ale unui șir

Să ne închipuim subsecvențele grupate după poziția de început. Există n subsecvențe care încep la poziția 0, n - 1 subsecvențe care încep la poziția 1 etc. Acum, să examinăm aceste poziții de început în ordinea lexicografică a perechilor. Pentru poziția A[i], am contabilizat deja o parte din perechi. Câte? Numărul lor este dat de lungimea celui mai lung prefix comun între sufixele (i-1) și i.

De exemplu, pentru șirul "xabyabz", A = { abyabz, abz, byabz, bz, xabyabz, yabz, z }.

Câte subsecvențe noi încep la primul "a"? Momentan toate 6: "a", "ab", "aby", "abya", "abyab", "abyabz".

Câte subsecvențe noi încep la cel de-al doilea "a"? Doar una: "abz", deoarece pe "a" și pe "ab" le-am contabilizat la pasul anterior.

Deci la fiecare pas i adăugăm la răspuns valoarea n - A[i] - LCP[i, i-1], unde A[i] este șirul (numeric) de sufixe ordonate.