Diamo un'occhiata all'approccio banale, che in molti casi può essere ottimale:
Memorizzerebbe:
- Il numero di elementi nell'intervallo (con 31 bit, poiché le liste in Java sono limitate a 2-31 - 1 elementi).
- Seguito da 1 bit per ogni indice, che indica se l'elemento è presente nel set o meno.
Questa è l'implementazione che la prima versione del compressore di immagine frattale aveva, per memorizzare i dati dalle scissioni e fusioni delle triangolazioni.
Sebbene non fosse ottimale, dal momento che man mano che le iterazioni delle divisioni progredivano, il numero di elementi da memorizzare diminuiva, diventando una percentuale molto piccola del totale, nel qual caso la codifica banale può essere sostanzialmente migliorata.
Ora l'obiettivo è quello di migliorare quella codifica banale, per vedere se si può ottenere una codifica più compressa in termini di numero di bit utilizzati.
Primo approccio : Quando il numero di elementi nell'insieme è molto più piccolo della dimensione dell'intervallo, possiamo considerare la memorizzazione degli indici presenti.
In questo caso, l'utilizzo sarebbe:
- 31 bit per il numero di elementi nell'intervallo.
- 31 bit per il numero di elementi presenti nel set.
- 31 bit * il numero di elementi presenti nel set.
Secondo approccio . Miglioriamo il numero di bit per elemento memorizzato:
- 31 bit per il numero di elementi nell'intervallo. Il numero di bit dell'elemento più grande nell'intervallo ( numBitsElem ) sarebbe stato calcolato.
- 5 bit da conservare numBitsElem .Quindi, se il numero di elementi nell'intervallo fosse 1023, un 10 verrebbe memorizzato in questi 5 bit.
- numBitsElem bit, per memorizzare il numero di elementi nel Set.
- numBitsElem bit * il numero di elementi presenti nel set.
Beh, a poco a poco ci stiamo avvicinando a una codifica migliore...
Terza approssimazione Ci rendiamo conto che se ordiniamo l'insieme in ordine crescente, i delta (differenze tra elementi consecutivi) possono probabilmente essere codificati con meno bit di un elemento assoluto dell'intervallo:
- 31 bit per il numero di elementi nell'intervallo.
- Calcoliamo il più piccolo numBitsElem per codificare un elemento.Calcoliamo anche l'elenco dei delta (elenco delle differenze tra gli elementi consecutivi dell'elenco ordinato degli elementi nel set).Infine, calcoliamo anche numBitsDelta
- 5 bit da conservare numBitsElem .
- 5 bit da conservare numBitsDelta .
- numBitsElem bit, per memorizzare il numero di elementi nel Set.
- numBitsDelta bit * il numero di elementi nell'insieme.
Beh, sembra che stiamo già raggiungendo la codifica ottimale, giusto?
Continuiamo...
Quarta approssimazione . Ci concentriamo sul fatto che ci può essere un numero molto più grande di delta più piccoli, e forse solo alcuni molto più grandi, che rompono il numBitsDelta .
In queste condizioni, potremmo trovare un numOptimumBitsDelta inferiore al massimo numMaxBitsDelta , che a sua volta è inferiore o uguale a numBitsElem .
Ma come possiamo codificare un elemento delta che supera numOptimumBitsDelta ?
Beh... dato che i delta non saranno mai 0 (non ci sono elementi ripetuti in un Set), possiamo usare il valore 0 per indicare che si tratta di un valore speciale.
E che 0 sarebbe seguito dal valore del delta, ma codificato questa volta con numMaxBitsDelta .Il numero totale di bit può essere calcolato come segue:
- 31 bit per il numero di elementi nell'intervallo. Calcoliamo il più piccolo numBitsElem per poter codificare un elemento. Calcoliamo anche l'elenco dei delta (elenco delle differenze tra gli elementi consecutivi dell'elenco ordinato degli elementi nell'insieme).
- 31 bit, per memorizzare il numero di elementi nel Set.
- 5 bit da conservare numOptimumBitsDelta .
- 5 bit da conservare numMaxBitsDelta .
- numOptimumBitsDelta bit * il numero di elementi nell'insieme.
- numMaxBitsDelta bit * il numero di delta che superano numOptimumBitsDelta .
Abbiamo già raggiunto la codifica ottimale?
Quinta approssimazione Beh... visto che abbiamo già programmato tutto questo...Potremmo pensare alla situazione complementare...Sarebbe possibile che la codifica del complemento del set con lo stesso algoritmo produrrebbe risultati più compressi?
Il complemento dell'insieme è inteso come un altro insieme, disgiunto dall'originale, la cui unione con l'insieme originale è l'intera gamma.
Cioè, il set complementare avrebbe tutti gli elementi della gamma assenti nel set originale, e nessuno di quelli nel set originale.
La bellezza è che da un insieme, è molto facile ottenere l'insieme complementare, e quindi potremmo ottenere l'insieme originale, dopo aver codificato quello complementare.
L'applicazione ovvia è un insieme che ha tutti gli elementi della gamma tranne uno, o pochi...
Beh... se conserviamo solo quelli assenti (il set complementare), potrebbe essere conservato in una dimensione molto più piccola, giusto?
La codifica in questo caso potrebbe essere così:
- 31 bit per il numero di elementi nell'intervallo. Calcoliamo il più piccolo numBitsElem Per codificare un elemento, calcoliamo anche l'elenco dei delta (elenco delle differenze tra gli elementi consecutivi dell'elenco ordinato degli elementi nell'insieme).
- 1 bit, per memorizzare se conserviamo il set originale, o il complemento.Questo è il bit in più.
- 31 bit, per memorizzare il numero di elementi nel Set.
- 5 bit da conservare numOptimumBitsDelta .
- 5 bit da conservare numMaxBitsDelta .
- numOptimumBitsDelta bit * il numero di elementi nell'insieme.
- numMaxBitsDelta bit * il numero di delta che superano numOptimumBitsDelta , nelle posizioni in cui appaiono.
Beh... ora stiamo parlando.
Quindi è lì che mi sono bloccato... ma sono consapevole che se tutte queste meraviglie possono essere fatte, cosa non potrebbe essere fatto cercando altri modelli, o semplicemente utilizzando un compressore senza perdita, come zip o 7z...
Dovrà aspettare, sul bruciatore posteriore per la prossima volta...
