Codage de Huffman

Résumé

Le codage de Huffman est un algorithme de compression de données sans perte. Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d'une estimation des probabilités d'apparition des symboles de source, un code court étant associé aux symboles de source les plus fréquents. Un code de Huffman est optimal au sens de la plus courte longueur pour un codage par symbole, et une distribution de probabilité connue. Des méthodes plus complexes réalisant une modélisation probabiliste de la source permettent d'obtenir de meilleurs ratios de compression. Il a été inventé par David Albert Huffman, et publié en 1952. Principe Le principe du codage de Huffman repose sur la création d'une structure d'arbre composée de nœuds. Supposons que la phrase à coder est « this is an example of a huffman tree ». On recherche tout d'abord le nombre d'occurrences de chaque caractèr

Source officielle

https://fr.wikipedia.org/wiki/Codage_de_Huffman

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (72)

Publications associées

Chargement

Personnes associées (8)

Personnes associées

Chargement

Unités associées (3)

Unités associées

Chargement

Concepts associés (17)

La compression de données ou codage de source est l'opération informatique consistant à transformer une suite de bits A en une suite de bits B plus courte pouvant restituer les mêmes informations, ou

vignette|Comparaison de la compression d'image entre les formats JPG (à gauche) et PNG (à droite). PNG utilise une compression sans perte. On appelle algorithme de compression sans perte toute procédu

En théorie de l'information, l'entropie de Shannon, ou plus simplement entropie, est une fonction mathématique qui, intuitivement, correspond à la quantité d'information contenue ou délivrée par une

Afficher plus

Concepts associés

Chargement

Cours associés (15)

Cours associés

Chargement

Séances de cours associées (21)

Séances de cours associées

Chargement

Rhythmic Modulation of Theta Oscillations Supports Encoding of Spatial and Behavioral Information in the Rat Hippocampus

Oscillatory patterns of activity in various frequency ranges are ubiquitously expressed in cortical circuits. While recent studies in humans emphasized rhythmic modulations of neuronal oscillations ("second-order" rhythms), their potential involvement in information coding remains an open question. Here, we show that a rhythmic (similar to 0.7 Hz) modulation of hippocampal theta power, unraveled by second-order spectral analysis, supports encoding of spatial and behavioral information. The phase preference of neuronal discharge within this slow rhythm significantly increases the amount of information carried by action potentials in various motor/cognitive behaviors by (1) distinguishing between the spikes fired within versus outside the place field of hippocampal place cells, (2) disambiguating place firing of neurons having multiple place fields, and (3) predicting between alternative future spatial trajectories. This finding demonstrates the relevance of second-order spectral components of brain rhythms for decoding neuronal information.

Elsevier2012

Chargement

Tight Bounds on the Redundancy of Huffman Codes

Ali Kakhbod

In this paper, we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

Ieee-Inst Electrical Electronics Engineers Inc2012

Chargement

Selection of Network Coding Nodes for Minimal Playback Delay in Streaming Overlays

Nicolae Cleju, Pascal Frossard, Nikolaos Thomos

Network coding permits to deploy distributed packet delivery algorithms that locally adapt to the network availability in media streaming applications. However, it may also increase delay and computational complexity if it is not implemented efficiently. We address here the effective placement of nodes that implement randomized network coding in overlay networks, so that the goodput is kept high while the delay for decoding stays small in streaming applications. We first estimate the decoding delay at each client, which depends on the innovative rate in the network. This estimation permits to identify the nodes that have to perform coding for a reduced decoding delay. We then propose two iterative algorithms for selecting the nodes that should perform network coding. The first algorithm relies on the knowledge of the full network statistics. The second algorithm uses only local network statistics at each node. Simulation results show that large performance gains can be achieved with the selection of only a few network coding nodes. Moreover, the second algorithm performs very closely to the central estimation strategy, which demonstrates that the network coding nodes can be selected efficiently in a distributed manner. Our scheme shows large gains in terms of achieved throughput, delay and video quality in realistic overlay networks when compared to methods that employ traditional streaming strategies as well as random network nodes selection algorithms.

2011

Chargement