Quelle structure de données est utilisée dans le codage de Huffman ?

La structure de données utilisée dans le codage Huffman est une "structure arborescente". Avec le support de l'algorithme de Huffman, un arbre binaire optimal est construit, et nous appelons ce type d'arbre arbre de Huffman. Par conséquent, pour être précis, le codage de Huffman est une forme de codage construite sur la base des arbres de Huffman.

L'environnement d'exploitation de ce tutoriel : système Windows 7, ordinateur Dell G3.

La structure de données utilisée dans le codage Huffman est une "structure arborescente".

Le codage Huffman, également connu sous le nom de codage Huffman, est une méthode de codage. Le codage Huffman est un type de codage à longueur variable (VLC). Huffman a proposé une méthode de codage en 1952. Cette méthode est entièrement basée sur la probabilité d'apparition de caractères pour construire un mot de code avec la longueur moyenne la plus courte de différents préfixes. Elle est parfois appelée le meilleur codage, et est généralement appelée codage de Huffman (parfois aussi appelé). Codage Hough).

Le codage de Huffman utilise la structure arborescente de la structure de données pour construire un arbre binaire optimal avec le support de l'algorithme de Huffman. Nous appelons ce type d'arbre un arbre de Huffman. Par conséquent, pour être précis, le codage de Huffman est une forme de codage construite sur la base d’arbres de Huffman et a une très large gamme d’applications.

Arbre de Huffman

Étant donné N poids en tant que N nœuds feuilles, construisez un arbre binaire, si la longueur de chemin pondérée de l'arbre atteint le minimum, un tel arbre binaire est appelé arbre binaire optimal, également connu sous le nom d'arbre de Huffman. L'arbre de Huffman est l'arbre avec la longueur de chemin pondérée la plus courte, et les nœuds avec des poids plus élevés sont plus proches de la racine.

La longueur de chemin pondérée de l'arbre est le poids de tous les nœuds feuilles de l'arbre multiplié par la longueur du chemin vers le nœud racine (si le nœud racine est de niveau 0, la longueur du chemin chemin du nœud feuille au nœud racine (la longueur du chemin d'un point est le nombre de couches du nœud feuille). La longueur du chemin de l'arbre est la somme des longueurs de chemin depuis la racine de l'arbre jusqu'à chaque nœud, enregistrée sous la forme WPL = (W1*L1+W2*L2+W3*L3+...+Wn*Ln), N poids Wi ( i=1,2,...n) constitue un arbre binaire avec N nœuds feuilles, et la longueur du chemin du nœud feuille correspondant est Li (i=1,2,...n). On peut prouver que le WPL de l’arbre de Huffman est le plus petit.

Pour plus d'articles connexes, veuillez visiter le Site Web PHP chinois ! !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!