Algorithme pour générer « n » codes binaires Prefix
https://stackoverflow.com/questions/7322703
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
code préfixe est un ensemble de codes tels qu'aucun code est un préfixe d'un autre code. Par exemple, l'ensemble suivant est un code préfixe:
10
11
000
001
0100
0101
0110
0111
Avec les membres de n = 8. Je pense que ceux-ci sont généralement créés avec un certain type d'arbre de Huffman.
Ma question est: Pouvez-vous me aider à créer une fonction qui va générer un code préfixe binaire avec les membres « n »
Quelque chose comme ceci:
list<int> GenerateBinaryPrefixCodes(int n);
En outre, l'exigence est que ce soit « optimale » dans le sens que la somme totale de bits est réduite au minimum.
Je préférerais une réponse en C / C ++ / C # / quelque chose de similaire. Ce n'est pas vraiment devoirs, mais j'étiqueté de cette façon parce qu'il semble que ce serait un bon problème hw.
Merci!
La solution
Codes Prefix
Comme vous l'avez dit, un code de préfixe est celui où un code donné n'est pas un préfixe pour tout autre code donné. Ceci est une définition très générale. Un Huffman codage est une forme restreinte du Code Prefix.
Un usage courant pour le codage de Huffman est de minimiser (Optimize) le nombre total de bits nécessaires pour coder un « message ». Un « message » est typiquement une séquence de symboles et il est codé en faisant correspondre chaque occurrence de symbole à un code préfixe spécifique et l'écriture sur le code de préfixe à sa place. Tout ensemble de codes de préfixe pourrait être utilisé pour faire ça. Mais, un codage de Huffman entraînera dans les plus brefs messages possible en fonction du nombre de bits.
Par exemple, le jeu de caractères ASCII pourrait être considéré comme une mise en correspondance des symboles à un ensemble de 8 codes de préfixe bits. Cela pourrait même être considéré comme un codage de Huffman à condition que le message codé contenait exactement le même nombre de chaque symbole possible.
Les choses intéressantes commence lorsque le message à coder contient des fréquences de symboles qui sont inégales. À ceci un point peut réduire la longueur totale du bit du message à l'aide de codes de préfixe de longueurs différentes. L'utilisation à court codes de préfixe pour les symboles plus fréquents et les codes de préfixe plus pour les symboles moins fréquents.
A partir de votre exemple, il y a 8 symboles à coder. Symboles mis en correspondance des codes préfixe « 11 » et « 10 » seraient les plus symboles fréquents dans le message. De même, les symboles mis en correspondance avec « 0111 », « 0110 », « 1010 » et « 0100 » serait moins fréquente. Plus la fréquence est plus le code préfixe.
Le « truc » dans la création d'un codage de Huffman est de construire l'ensemble de codes de préfixe de telle sorte qu'après la cartographie chaque symbole dans le message à leurs codes préfixes associés le message contient le moins de bits possible.
Je trouve utile de voir les codes de préfixe comme un arbre binaire où chaque noeud feuille correspond à un symbole. Par exemple, l'arbre binaire correspondant aux codes préfixes donnés dans votre question (01, 11, 000, 001, 0100, 0101, 0110, 0111) serait:
+-- (11)
+--+
| +-- (10)
|
| +-- (0111)
--+ +--+
| | +-- (0110)
| +--+
| | | +-- (0101)
| | +--+
+--+ +-- (0100)
|
| +-- (001)
+--+
+-- (000)
Pour obtenir les valeurs entre parenthèses vous attribuez juste un « 1 » lorsque le bord supérieur est suivi ou un « 0 » si le fond bord est suivie.
Comment construire un tel arbre?
Démarrer avec des structures de données pour représenter un arbre binaire et une liste.
L'arbre binaire contiendra deux types de nœuds. 1) Un noeud feuille représentant un symbole et sa fréquence et 2) un noeud interne représentant la fréquence cumulative de tous les nœuds ci-dessous (il a aussi besoin de deux pointeurs, une pour la branche gauche et une pour la branche droite).
La liste contient un ensemble ordonné de noeuds de l'arbre binaire. Les nœuds dans la liste sont sur la base de la valeur de fréquence du noeud ils pointent. Le plus bas noeuds de fréquence se produisent à l'avant de la liste et augmenter vers la fin de la liste. Une liste chaînée de pointeurs vers des noeuds d'arbres pourrait être utile la mise en œuvre -. mais toute structure de liste ordonnée fera
L'algorithme ci-dessous utilise deux listes: une « référence » et une liste « de travail ». Comme les nœuds sont traitée dans la liste « référence » de nouveaux noeuds sont créés et insérés dans la liste « de travail » de telle sorte que la liste « de travail » reste commandée par la fréquence de noeud.
L'utilisation de ces structures de données et l'algorithme suivant pour créer un codage de Huffman.
0. Initialize the "reference" list by creating a leaf node for each symbol
then add it into this list such that nodes with the lowest frequency
occur at the front of the list and those with the highest frequency
occur at the back (basically a priority queue).
1. Initialize the "working" list to empty.
2. Repeat until "reference" list contains 1 node
2.1 Set MaxFrequency to the sum of the first 2 node frequencies
2.1 Repeat until "reference" list is empty
If ("reference" list contains 1 node) OR
(sum of the next two nodes frequency > MaxFrequency)
Move remaining nodes to the "working" list
Set "reference" list to empty
Else
Create a new internal node
Connect the first "reference" node to the left child
Connect the second "reference" node to the right child
Set the new node frequency to the sum of the frequencies of the children
Insert the new node into the "working" list
Remove the first and second nodes from the "reference" list
2.2 Copy the "working" list to the "reference" list
2.3 Set the "working" list to empty
A la fin de ce processus, l'élément de la liste « de référence » single sera la racine d'un arbre de Huffman. Vous pouvez énumérer codes de préfixe en faisant une profondeur d'abord traversal de l'arbre. Ecrire un « 0 » pour chaque branche gauche pris et un « 1 » pour chaque branche droite. Le code est complet quand une feuille est rencontrée. Le symbole au la feuille est codée par le code de Huffman juste généré.
Qu'est-ce qu'un optimum encodage
Un calcul intéressant une de peut effectuer consiste à calculer le « poids de bit » d'un codage de préfixe. Le poids de bits est le nombre total de bits nécessaires pour représenter les set des codes de préfixe.
Regardez votre arbre original ci-dessus. Le poids de cet arbre est (2 bits * 2) + (4 bits * 5) + (3 bits * 2) = 30 bits. Vous avez utilisé 30 bits pour représenter 8 valeurs de préfixe. Quoi est le nombre minimal de bits que vous auriez pu utiliser? Pensez-y, comme un arbre devient déséquilibré la longueur du chemin à quelques feuilles devient plus - ce qui ajoute au poids. Par exemple, le pire des cas pour un arbre préfixe 4 valeur serait:
+-- (1 bit)
--+
| +-- (2 bits)
+--+
| +-- (3 bits)
+--+
+-- (3 bits)
donnant un poids total de (1 bit * 1) + (2 bits * 1) + (3 bits * 2) = 9 bits
Équilibre l'arbre:
+-- (2 bits)
+--+
| +-- (2 bits)
--+
| +-- (2 bits)
+--+
+-- (2 bits)
donnant un poids total de (2 bits * 4) = 8 bits. Notez que pour les arbres équilibrés tous les codes préfixes finissent par ayant le même nombre de bits.
Arbre poids de bit est seulement la somme des longueurs de trajet à toutes les feuilles. Vous réduisez au minimum le poids de bits en réduisant au minimum la longueur totale du chemin -. et cela se fait en équilibrant l'arbre
Comme vous pouvez le voir, il n'y a pas beaucoup de valeur en réduisant au minimum tout arbre de préfixe donné, vous venez de finir avec une longueur fixe encodage symbole. La valeur vient quand on considère le poids binaire du message codé résultant. minimisation qui conduit à un codage de Huffman.
Combien de codages différents sont là?
codes de préfixe peut être généré en parcourant un arbre binaire et à émettre un « 0 » pour chaque branche inférieure suivie et pour chaque branche supérieure « 1 » suivi jusqu'à ce qu'une feuille est rencontrée. Comme dans:
+--+ (1)
|
--+
| +-- (01)
+--+
+-- (00)
Une autre alternative serait « flip » cette règle et lui attribuer un « 1 » pour chaque branche inférieure et un « 0 » pour les branches supérieures:
+-- (0)
|
--+
| +-- (10)
+--+
+-- (11)
Ces génèrent deux ensembles différents de codes de préfixe. ensembles Addtitional peuvent être générés par en passant par tous les 1/0 possibles affectations aux branches puis traversant l'arbre. Cela vous donnera 2 ^ n ensembles. Mais si vous faites cela, vous trouverez peut générer les mêmes codes de préfixe, mais dans un ordre différent. Par exemple, l'arbre précédent donnerait les ensembles suivants: {(0, 10, 11), (0, 11, 01), (1, 01, 00), (1, 00, 01)}. Ensuite, retourner l'arbre à:
+-- (??)
+--+
| +-- (??)
--+
|
+-- (?)
et vous obtenez: {(11, 10, 0), (10, 11, 0), (01, 00, 1), (00, 01, 1)}. Mettez les deux ensemble pour 2 ^ 3 = 8 ensembles. Toutefois, si vous voulez des ensembles uniques sans tenir compte pour il y a seulement 2 jeux: {(0, 10, 11), (1, 00, 01)}. Passez par le même exercice pour un arbre équilibré et il n'y a jamais 1 ensemble. Tout ça conduit moi de croire que le nombre d'encodages uniques est lié à la structure de l'équilibre de l'arbre utilisé pour générer des codes de préfixe. Malheureusement, je n'ai pas une formule exacte ou calcul travaillé sur. Sur une intuition, je suppose que le nombre serait 2 ^ (nombre de longueurs de code distincts - 1). Pour un arbre équilibré qui est: 2 ^ (1 - 1) = 1; pour un arbre avec deux longueurs de code distincts (comme dans l'exemple ci-dessus): 2 ^ (2 - 1) = 2; et pour votre exemple: 2 ^ (3 - 1) = 4.
Autres conseils
L'exigence que la somme du nombre de bits est réduit au minimum équivaut à exiger que les codes d'être optimal codes de Huffman pour une chaîne de caractères, où chaque symbole se produit une fois. Donc, il suffit de créer une chaîne avec n caractères uniques et produire un arbre de Huffman pour elle. L'algorithme est décrit sur Wikipedia .
Votre exemple pour n = 8 ne semble pas représenter une solution optimale.
10 11 000 001 0100 0101 0110 0111 Total de bits: 26
001 010 011 000 100 101 110 111 Nombre de bits: 24
Quand il y a une fréquence constante du préfixe optimal codage sera de longueur fixe. Chaque code préfixe sera de log de longueur (n) et être la représentation binaire de l'alphabet de 0..n-1.
EDIT pour le cas où n est pas une puissance de 2.
// generate tree
function PCode(n) {
var a = [];
for(var x=1; x<=n; x++) {
a.push({"v":x});
}
for(var x=0; x<n-1; x++) {
var node = {"v": null, "l": a.shift(), "r": a.shift()};
a.push(node);
}
return a.pop();
}
//print
function Print(node, s) {
if(node["v"] != null) {
console.log(s);
}
if(node["l"] != null) Print(node["l"], s + "0");
if(node["r"] != null) Print(node["r"], s + "1");
return;
}
//test
Print(PCode(3), "");
S'il vous plaît jeter un oeil à ce site C ++ tutoriel . Il fournira des structures C ++ utiles pour vous. Et je vois d'autres questions similaires de SO qui peuvent être utiles à la section « liée » à droite.
Je l'ai fait avant en C avec un algorithme récursif, et oui, il ferait un grand problème de devoirs.
Le problème de la génération (unicité de décodage) peut être garantie par la construction d'un arbre binaire de noeuds de feuille n, et dénombrer la position de chaque noeud de l'arbre (0 est la branche gauche, la figure 1 est branche à droite). Et vous avez raison, Huffman Les arbres ont cette propriété. Notez que pour Huffman arbres, chaque nœud est une pondération égale à la fréquence de son caractère représentatif, et l'arbre est construit avec une propriété récursive que la décision droite à gauche sur le nœud rejoint est basé sur la somme des enfants à ce moment-là . Cette propriété de somme cumulative est également la raison pour laquelle une distribution de Fibonacci donne la compression pire des cas pour Huffman arbres.
Note, le codage de Huffman est optimal pour le codage variable des alphabets fixes. Un exemple d'un alphabet non fixée est la décision de traiter « le » comme un seul élément dans le jeu à comprimer (par opposition à deux places et une chacune des lettres).
Votre problème semble ne pas être la substitution liée. Vous voulez juste des codes de préfixe pour n éléments où la somme des longueurs de tous les codes de préfixe est réduite au minimum. Ceci est le même que la construction d'un arbre de Huffman où chaque fréquence d'élément est 1 (car il garantit le codage minimum de la chaîne encodée totale, qui pour vous est égal à la somme des bits de chaque élément codé exactement une fois, à savoir réduire au minimum le total morceaux). Note: ce qui garantit l'encodage minimum, il ne garantit pas la plus rapide mise en œuvre. Vous n'avez probablement pas besoin de construire un arbre pour chaque appel de méthode. Malheureusement, je ne sais pas la mise en œuvre du haut de ma tête.
Le encode Let une chaîne binaire x par le nombre dont la représentation binaire est 1x. Dans le cas contraire, 0 et 00 tracerait au même int.
std::vector<int> GenerateBinaryPrefixCodes(int n) {
std::vector<int> list;
for (int i = n; i != 2 * n; ++i) list.push_back(i);
return list;
}
