Rappresentazione succinta

In informatica, si chiama rappresentazione succinta di una struttura di dati un particolare schema di memorizzazione della stessa tale che lo spazio occupato sia simile al limite inferiore teorico e ciononostante sia possibile effettuare le operazioni tipiche della struttura (o perlomeno le operazioni di codifica e decodifica della forma succinta) in modo efficiente.

Per alberi binari

Un semplice albero binario.

Lo stesso albero con l'aggiunta dei nodi segnaposto.

L'esempio più classico di rappresentazione succinta è quello degli alberi binari: siccome il numero di alberi binari diversi con n nodi è ${\frac {2n \choose n}{n+1}}$, che asintoticamente cresce come $4^{n}$, il limite inferiore teorico di memoria richiesta è circa

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

bit per albero, ovvero 2 bit per nodo.

Questo limite si raggiunge facilmente con la seguente codifica:

1. prima di tutto si "satura" il grafo aggiungendo dei nodi segnaposto ad ogni ramificazione assente (ovvero aggiungendo un nodo segnaposto ad ogni nodo con un solo figlio e due nodi segnaposto ad ogni foglia)
2. si effettua quindi una visita in ampiezza dell'albero così modificato e si scrive in un'apposita stringa un 1 per ogni nodo vero ed uno 0 per ogni segnaposto visitati

Ad esempio, la rappresentazione succinta dell'albero a destra è data dalla stringa:

111001000

Si verifica facilmente che una tale notazione produce una stringa di esattamente $2n+1$ bit, e si può quindi considerare succinta. È evidente che questa rappresentazione riguarda la struttura dell'albero e non eventuali dati o etichette che i nodi del grafo contiene; questi possono essere memorizzati in un altro array, nell'ordine in cui vengono visitati dalla visita in ampiezza.

Questo risultato si può generalizzare ad alberi qualsiasi.

Per grafi

Nel caso dei grafi orientati con n vertici numerati (ovvero supponendo che i vertici siano ordinati e considerando "diversi" due grafi tra i quali la funzione che manda il vertice i-esimo di un grafo nel vertice i-esimo dell'altro non è un isomorfismo), la rappresentazione succinta è molto più semplice, ed è data dalla matrice delle adiacenze. Posto n il numero dei vertici del grafo, i possibili grafi orientati numerati sono esattamente $2^{n^{2}}$, ovvero esattamente tanti quante sono le matrici $n\times n$ contenenti solo 0 e 1.

I grafi non orientati numerati sono invece $2^{\frac {n*(n+1)}{2}}$, e una rappresentazione succinta perfetta è data dalla parte triangolare superiore (o inferiore) della matrice di adiacenza (matrice che sarà infatti simmetrica).

Il discorso è nettamente più complesso nel caso dei grafi non numerati, dato che è piuttosto complicato stabilire quando esiste un isomorfismo tra due grafi non numerati, e quindi quanti sono i tipi di grafi non isomorfi. Tuttavia si sa che il numero di bit necessari per codificare un grafo non numerato è limitato inferiormente da ${n \choose 2}-n\log n+O(n)$ e che esistono rappresentazioni efficienti (codifica e decodifica richiedono tempo lineari) che raggiungono questo limite.