Quel est le meilleur schéma d'encodage d'entropie pour compresser les symboles avec une distribution de probabilité connue?

Question

Je cherche à encoder User_IDS dans une longue liste d'enregistrements d'appels. Les parties de ces enregistrements qui occupent le plus d'espace sont les symboles de l'appelant et du récepteur. Je vais créer une carte qui attribue les appelants les plus courts les plus courts --- Cela aidera à maintenir la taille globale des fichiers (et donc le temps d'E / S).

Je sais à l'avance combien de fois chaque symbole sera utilisé --- En d'autres termes, je connais la distribution de probabilité relative. En outre, il n'est pas important que les codes produits soient "sans préfixe" tels que les codes Huffman. Alors, quel est le meilleur schéma d'encodage, c'est-à-dire celui qui fournira le plus de compression et pour laquelle une mise en œuvre rapide existe?

Une réponse ne doit pas seulement indiquer un schéma de compression, elle doit également indiquer une mise en œuvre de ce schéma d'encodage.

Answer 1

Pour un codage sans perte à usage général avec une distribution de probabilité connue, à part le codage de Huffman, l'autre réponse "manuel" est codage arithmétique.

Dans la pratique, il existe une variété d'implémentations. Voir Ces codeurs à usage général. Chacun a des propriétés différentes. Sans plus d'informations, nous ne pouvons pas vous donner une réponse plus précise.

Answer 2

@conradlee: re "Dans quels cas le codage arithmétique est-il meilleur que le codage de Huffman?" En termes de compression, presque toujours. Si vous avez un symbole, S, avec une probabilité, ps, alors le nombre idéal de bits pour le coder avec, bs, est -log (ps) / log (2). Par exemple, si PS est 1/3, alors BS est d'environ 1,585 bits. Avec Huffman vous ont pour rassembler ou descendre le nombre entier de bits le plus proche (donc le rapport de compression diminuera). Le codage arithmétique le stockera avec un nombre fractionnaire de bits.