Comment calculer l'entropie d'un fichier ?

Question

Comment calculer l'entropie d'un fichier ? (Ou disons simplement un tas d'octets)
J'ai une idée, mais je ne suis pas sûr qu'elle soit mathématiquement correcte.

Mon idée est la suivante :

• Créez un tableau de 256 entiers (tous des zéros).
• Traverse le fichier et pour chacun de ses octets,
  incrémente la position correspondante dans le tableau.
• A la fin : Calculez la valeur "moyenne" du tableau.
• Initialise un compteur avec zéro,
  et pour chacune des entrées du tableau :
  ajouter la différence de l'entrée à la "moyenne" du compteur.

Eh bien, maintenant je suis coincé. Comment "projeter" le résultat du compteur de telle manière que tous les résultats soient compris entre 0.0 et 1.0 ? Mais je suis sûr, que l'idée est incohérente de toute façon...

J'espère que quelqu'un a des solutions meilleures et plus simples ?

Note : J'ai besoin que l'ensemble fasse des hypothèses sur le contenu du fichier :
(texte en clair, balisé, compressé ou binaire, ...)

Answer 1

• A la fin : Calculez la valeur "moyenne" du tableau.
• Initialiser un compteur avec zéro, et pour chacune des entrées du tableau : ajoutez la différence de l'entrée par rapport à la "moyenne" au compteur.

Avec un peu de modifications vous pouvez obtenir l'entropie de Shannon :

renommez "moyenne" en "entropie".

(float) entropy = 0
for i in the array[256]:Counts do 
  (float)p = Counts[i] / filesize
  if (p > 0) entropy = entropy - p*lg(p) // lgN is the logarithm with base 2

Edit : Comme Wesley l'a mentionné, nous devons diviser l'entropie par 8 afin de l'ajuster dans l'intervalle 0 . . 1 (ou alternativement, on peut utiliser la base logarithmique 256).

Answer 2

Une solution plus simple : gzip le fichier. Utilisez le ratio des tailles de fichiers : (taille du fichier compressé)/(taille du fichier original) comme mesure du caractère aléatoire (c'est-à-dire de l'entropie).

Cette méthode ne vous donne pas la valeur absolue exacte de l'entropie (car gzip n'est pas un compresseur "idéal"), mais elle est suffisante si vous devez comparer l'entropie de différentes sources.

Answer 3

Pour calculer l'entropie d'information d'une collection d'octets, vous devrez faire quelque chose de similaire à la réponse de Tydok. (La réponse de tydok fonctionne sur une collection de bits).

Les variables suivantes sont supposées exister déjà :

• byte_counts est une liste de 256 éléments du nombre d'octets avec chaque valeur dans votre fichier. Par exemple, byte_counts[2] est le nombre d'octets qui ont la valeur 2 .

• total est le nombre total d'octets dans votre fichier.

Je vais écrire le code suivant en Python, mais ce qui se passe devrait être évident.

import math

entropy = 0

for count in byte_counts:
    # If no bytes of this value were seen in the value, it doesn't affect
    # the entropy of the file.
    if count == 0:
        continue
    # p is the probability of seeing this byte in the file, as a floating-
    # point number
    p = 1.0 * count / total
    entropy -= p * math.log(p, 256)

Il y a plusieurs choses qu'il est important de noter.

• Le chèque de count == 0 n'est pas seulement une optimisation. Si count == 0 alors p == 0 et log( p ) sera indéfini ("infini négatif"), ce qui entraînera une erreur.

• Le site 256 dans l'appel à math.log représente le nombre de valeurs discrètes possibles. Un octet composé de huit bits aura 256 valeurs possibles.

La valeur obtenue sera comprise entre 0 (chaque octet du fichier est identique) et 1 (les octets sont répartis de manière égale entre toutes les valeurs possibles d'un octet).

---

Une explication de l'utilisation de la base logarithmique 256

Il est vrai que cet algorithme est généralement appliqué en utilisant la base logarithmique 2. Cela donne la réponse résultante en bits. Dans ce cas, vous disposez d'un maximum de 8 bits d'entropie pour un fichier donné. Essayez vous-même : maximisez l'entropie de l'entrée en faisant byte_counts une liste de tous les 1 ou 2 ou 100 . Lorsque les octets d'un fichier sont répartis uniformément, vous constaterez qu'il y a une entropie de 8 bits.

Il est possible d'utiliser d'autres bases logarithmiques. Utilisation de b \=2 permet un résultat en bits, car chaque bit peut avoir 2 valeurs. En utilisant b \=10 met le résultat dans dits ou bits décimaux, car il y a 10 valeurs possibles pour chaque dit. Utilisation de b \=256 donnera le résultat en octets, car chaque octet peut avoir une des 256 valeurs discrètes.

Il est intéressant de noter qu'en utilisant les identités logarithmiques, vous pouvez trouver comment convertir l'entropie résultante entre les unités. Tout résultat obtenu en unités de bits peut être converti en unités d'octets en divisant par 8. Comme effet secondaire intéressant et intentionnel, cela donne à l'entropie une valeur comprise entre 0 et 1.

En résumé :

• Vous pouvez utiliser différentes unités pour exprimer l'entropie.
• La plupart des gens expriment l'entropie en bits ( b \=2)
  • Pour une collection d'octets, cela donne une entropie maximale de 8 bits.
  • Puisque le demandeur veut un résultat entre 0 et 1, divisez ce résultat par 8 pour obtenir une valeur significative.
• L'algorithme ci-dessus calcule l'entropie en octets ( b \=256)
  • Ceci est équivalent à (entropie en bits) / 8
  • Cela donne déjà une valeur entre 0 et 1

Answer 4

Pour ce que cela vaut, voici le calcul traditionnel (bits d'entropie) représenté en C# :

/// <summary>
/// returns bits of entropy represented in a given string, per 
/// http://en.wikipedia.org/wiki/Entropy_(information_theory) 
/// </summary>
public static double ShannonEntropy(string s)
{
    var map = new Dictionary<char, int>();
    foreach (char c in s)
    {
        if (!map.ContainsKey(c))
            map.Add(c, 1);
        else
            map[c] += 1;
    }

    double result = 0.0;
    int len = s.Length;
    foreach (var item in map)
    {
        var frequency = (double)item.Value / len;
        result -= frequency * (Math.Log(frequency) / Math.Log(2));
    }

    return result;
}

Answer 5

Est-ce quelque chose que ent pourrait gérer ? (Ou peut-être n'est-il pas disponible sur votre plateforme).

$ dd if=/dev/urandom of=file bs=1024 count=10
$ ent file
Entropy = 7.983185 bits per byte.
...

A titre de contre exemple, voici un fichier sans entropie.

$ dd if=/dev/zero of=file bs=1024 count=10
$ ent file
Entropy = 0.000000 bits per byte.
...