Bonjour à tous,
Comment obtenir le nombre maximum de mots codables en n bits avec un code préfixe ?
J'ai du mal à voir comment on peut l'avoir.
Ce n'est pas à visée éducative, j'ai besoin du résultat relativement rapidement (même si j'ai besoin de le comprendre, je ne recherche pas de longues leçons expliquant le résultat quoi ^^). Je ne vois juste pas où le trouver.
Merci d'avance pour votre aide !
Bonjour,
Posée ainsi la question a pour réponse 2n ; mais ce n'est sans doute pas le fond de votre question qu'il vous faut donc préciser.
(code préfixe : aucun code n'est le préfixe d'un autre, c'est bien le cas avec tous les codes possibles sur n bits (de longueur fixe))
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Ah oui, désolé.
Je voulais dire, avec des codes de longueurs variables, dont la longueur peut aller de 1 bits à n bits.
Ce qui va sans dire va mieux en le disant ~
A l'autre extrême (1 code sur 1 bit, 1 code sur 2 bits ... 2 codes sur n bits), la réponse est n + 1, mais un grand nombre des valeurs entre n + 1 et 2n doivent être possibles
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Auriez-vous l'idée d'une méthode permettant de trouver le maximum ?
Ou en connaissez-vous une ?
(Je me doutais un peu qu'il y avait un grand nombre de possibilités entre n+1 et 2^n ^^')
Je ne comprends bien votre question : le maximum est 2n et il est atteint quand on doit coder 2n tous de même poids (équiprobables)
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Je vois.
En fait, mon but est de faire un compresseur.
Du coup, ça m'intéresse d'avoir un code préfixe de longueur variable pour pouvoir coder sur moins de bits (logique).
Mais en fait, je dois avoir une fonction de poids.
Je vois mieux ce que vous ne compreniez pas ^^
L'idée est donc avoir un maximum. J'aimerais pouvoir avoir le maximum en fonction de ma fonction de poids.
Par exemple, supposons qu'un mot de longueur l pèse (2*(n - l) + 1), quel code puis-je créer afin que la somme des poids des mots soit maximale ?
Un petit codage de Huffman ne serrait-il pas adapté?
https://fr.wikipedia.org/wiki/Codage_de_Huffman
Non, désolé ^^
Plus précisément, l'algorithme utilisé se fait sur un message transmis en continu, pas sur un message qu'on a en entier.
La problématique est précisément celle énoncée plus haut
Plus "moderne" que Huffman il y a Lempel-Ziv-Welch ou LZW
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Un codage de Huffman adaptatif pourrait convenir alors...Envoyé par Le_Doute
Du coup est-ce que ce fil ne serait pas mieux dans un forum informatique ?
Si Le_Doute en est persuadé (), il suffit de demander, je peux le faire.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
En fait, l'idée est de comparer les performances du LZW dans un certain contexte avec des tailles de dictionnaires différentes, fixes, puis variables, puis avec du code à longueur variable.
D'où la question du dessus ^^
L'idée est plus de pouvoir créer un certain code (problème d'optimisation), que de trouver le meilleur algorithme.
Du coup, je ne sais pas trop où ça se place, la question étant selon moi mathématique ^^'
