Ho bisogno di aiuto per analizzare questa tecnica di programmazione per comprimere un array

Question

Spero che i lettori siano a conoscenza della teoria delle informazioni di shannon che dice che il contenuto informativo associato a un evento a con probabilità p (a) è -log (p (a)). In parole povere se è necessario rappresentare un numero nell'intervallo 0-7, allora è necessario almeno -log (1/8) = log (8) (dove base è 2) cioè 3 bit.

Supponiamo che ci sia un array di numeri interi che vanno da 0 a 255. Invece di memorizzare l'array come numeri a 8 bit, ordinerò prima l'array in ordine ascendente (mantenendo un backup del corso). Invece di codificare ogni elemento dell'array come un intero a 8 bit, emetterò la sua posizione nell'array ordinato. Ora il problema è lasciare che il decodificatore o il ricevitore conoscano questo array ordinato. Invierò il primo (minimo) valore intero come un numero a 8 bit, quindi l'incremento da aggiungere a questo numero e presto. Prima tutto l'array ordinato seguito dall'ordine degli elementi cioè i valori di posizione.

Es: originale nell'edificio-> 231, 3, 45, 0, 23, 32, 78

ordinati nell'edificio-> 0,3,23,32,45,78,231

informazioni codificate è 0 (il primo elemento dell'array ordinato come 8 bit num) poi 3 (questo è l'incremento su 0) quindi 20 poi 9 poi 13, poi 33 poi 153.

dopo aver inviato il primo numero e successivi delta che invierò ordine cioè poiché ci sono 7 interi qui avrò bisogno di un numero a tre bit per l'ordine, 3 (la posizione di 0 nell'array originale) quindi 1 (posizione di 3) quindi 4 (posizione di 23) quindi 5 (posizione di 32) poi 2 (posizione di 45) quindi 6 (posizione di 78) quindi 0 (posizione di 231).

cioè i valori di posizione sono ora 3, 1, 4, 5, 2, 6, 0

analisi per vedere se questo schema comprimerà:

primo numero-> 8 bit (si può effettivamente richiede meno bit poiché è il più piccolo)

next 6 numeri -> 5 bit (il problema è che possiamo codificare 0,3,20,9,13 con 5 bit ma non 33 e 153 che potremmo dover codificare come 31 (massimo per 5 bit))

7 posizioni di 3 bit ciascuna-> 21 bit

totale-> 8 + 6 * 5 + 21 = 59. che è più dei 56 bit che avremmo richiesto per codificare 7 numeri di 8 bit ciascuno, e abbiamo raggiunto l'espansione rispetto alla compressione e il nostro schema è in perdita poiché alcuni grandi numeri non sono stati in grado di rappresentare in modo proporzionale.

Aggiungiamo un po 'di complessità a questo schema.

Codirò il primo 0 come numero di 8 bit immediatamente seguito dal codice per l'ultimo numero 231. Quindi invierò il codice per 3 l'incremento successivo su 0 quindi il codice per 153 il decremento su 231 poi 20 poi 33, 9,13

cioè ho inviato in diversi ordine-> invece di 0,3,20,9,13,33,153 invierò come 3,153,20,33,9,13

