Il modo più efficiente per codificare 2 posizioni tra 0 e 64?

Question

Ho valori a 64 bit che voglio comprimere sfruttando il fatto che solo una parte da qualche parte nel mezzo contiene dati e prima e dopo che sono zero.

Supponi che i dati effettivi siano l bit lunghi e riempiti con n 0s davanti e m 0s alla fine in modo tale che n + l + m = 64. Invece di trasmettere / memorizzare 64 bit, posso trasmettere l bit più qualunque cosa I è necessario codificare la posizione dei dati nell'intervallo a 64 bit.

Ad esempio, supponiamo che stavo memorizzando l, me bit di dati, quindi ripristinerei il modello originale a 64 bit leggendo l, leggendo l bit di dati, leggendo me spostando i bit di dati a sinistra.

Il più piccolo overhead che ho potuto immaginare è due volte 6 bit per memorizzare due di l, n e m (ognuno può essere compreso tra 0 e 64). È possibile ridurre quel numero?

Answer 1

l può essere compreso tra 0 e 64, quindi non inviare l, invia n e m, poiché possono essere entrambi zero e non devono andare fino a 64 (devono semplicemente essere in grado di aggiungere a 64).

I bit l devono iniziare e terminare con un 1, quindi non devono essere trasmessi.

invia 6 bit per n
invia fino a 6 bit per m (vedi sotto)
calcola l = 64 - (n + m)
se l = 0, il numero è 0, non inviare nient'altro
se l = 1, il numero è 1 * 2 ^ m, non inviare nient'altro
se l = 2, il numero è 3 * 2 ^ m, non inviare nient'altro
invia il mezzo l - 2 bit.

Overhead massimo = 10 bit.

La riduzione dei bit per m è dovuta al fatto che
se n > 32 allora conosci m & Lt; 32, quindi necessita solo di 5 bit
se n > 48 allora conosci m & Lt; 16, quindi necessita solo di 4 bit
se n > 56 allora conosci m & Lt; 8, quindi necessita solo di 3 bit
se n > 60 allora conosci m & Lt; 4, quindi necessita solo di 2 bit
se n = 63 allora conosci m < 2, quindi richiede solo 1 bit

Answer 2

La tua analisi suona bene per singoli valori. Ma se stai trasmettendo molti di questi valori insieme, un algoritmo di codifica entropica generico come gzip probabilmente farà meglio, poiché può eliminare abbastanza bene le stringhe di zeri e sfruttare anche le ridondanze nei dati.

Answer 3

Come hai affermato il problema, no non puoi fare di meglio della soluzione che hai proposto.

Tuttavia, se la distribuzione degli zeri nei numeri è distorta, potresti essere in grado di ottenere una compressione migliore in media usando i codici Huffman o una tecnica simile per rappresentare i conteggi. Un'altra possibilità è quella di utilizzare la codifica delta se la distribuzione zero è fortemente correlata da un valore a 64 bit al successivo.

In entrambi i casi, dovrai utilizzare un numero variabile di bit per rappresentare il numero di zeri. E se le tue assunzioni su disallineamento o correlazione risultano false, potresti finire per usare più bit in media rispetto a se lo avessi fatto in modo semplice.

Answer 4

La tua soluzione sembra abbastanza buona.
Codifica Huffman è un altro modo per comprimere i tuoi valori, specialmente se ci sono valori con grande frequenza.

Non è molto difficile implementarlo, ma potrebbe essere travolgente se non si hanno molti dati da trasmettere.

Answer 5

Esistono 64 possibili posizioni iniziali n della sequenza di quelle e la lunghezza della sequenza l non può più essere 64 - n. Quindi c'è un

r = sum(n = 0..63, 64 - n) + 1

sequenze in totale. Quello aggiunto è per una sequenza di tutti zeri. Fare un po 'di matematica produce quanto segue.

r = 64 * 64 - (63 * 64) / 2 + 1
  = 2081

La rappresentazione di 2081 valori possibili richiede log2(2081) = 11.023 bit. Il tuo suggerimento di codificare le informazioni utilizzando due 6 numeri di bit che richiedono 12 bit in totale è quindi ottimale (presupponendo distribuzioni uguali di tutti i valori possibili).