Comment calculer les bits par caractère d'une chaîne? (BPC)

La bibliothèque SYS a une fonction GETIZEOF (), cela peut être utile? http://docs.python.org/dev/Library/sys

bits par caractère est une mesure de la performance des méthodes de compression. Il est appliqué en comprimant une chaîne puis en mesurant combien de bits la représentation comprimée prend totalement, divisé par le nombre de symboles (c'est-à-dire des caractères) dans la chaîne d'origine. Moins de bits par caractère La version compressée prend, plus la méthode de compression est efficace.

En d'autres termes, les auteurs utilisent leur modèle de langue générative, entre autres, pour compression et en supposant qu'une efficacité élevée de la méthode de compression résultante indique une hauteur. précision du modèle génératif sous-jacent.

dans la section 1, ils indiquent:

Le but du papier est de démontrer la puissance des grandes RNN entraînées avec le nouvel optimiseur sans Hessian en les appliquant à la tâche de prédire le caractère suivant dans un flux de texte. C'est un problème important, car un meilleur modèle de langue de niveau de caractère pourrait améliorer la compression des fichiers texte (Rissanen & Langdon, 1979) [...]

L'article de Rissanen & Langdon (1979) est la description originale de codage arithmétique , un procédé bien connu pour la compression de texte.

Le codage arithmétique fonctionne sur la base d'un modèle de langue générative, tel que celui que les auteurs ont construit. Compte tenu d'une séquence de caractères (éventuellement vide), le modèle prédit quel personnage peut venir ensuite. Les humains peuvent aussi faire cela, par exemple, étant donné la séquence d'entrée Hello w , nous pouvons deviner les probabilités pour le caractère suivant: o a une probabilité élevée (car bonjour monde est une continuation plausible), mais des caractères comme h comme dans bonjour où puis-je trouver .. ou i comme dans Bonjour Winston a également une probabilité non nulle. Nous pouvons donc établir une distribution de probabilité de caractères pour cette entrée particulière, et c'est exactement ce que le modèle générateur des auteurs aussi.

Ceci s'adapte naturellement avec le codage arithmétique: donné une séquence d'entrée qui a déjà été codée, la séquence de bits pour le caractère suivant est déterminée par la répartition des probabilités de caractères possibles: les caractères à haute probabilité Obtenez une séquence de bits courte, des caractères bas la probabilité obtenir une séquence plus longue. Ensuite, le caractère suivant est lu à partir de l'entrée et codé à l'aide de la séquence de bits qui a été déterminée à partir de la distribution de probabilité. Si le modèle de langue est bon, le caractère aura été prédit avec une probabilité élevée. La séquence de bits sera donc courte . Ensuite, la compression continue avec le caractère suivant, à nouveau en utilisant l'entrée jusqu'à présent pour établir une distribution de probabilité de caractères, déterminer des séquences de bits, puis lire le caractère suivant réel et le coder en conséquence.

Notez que le modèle génératif est utilisé à chaque étape pour établir une nouvelle distribution de probabilité. Il s'agit donc d'une instance de codage arithmétique adaptatif .

Après que toute entrée a été lue et codée, la longueur totale (dans les bits) du résultat est mesurée et divisée par le nombre de caractères dans l'entrée d'origine et non compressée. Si le modèle est bon, il aura prédit les personnages à haute précision, la séquence de bits utilisée pour chaque caractère aura été courte en moyenne, d'où le total des bits par caractère sera faible.

---

concernant les implémentations prêtes à l'emploi

Je ne suis pas au courant d'une mise en œuvre de codage arithmétique qui permet une intégration facile de votre propre modèle de langue générative. La plupart des implémentations construisent leur propre modèle adaptatif à la volée, c'est-à-dire. Ils ajustent les tables de fréquence de caractères lorsqu'ils lisent l'entrée.

Une option pour vous peut être de commencer avec Arcode . J'ai examiné le code et il semble que cela puisse être possible d'intégrer votre propre modèle, bien que ce ne soit pas très facile. Le membre auto._ranges représente le modèle de langue; Fondamentalement comme un éventail de fréquences de caractère cumulatif, donc self._ranges [ord (d ('d')] est la fréquence relative totale de tous les caractères inférieurs à d (c.-à-d. A , B , c si nous supposons uniquement des caractères alphabétiques minuscules). Vous devriez modifier ce tableau après chaque caractère d'entrée et cartographier les probabilités de caractères que vous recevez du modèle générateur à des gammes de fréquences de caractère.