Come procederesti a comprimere un elenco di numeri interi che non sono univoci e mantengono l'ordine originale?

Question

Come procederesti a comprimere un elenco di numeri interi che non sono univoci e mantengono l'ordine originale?

#1 da (8 voti)
#2 da (1 voti)

2

Iniziamo con un esempio

[1,1,1,5,3,1,1,2,78,2,3,1,1,...,1]

Come puoi vedere nell'esempio, 1 è ripetuto molto, ma ci saranno valori anomali (come 78, e in realtà tutto ciò che non è 1).

Il problema alla mia domanda è che, quando decomprimono i numeri, devono mantenere l'ordine originale. Gli algoritmi che ho trovato generalmente trattano numeri univoci, ordinati o non ordinati. Non mi dispiacerebbe usare uno di questi, ma dato che la mia lista intera non è unica, mi chiedo se al momento ci sia qualcosa che è ottimizzato per questo genere di cose.

Pensando velocemente, la mia prima idea era di fare un normale albero di compressione e solo mappare i valori per i modelli.

La mia seconda Idea era di descrivere solo numeri ripetuti in questo modo: 3- > 1, 1- > 5, 1- > 3, 2- > 1, 1- > 2, 1- > 78 , 1- > 2, 1- > 3, x- > 1.

Ovviamente funziona solo se i valori vengono costantemente ripetuti, che generalmente i numeri più bassi verranno ripetuti molto, ma non posso essere al 100% positivo che sarà il caso ogni volta.

algorithms compression

posta Michael King 29.10.2014 - 01:24

fonte

2 risposte

1

Qualsiasi algoritmo di compressione non-lossy dovrebbe funzionare per i tuoi requisiti. La più semplice da implementare è Codifica run-length , che è fondamentalmente la tua seconda idea.

Ci sono anche varianti della codifica Run-length in cui il conteggio delle ripetizioni per singole occorrenze di un numero può essere lasciato fuori, il che offre un rapporto di compressione migliore per i dati come il tuo.

risposta data 29.10.2014 - 08:54

fonte

Leggi altre domande sui tag algorithms compression

Stampa le istruzioni all'interno della funzione o prima di chiamarla? [chiuso] Come dovrei fornire informazioni dettagliate su un errore, se non attraverso i codici di stato HTTP?

score 8 · Accepted Answer

L'approccio più semplice a questo è semplice codifica della lunghezza di esecuzione . Questo fa parte di ciò che descrivi in "La mia seconda idea era di descrivere solo numeri ripetuti in questo modo: 3- > 1, 1- > 5, 1- > 3, 2- > 1, 1- > 2 , 1- > 78, 1- > 2, 1- > 3, x- > 1. "

Funziona per molti dati e lo vedrai spesso in bitmap (dove ogni valore è un 0 o un 1 - ecco perché è nella sezione 'immagine' di Modello di compressione dei dati su Wikipedia). La difficoltà con questo metodo è che più i dati sono irregolari, minori sono le tirature e più è necessaria la contabilità. Essenzialmente con RLE, la contabilità è con ogni blocco.

Potresti anche consultare codifica di Huffman . Ha un po 'più di lavoro da fare rispetto al semplice RLE, ma può anche risparmiare un po' di spazio.

Il fatto è che i tuoi numeri sono ancora fissi. Diciamo che sono tutti byte (8 bit) piuttosto che interi o long. Ora, 1 è in realtà 0000 0001 e 78 è 0100 1110 . Il trucco con la codifica di huffman è che possiamo fare in modo che% co_de occupi 1 bit perché è così comune.

Per la sequenza 1 abbiamo 1, 5, 3, 2, 78 come simboli - 5 simboli in totale.

Questo potrebbe darci una tabella di codifica di Huffman che assomiglia a:

1  => 1
2  => 01
3  => 0010
5  => 0011
78 => 0001

Questo ci permetterebbe di codificare i dati precedenti da:

0000 0001, 0000 0001, 0000 0001, 0000 0101, 0000 0011, 0000 0001,
0000 0001, 0000 0010, 0100 1110, 0000 0010, 0000 0011, 0000 0001, 
0000 0001, 0000 0001

A:

1, 1, 1, 0011, 0010, 1, 1, 01, 0001, 01, 0010, 1, 1, 1

Quale dovrebbe essere chiaro molto meno informazioni. Sì, sarà comunque necessario passare il libro mantenendo le informazioni su ciò che effettivamente quei significano con esso. Hai qualcosa che si comprime un po 'più stretto di RLE nella maggior parte dei casi a causa delle informazioni di contabilità comuni rispetto a quelle con le informazioni che vengono memorizzate ad ogni analisi.