quello che ottengo da questa è la successiva riduzione dell'intervallo dinamico osservate che abbiamo inviato 0 quindi 231 poi 3 poi 153 a quest'ora l'intervallo di valori riduce io intendo che l'incremento successivo a 3 che sarà 20 non può essere maggiore del secondo numero precedente, cioè 78 e il numero 20 non può andare oltre il 75 (se va poi il thir d numero (3 + 76 (dire)) sarà maggiore di 78 chiaramente violazione della nostra ipotesi di smistamento.

Se avete capito l'idea fino ad ora ho uno schema ulteriormente migliorato per usare l'idea di ricerca binaria per ridurre ulteriormente la gamma dinamica e mettere questa tecnica su steroidi. Ecco l'array ordinato

0, 3, 23, 32, 45, 78, 231

rilevano che la matrice ordinata sta avendo 7 numeri e quello centrale è 32. Per ora ci codificare questo 32 con 8 bit, invieremo i delta in preordine. cioè il prossimo numero dopo 32 sarà 3 che sarà codificato come 29 (cioè 32-3) e il prossimo sarà 78 codificato come 46 (78-32), quindi 0 codificato come 3 (3-0) poi 23 codificato come 20 (23-3) poi 45 codificati come 33 (78-45), quindi l'ultimo 231 codificato come 153 (231-78).

Se ora si vede che è possibile decidere quanti bit utilizzare per ciascun numero qui, caso per caso.

invieremo l'array ordinato come 32 (intervallo 0-255 quindi 8 bit), 29 (intervallo 0-32 quindi 6 bit), 46 (intervallo 32-255 quindi 8 bit), 3 (intervallo 0- 3 quindi 2 bit), 20 (intervallo 3-32 quindi 5 bit), 33 (intervallo 32-78 quindi 6 bit), 153 (intervallo 78-255 8 bit)

così totalmente 8 + 6 + 8 + 2 + 5 + 6 + 8 = 43 che è non-lossy e più della nostra stima iniziale di 38 (8 bit + 5 * 6 bit) quindi questo aggiunto con i 7 valori di posizione di tre bit ciascuno in totale 43 + 21 = 64 è più di 56. Il nostro schema è ancora in espansione.

Che miglioramento possiamo fare per i numeri di posizione che sono 21 bit. Poiché ogni volta che inviamo informazioni sulla posizione il numero di posizioni si riduce di uno se abbiamo 7 posizioni da inviare, allora il numero di bit è log (7) + log (6) + log (5) .... Questo è quindi log (fatto (7)) bit dove tutti i logaritmi sono base 2.

osservi che ho usato il registro formula (a) + log (b) = log (ab)

Questo è uguale a 12,299 che, se aggiunto con 43 è uguale a 55.299, che è un po 'più basso di 56. Ma questo non è pratico. Abbiamo bisogno di almeno 3 (range 7) +3 (range 6) +3 (range 5) +2 (range 4) +2 (range 3) +1 (range 2) +0 (range 1) = 14 che quando aggiunto con 43 dà 57 che è l'espansione.

L'obiettivo di questo sforzo è ottenere una riduzione di almeno 1 bit delle dimensioni dei dati. Se comprimiamo 56 bit in 55 senza alcuna ipotesi sui dati, possiamo prendere l'output di 55 bit e comprimerlo nuovamente a 54 bit e presto. Questo sembra impossibile e l'idea è simile alle macchine perpetue. Il compito ora è vedere cosa ci impedisce di comprimere di più.

Ho bisogno di analizzare prendendo un esempio di un array più grande per vedere se 43 bit dell'array ordinato possono essere inferiori a 43. Anche il vantaggio di dividere un array in molte parti e codificare ciascuna parte separatamente. Inoltre, l'obiettivo è trovare la formula per calcolare il numero di bit necessari per rappresentare una matrice ordinata. vale a dire dato una dimensione dell'array e una gamma di elementi dell'array come trovare numeri come 43.

Prendiamo questo 3,1,4,5,2,6,0 come una matrice non ordinata di nuovo e osserviamo che questa sequenza è una di 5040 permutazioni di sette numeri da 0 a 6. Possiamo rappresentare questo come un numero a 13 bit (12.299 come suggerisce la teoria).

Ho bisogno di sapere che è possibile comprimere ancora meglio questo array.

Answer 1

Se comprimiamo 56 bit in 55 senza alcuna ipotesi sui dati, possiamo prendere l'output di 55 bit e comprimerlo nuovamente a 54 bit e presto. Questo sembra impossibile e l'idea è simile alle macchine perpetue. Il compito ora è vedere cosa ci impedisce di comprimere di più.

Non è possibile avere mai un algoritmo di compressione senza perdite senza alcuna ipotesi sui dati che è garantito per ridurre la dimensione di tutti i valori di dati possibili. Semplicemente da pigeon hole principle possiamo vedere quanto segue. Quando usi n bit puoi rappresentare 2^n valori. Usando i bit n-1 puoi rappresentare solo 2^(n-1) valori. Quindi, se si codifica metà dei valori originali, il valore successivo deve essere codificato utilizzando gli stessi bit di uno dei valori già codificati, quindi si perdono le informazioni. Naturalmente, se nei dati originali si utilizzano solo valori diversi da 2^(n-1), è possibile ridurre la dimensione di tali dati di un bit (o più), ma ciò sta già ipotizzando i dati. Inoltre, non sarà possibile utilizzare tale approccio per ridurre ricorsivamente la dimensione dei dati senza perdite.

Quindi è possibile trovare un modo per comprimere l'array di un bit, ma solo nel caso se il modo corrente di compressione utilizza la maggior parte dei possibili schemi di bit. Questo potrebbe essere un modo oscuro per comprimere l'array e sicuramente utilizzerà più della metà dei pattern di bit di alcuni k bit. Questa k sarà la tua soglia e non sarai più in grado di diminuire le dimensioni.

Anche il vantaggio di dividere un array in molte parti e codificarne ogni parte separatamente.

Se si divide l'array in parti più piccole, le differenze locali saranno inferiori e quindi è possibile utilizzare meno bit per rappresentare le differenze tra i numeri. Quindi in array come [1, 2, 3, 4, 2^30, 2^30 + 1, 2^30 + 2, 2^30 + 3] puoi risparmiare spazio. Dovrai comunque usare più bit per rappresentare i nuovi valori assoluti. Di nuovo potrebbero essere rappresentati come distanze rispetto ad un valore assoluto arbitrario per risparmiare spazio. Ma non sono sicuro che valga davvero la pena di tutti gli sforzi che hai delineato per salvare, in alcuni casi, 1 bit.

Per riassumere. Se hai un array come [2^30, 2^30 + 1, 2^30 + 2, 2^30 + 3], puoi ovviamente risparmiare spazio prendendo le differenze tra i numeri, ma come hai già affermato in la tua risposta, in alcuni casi aumenta la dimensione dei dati. Quindi, non è possibile avere un algoritmo di compressione che memorizza qualsiasi matrice (senza fare assunzioni) dei numeri utilizzando meno di n bit, dove n è la somma dei massimali dei logaritmi dei numeri nell'array.

Answer 2

L'obiettivo di questo sforzo è ottenere una riduzione di almeno 1 bit dei dati dimensioni.

Questo non è possibile su tutti gli ingressi. Puoi sprecare un grande sforzo nel cercare di contare correttamente i bit in varie rappresentazioni, fare errori, correggerli, ecc., Quando tutto ciò che devi davvero fare è contare quanti casi ci sono.

Ci sono 2^k ingressi possibili, dove k è il numero di bit nell'input. Diciamo che credi di avere una rappresentazione in k-1 bit di ogni singolo input. Quindi ci sono 2^(k-1) rappresentazioni possibili. Quindi se si alimentano ognuna di quelle rappresentazioni 2^(k-1) nel proprio decompressore, ovviamente si ottengono solo risultati 2^(k-1). Gli altri ingressi possibili 2^(k-1) mancano in azione. Non c'è modo di generare quegli input mancanti dalla tua rappresentazione, il che significa che in effetti la tua rappresentazione non può coprire tutti i possibili input 2^k. Almeno la metà di loro non sono coperti.