Quali dati non possono essere compressi dai codici di Huffman?

I codici di Huffman hanno la loro base nella probabilità che un dato personaggio apparirà in una sequenza. Questo è il motivo per cui quando si genera un albero di prefisso Huffman, i caratteri più comuni (quelli con la più alta probabilità di apparire) hanno la priorità per il prefisso più breve.

Ad esempio, nel testo di esempio "ABAABACABEDCA" il carattere "A" appare 6 volte e verrà assegnato il codice Huffman più breve, 0. "B" appare 3 volte, e otterrà il codice immediatamente successivo, 10, e così via, fino a E e D, che appaiono entrambi una sola volta e otterranno i codici più lunghi.

In un set di dati veramente casuale (cioè una stringa in cui tutti i possibili caratteri hanno un'uguale probabilità di apparire), quindi nessun albero di Huffman che può essere generato da quella stringa sarà più efficiente di qualsiasi altro.

La ragione di ciò è la entropia della stringa. Una stringa con alta entropia non può essere compresso, perché sono necessari più dati per descrivere l'entropia di quanto sarebbe necessario per dati a bassa entropia o altamente strutturati.

Il canale Youtube Computerphile ha un video eccellente che descrive questo problema in modo abbastanza elegante.

Diamo prima un'occhiata a cosa fa la compressione. Ci vuole qualcosa che è grande in qualcosa di più piccolo. Sì, questo è un modo veramente alto di guardarlo, ma è un importante punto di partenza.

Con una compressione senza perdita di dati, c'è un punto in cui non puoi più spremere le informazioni - ha raggiunto la massima densità di informazioni.

Questo entra nella definizione della teoria dell'informazione di entropia . Il pioniere in questo campo è Claude Shannon che ha scritto un articolo nel 1950 intitolato Predizione e entropia dell'inglese stampato . Risulta che l'inglese ha da 1,0 a 1,2 bit di informazioni per lettera. Pensa alla parola th_ che cos'è vuota? Puoi prevederlo - e quindi non ci sono molte informazioni in quella lettera.

Questo approfondisce ciò che fa la codifica di Huffman: stringe le informazioni il più strettamente possibile.

Cosa succede se stringi più strong? Beh, niente davvero. Non puoi montare più di 1 bit in 1 bit. Una volta compresso i dati nel modo ottimale in quanto può essere compresso, non è più possibile comprimerlo.

C'è uno strumento là fuori che misurerà la quantità di entropia in un determinato flusso di bit. L'ho usato per scrivere su numeri casuali . È ent . La prima misura che fa è quella dell'entropia nel flusso (può fare altri test accurati come calcolare il pi).

Se prendiamo qualcosa di abbastanza casuale, come i primi 4k bit di pi, otteniamo:

Entropy = 7.954093 bits per byte.

Optimum compression would reduce the size of this 4096 byte file by 0 percent.

Chi square distribution for 4096 samples is 253.00, and randomly would exceed this value 52.36 percent of the times.

Arithmetic mean value of data bytes is 126.6736 (127.5 = random).

Monte Carlo value for Pi is 3.120234604 (error 0.68 percent).

Serial correlation coefficient is 0.028195 (totally uncorrelated = 0.0).

E qui vediamo che non puoi comprimere le cifre di pi perché ci sono quasi 8 bit per byte di dati lì.

Quindi ... numeri casuali, non puoi comprimerli affatto.

Ci sono altre cose che hanno quantità piuttosto elevate di contenuto di informazioni come i dati crittografati.

Tornando al semplice esempio della parola th_ e riuscendo a indovinare cosa verrà dopo, lo sappiamo a causa delle frequenze lettera in inglese e delle parole inglesi valide. D'altra parte, se comprimiamo questo, è più difficile indovinare qual è la lettera successiva e quindi c'è più densità di informazioni per lettera.

Puoi vedere questo con (un semplice codice) la cifra di Vigenère

(daWikipedia: frequenze lettera Vigenere )

Qui possiamo vedere che le frequenze delle lettere sono molto più simili a quelle del normale testo inglese. Ciò renderebbe più difficile per la codifica di Huffman creare una codifica ottimale per il testo.

I moderni schemi di crittografia fanno un lavoro ancora migliore nel mescolare insieme le informazioni della chiave e il testo del dolore e creare un flusso di dati con una densità di informazioni estremamente elevata, e quindi molto difficile prevedere quale personaggio verrà dopo.

E così, quelle sono le cose che la compressione ha difficoltà con e perché.

Dati ben compressi. Nota che se i dati sottostanti sono altamente ripetitivi potresti trarre qualche vantaggio dalla compressione dei dati compressi perché lo schema sottostante non era abbastanza buono - i compressori sono normalmente costruiti per funzionare abbastanza velocemente e questo preclude la ricerca di uno schema assolutamente perfetto.

Si noti, inoltre, che se i dati "compressi" non sono realmente tutti compressi, si può ottenere un po 'in questo modo - ho ottenuto il 2% chiudendo un zip - ma solo quando lo zip originale era pieno di un sacco di piccoli file. I file venivano compressi, il file NAMES e altre informazioni sulla directory non lo erano.

Dati crittografati. Un buon schema di crittografia è praticamente indistinguibile dai dati casuali e quindi non è più comprimibile di quanto lo siano i dati casuali.