Nombre Maximum de numéros différents, la Compression de Huffman

Question

Je veux compresser beaucoup de 32 bits en nombre à l'aide de la compression de huffman.

Chaque numéro peut apparaître plusieurs fois, et je sais que chaque numéro sera remplacé par quelques séquences de bits:

111 010 110 1010 1000 etc...

Maintenant, la question:Combien de nombres différents peuvent être ajoutés à l'arbre de huffman avant de la longueur de la séquence binaire dépasse 32bits?

La règle de génération de séquences (pour ceux qui ne connaissent pas) c'est que chaque fois qu'un nouveau numéro est ajouté, vous devez attribuer la plus petite séquence binaire possible qui n'est pas le préfixe d'un autre.

Answer 1

Vous semblez comprendre le principe des codes de préfixe.

Beaucoup de gens (confusion) se réfèrent à tout CODES DE PRÉFIX COMME "CODES HUFFMAN".

Il existe de nombreux autres types de codes de préfixe - aucune d'entre elles ne compresse les données en plus de bits que la compression de Huffman (si nous négligeons les frais généraux de transmission du tableau de fréquence), mais beaucoup d'entre eux se rapprochent assez (avec quelques types de données) et Ayez d'autres avantages, tels que l'exécution beaucoup plus rapidement ou la garantie d'une durée de code maximale ("codes de préfixe limité à la longueur").

Si vous avez un grand nombre de symboles uniques, les frais généraux du tableau de fréquence Huffman deviennent grands - peut-être qu'un autre code de préfixe peut donner une meilleure compression nette.

De nombreuses personnes faisant de la compression et de la décompression du matériel ont des limites fixes pour la taille maximale des mots de code - de nombreux algorithmes de compression d'image et de vidéo spécifient un "code Huffman limité à la longueur".

Les codes de préfixe les plus rapides - codes universels - En fait, impliquent une série de séquences de bits qui peuvent être pré-générées sans tenir compte des fréquences de symboles réelles. Les programmes de compression qui utilisent ces codes, comme vous l'avez mentionné, associent le symbole d'entrée le plus fréquente à la séquence de bits la plus courte, le symbole d'entrée le plus prochain à la séquence de bits à court suivant, etc.

Par exemple, certains programmes de compression utilisent Codes fibonacci (une sorte de code universel), et associez toujours le symbole le plus fréquente de la séquence de bits "11", le symbole le plus proche de la séquence de bits "011", le suivant de "0011", le suivi de " 1011 ", et ainsi de suite.

L'algorithme Huffman produit un code similaire à bien des égards à un code universel - les deux sont des codes de préfixe. Mais, comme le souligne Cyan, l'algorithme Huffman est légèrement différent de ces codes universels. Si vous avez 5 symboles différents, l'arbre Huffman contiendra 5 séquences de bits différentes - cependant, les séquences de bits exactes générées par L'algorithme Huffman dépendent des fréquences exactes. Un document peut avoir un nombre de symboles de {10, 10, 20, 40, 80}, conduisant à des séquences de bits de Huffman {0000 0001 001 01 1}. Un autre document peut avoir un nombre de symboles de {40, 40, 79, 79, 80}, conduisant à des séquences de bits de Huffman {000 001 01 10 11}. Même si les deux situations ont exactement 5 symboles uniques, le code Huffman réel pour le symbole le plus fréquente est très différent dans ces deux documents compressés - le code Huffman "1" dans un document, le code Huffman "11" dans un autre document. Si, cependant, vous avez compressé ces documents avec le code Fibonacci, le code Fibonacci pour le symbole le plus fréquente est toujours le même - "11" dans chaque document.

Pour Fibonacci en particulier, le premier code Fibonacci 33 bits est "31 bits nul suivi de 2 bits", représentant la valeur F (33) = 3 524 578. Et donc 3 524 577 symboles uniques peuvent être représentés par des codes de fibonacci de 32 bits ou moins.

L'une des caractéristiques les plus contre-intuitives des codes de préfixe est que certains symboles (les symboles rares) sont "compressés" en séquences de bits beaucoup plus longues. Si vous avez réellement 2 ^ 32 symboles uniques (tous les nombres 32 bits possibles), il n'est pas possible de gagner une compression si vous forcez le compresseur à utiliser des codes de préfixe limités à 32 bits ou moins. Si vous avez réellement 2 ^ 8 symboles uniques (tous les nombres de 8 bits possibles), il n'est pas possible de gagner une compression si vous forcez le compresseur à utiliser des codes de préfixe limités à 8 bits ou moins. En permettant au compresseur d'étendre des valeurs rares - d'utiliser plus de 8 bits pour stocker un symbole rare que nous connaissons boîte être stocké en 8 bits - ou utiliser plus de 32 bits pour stocker un symbole rare que nous savons boîte être stocké en 32 bits - qui libère le compresseur pour utiliser moins de 8 bits - ou moins de 32 bits - pour stocker les symboles plus fréquents.

En particulier, si j'utilise des codes de fibonacci pour comprimer un tableau de valeurs, où les valeurs incluent tous les nombres 32 bits possibles, il faut utiliser les codes de fibonacci jusqu'à n bits de long, où f (n) = 2 ^ 32 - résolution pour Ni Obtenez n = 47 bits pour le symbole de 32 bits le moins utilisé.

Answer 2

Huffman est sur la compression, compression et exige une "asymétrie" de distribution de travail (en supposant que nous parlons de la normale, de l'ordre de-0, entropie).

La pire situation en matière de profondeur de l'arbre de Huffman est lorsque l'algorithme crée un dégénéré de l'arbre, c'est à direavec une seule feuille par niveau.Cette situation peut se produire si la distribution ressemble à une série de Fibonacci.

Par conséquent, le pire de la distribution de la séquence ressemble à ceci :1, 1, 1, 2, 3, 5, 8, 13, ....

Dans ce cas, vous remplissez les 32 bits de l'arbre avec seulement 33 différents éléments.

Notez, cependant, que pour atteindre un 32 profondeur de bits avec seulement 33 éléments, les plus nombreux, l'élément doit apparaître 3 524 578 fois.

Par conséquent, depuis suming tous les nombres de Fibonacci vous obtenez 5 702 886, vous avez besoin de compresser au moins 5 702 887 numéros de commencer à avoir un risque de ne pas être en mesure de les représenter avec un 32 bits arbre de huffman.

Cela étant dit, à l'aide d'un arbre de Huffman pour représenter 32-bits des nombres nécessite une quantité considérable de mémoire pour calculer et maintenir l'arbre.

[Modifier] Un format plus simple, appelé "logarithme rapprochement", donne presque le même poids à tous les symboles.Dans ce cas, seul le nombre total de symboles est nécessaire.

Il calcule très vite :dire pour 300 symboles, vous aurez une aide de 8 bits, et d'autres à l'aide de 9 bits.La formule de décider combien de chaque type :

9 bits :(300-256)*2 = 44*2 = 88 ;8 bits :300 - 88 = 212

Ensuite, vous pouvez distribuer les numéros que vous souhaitez (de préférence le plus souvent à l'aide de 8 bits, mais ce n'est pas important).

Cette version échelles jusqu'à 32 bits, qui signifie fondamentalement aucune restriction.