Reprezentare succintă

În informatică , o anumită schemă de stocare se numește o reprezentare succintă a unei structuri de date, astfel încât spațiul ocupat este similar cu limita teoretică inferioară și totuși este posibil să se efectueze operațiile tipice ale structurii (sau cel puțin operațiunile de codificarea și decodificarea formei succinte) eficient.

Pentru copaci binari

Un arbore binar simplu.

Același arbore cu adăugarea nodurilor de substituent.

Cel mai clasic exemplu de reprezentare succintă este cel al copacilor binari : deoarece numărul de copaci binari diferiți cu n noduri este ${\frac {2n \choose n}{n+1}}$ ${\ displaystyle {\ frac {2n \ choose n} {n + 1}}}$ ${\ displaystyle {\ frac {2n \ choose n} {n + 1}}}$ , care crește asimptotic ca $4^{n}$ ${\ displaystyle 4 ^ {n}}$ ${\ displaystyle 4 ^ {n}}$ , limita teoretică inferioară de memorie necesară este aproximativ

\log _{2}(4^{n})=2n

{\ displaystyle \ log _ {2} (4 ^ {n}) = 2n}

{\ displaystyle \ log _ {2} (4 ^ {n}) = 2n}

biți pe arbore, adică 2 biți pe nod.

Această limită este ușor atinsă cu următoarea codificare:

în primul rând graficul este „saturat” prin adăugarea de noduri de substituent la fiecare ramură absentă (adică adăugarea unui nod de substituent la fiecare nod cu un singur copil și două noduri de substituent la fiecare frunză)
se efectuează apoi o vizită la lățimea arborelui astfel modificat și un 1 este scris într-un șir specific pentru fiecare nod adevărat și un 0 pentru fiecare substituent vizitat

De exemplu, reprezentarea succintă a arborelui din dreapta este dată de șirul:

111001000

Se întâmplă cu ușurință ^[1] că o astfel de notație produce un șir de exact $2n+1$ ${\ displaystyle 2n + 1}$ ${\ displaystyle 2n + 1}$ bit ^[2] și, prin urmare, poate fi considerat succint. Este evident că această reprezentare privește structura arborelui și nu orice date sau etichete pe care le conține nodurile graficului; acestea pot fi stocate într-o altă matrice, în ordinea în care sunt vizitate de vizită în lățime.

Acest rezultat poate fi generalizat la orice copac ^[3] .

Pentru grafice

În cazul graficelor orientate cu n vârfuri numerotate (adică presupunând că vârfurile sunt ordonate și luând în considerare „diferite” două grafice dintre care funcția care trimite i-a vârful unui grafic la i-a vârful celuilalt nu este un izomorfism), reprezentarea succintă este mult mai simplă și este dată de matricea de adiacență . Având în vedere numărul de vârfuri ale graficului, posibilele grafice direcționate numerotate sunt exact $2^{n^{2}}$ ${\ displaystyle 2 ^ {n ^ {2}}}$ ${\ displaystyle 2 ^ {n ^ {2}}}$ , adică exact atâtea câte matrice există $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ conținând doar 0 și 1.

Graficele nedirecționate numerotate sunt în schimb $2^{\frac {n*(n+1)}{2}}$ ${\ displaystyle 2 ^ {\ frac {n * (n + 1)} {2}}}$ ${\ displaystyle 2 ^ {\ frac {n * (n + 1)} {2}}}$ , iar o reprezentare succintă perfectă este dată de partea triunghiulară superioară (sau inferioară) a matricei de adiacență (matrice care va fi de fapt simetrică).

Discursul este mult mai complex în cazul graficelor nenumerotate, deoarece este destul de complicat să se stabilească când există un izomorfism între două grafice nenumerotate și, prin urmare, câte tipuri de grafice neizomorfe sunt. Cu toate acestea, se știe că numărul de biți necesari pentru a codifica un grafic nenumerotat este limitat mai jos de ${n \choose 2}-n\log n+O(n)$ ${\ displaystyle {n \ choose 2} -n \ log n + O (n)}$ ${\ displaystyle {n \ choose 2} -n \ log n + O (n)}$ și că există reprezentări eficiente (codificarea și decodarea necesită timp liniar) care ating această limită ^[4] .

Notă

^ Prin inducție asupra numărului de noduri, unde pasul inductiv constă în unirea a doi copaci ca subarburi ai unei noi rădăcini.
^ De fapt, puteți merge cu ușurință la 2n-1, eliminând ultimele două cifre, care vor fi întotdeauna 0s.
^ Note de curs despre algoritmică de prof. Univ. Lucci ^{[ link rupt ]} , p. 2
^(EN) reprezentare succintă a graficelor generale fără etichetă

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] Prin inducție asupra numărului de noduri, unde pasul inductiv constă în unirea a doi copaci ca subarburi ai unei noi rădăcini.

[2] De fapt, puteți merge cu ușurință la 2n-1, eliminând ultimele două cifre, care vor fi întotdeauna 0s.

[3] Note de curs despre algoritmică de prof. Univ. Lucci ^{[ link rupt ]} , p. 2

[4] (EN) reprezentare succintă a graficelor generale fără etichetă

[1]

[2]

[3]

[4]