algorithm - ¿Cómo calcular la entropía de un archivo?

file-io entropy

Question

¿Cómo calcular la entropía de un archivo? (O digamos un montón de bytes)
Tengo una idea, pero no estoy seguro de que sea matemáticamente correcta.

Mi idea es la siguiente:

• Crea una matriz de 256 enteros (todos ceros).
• Recorrer el archivo y para cada uno de sus bytes,
  incrementa la posición correspondiente en la matriz.
• Al final: calcule el valor "promedio" para la matriz.
• Inicializa un contador con cero,
  y para cada una de las entradas de la matriz:
  agregue la diferencia de la entrada a "promedio" en el contador.

Bueno, ahora estoy atascado. ¿Cómo "proyectar" el resultado del contador de tal manera que todos los resultados estén entre 0.0 y 1.0? Pero estoy seguro, la idea es inconsistente de todos modos ...

Espero que alguien tenga soluciones mejores y más simples?

Nota: Necesito todo para hacer suposiciones sobre el contenido del archivo:
(texto plano, marcado, comprimido o algo binario, ...)

Answer 1

• Al final: calcule el valor "promedio" para la matriz.
• Inicialice un contador con cero, y para cada una de las entradas de la matriz: agregue la diferencia de la entrada a "promedio" en el contador.

Con algunas modificaciones puedes obtener la entropía de Shannon:

renombrar "promedio" a "entropía"

(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

Editar: Como mencionó Wesley, debemos dividir la entropía entre 8 para ajustarla en el rango 0. . 1 (o alternativamente, podemos usar la base logarítmica 256).

Answer 2

¿Es esto algo que ent podría manejar? (O tal vez no esté disponible en su plataforma).

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

Como ejemplo de contador, aquí hay un archivo sin entropía.

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

Answer 3

Calcula la entropía de cualquier cadena de caracteres sin signo de tamaño "longitud". Esto es básicamente una refactorización del código que se encuentra en http://rosettacode.org/wiki/Entropy . Utilizo esto para un generador IV de 64 bits que crea un contenedor de IV 100000000 sin engaños y una entropía promedio de 3.9. http://www.quantifiedtechnologies.com/Programming.html

#include <string>
#include <map>
#include <algorithm>
#include <cmath>
typedef unsigned char uint8;

double Calculate(uint8 * input, int  length)
  {
  std::map<char, int> frequencies;
  for (int i = 0; i < length; ++i)
    frequencies[input[i]] ++;

  double infocontent = 0;
  for (std::pair<char, int> p : frequencies)
  {
    double freq = static_cast<double>(p.second) / length;
    infocontent += freq * log2(freq);
  }
  infocontent *= -1;
  return infocontent;
 }

Answer 4

No existe la entropía de un archivo. En la teoría de la información, la entropía es una función de una variable aleatoria , no de un conjunto de datos fijo (bueno, técnicamente un conjunto de datos fijo tiene una entropía, pero esa entropía sería 0; podemos considerar los datos como una distribución aleatoria que tiene solo un resultado posible con probabilidad 1).

Para calcular la entropía, necesita una variable aleatoria para modelar su archivo. La entropía será entonces la entropía de la distribución de esa variable aleatoria. Esta entropía será igual al número de bits de información contenidos en esa variable aleatoria.

Answer 5

Para calcular la entropía de información de una colección de bytes, deberá hacer algo similar a la respuesta de tydok. (La respuesta de tydok funciona en una colección de bits).

Se supone que las siguientes variables ya existen:

• byte_counts es una lista de 256 elementos del número de bytes con cada valor en su archivo. Por ejemplo, byte_counts[2] es la cantidad de bytes que tienen el valor 2 .

• total es la cantidad total de bytes en su archivo.

Escribiré el siguiente código en Python, pero debería ser obvio lo que está sucediendo.

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)

Hay varias cosas que es importante tener en cuenta.

• La verificación del count == 0 no es solo una optimización. Si count == 0 , entonces p == 0 y log ( p ) no estarán definidos ("infinito negativo"), lo que provocará un error.

• El 256 en la llamada a math.log representa la cantidad de valores discretos que son posibles. Un byte compuesto por ocho bits tendrá 256 valores posibles.

El valor resultante será entre 0 (cada byte en el archivo es el mismo) hasta 1 (los bytes se dividen de manera uniforme entre todos los valores posibles de un byte).

Una explicación para el uso de log base 256

Es cierto que este algoritmo se aplica generalmente utilizando log base 2. Esto da la respuesta resultante en bits. En tal caso, tiene un máximo de 8 bits de entropía para cualquier archivo dado. Pruébelo usted mismo: maximice la entropía de la entrada haciendo byte_counts una lista de todos 1 o 2 o 100 . Cuando los bytes de un archivo se distribuyen uniformemente, encontrará que hay una entropía de 8 bits.

Es posible usar otras bases de logaritmo. Usar b = 2 permite un resultado en bits, ya que cada bit puede tener 2 valores. El uso de b = 10 coloca el resultado en dits o bits decimales, ya que hay 10 valores posibles para cada dit. El uso de b = 256 dará el resultado en bytes, ya que cada byte puede tener uno de los 256 valores discretos.

Curiosamente, al usar identidades de registro, puede averiguar cómo convertir la entropía resultante entre unidades. Cualquier resultado obtenido en unidades de bits se puede convertir en unidades de bytes dividiendo por 8. Como un efecto secundario interesante e intencional, esto da la entropía como un valor entre 0 y 1.

En resumen:

• Puedes usar varias unidades para expresar entropía
• La mayoría de las personas expresa entropía en bits ( b = 2)
  • Para una colección de bytes, esto proporciona una entropía máxima de 8 bits
  • Como el solicitante quiere un resultado entre 0 y 1, divida este resultado entre 8 para obtener un valor significativo
• El algoritmo anterior calcula la entropía en bytes ( b = 256)
  • Esto es equivalente a (entropía en bits) / 8
  • Esto ya da un valor entre 0 y 1

Answer 6

Por lo que vale, aquí está el cálculo tradicional (bits de entropía) representado 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 7

Re: Necesito todo para hacer suposiciones sobre el contenido del archivo: (texto plano, marcado, comprimido o algo de binario, ...)

Como otros han señalado (o han sido confundidos / distraídos), creo que en realidad estás hablando de entropía métrica (la entropía dividida por la duración del mensaje). Ver más en Entropy (teoría de la información) - Wikipedia .

El comentario de jitter que enlaza a los datos escaneados en busca de anomalías de entropía es muy relevante para su objetivo subyacente. Eso se vincula eventualmente con libdisorder (biblioteca C para medir la entropía de bytes) . Ese enfoque parece darle mucha más información para trabajar, ya que muestra cómo la entropía métrica varía en diferentes partes del archivo. Ver, por ejemplo, este gráfico de cómo la entropía de un bloque de 256 bytes consecutivos desde una imagen jpg de 4 MB (eje y) cambia para diferentes desplazamientos (eje x). Al principio y al final, la entropía es más baja, ya que está parcialmente insertada, pero se trata de 7 bits por byte para la mayoría del archivo.

Fuente: https://github.com/cyphunk/entropy_examples . [ Tenga en cuenta que este y otros gráficos están disponibles a través de la novedosa licencia http://nonwhiteheterosexualmalelicense.org .... ]

Más interesante es el análisis y gráficos similares en el análisis de la entropía de bytes de un disco formateado FAT | CON POCA SINCERIDAD

Las estadísticas como el máximo, el mínimo, el modo y la desviación estándar de la entropía métrica para todo el archivo y / o el primer y último bloque de este podrían ser muy útiles como firma.

Este libro también parece relevante: Detección y reconocimiento de archivos enmascarados para correo electrónico y seguridad de datos - Springer

Answer 8

Si usa la entropía de la teoría de la información, tenga en cuenta que podría tener sentido no usarla en bytes. Supongamos que, si sus datos consisten en flotantes, debería ajustar una distribución de probabilidad a esas carrozas y calcular la entropía de esa distribución.

O bien, si los contenidos del archivo son caracteres unicode, debe usarlos, etc.

Answer 9

Sin ninguna información adicional, la entropía de un archivo es (por definición) igual a su tamaño * 8 bits. La entropía del archivo de texto es aproximadamente de tamaño * 6.6 bits, dado que:

• cada personaje es igualmente probable
• hay 95 caracteres imprimibles en byte
• log (95) / log (2) = 6.6

La entropía del archivo de texto en inglés se estima en alrededor de 0.6 a 1.3 bits por carácter (como se explica here ).

En general, no se puede hablar de entropía de un archivo dado. Entropy es una propiedad de un conjunto de archivos .

Si necesita una entropía (o entropía por byte, para ser exactos), la mejor manera es comprimirla usando gzip, bz2, rar o cualquier otra compresión fuerte, y luego dividir el tamaño comprimido por el tamaño sin comprimir. Sería una gran estimación de entropía.

Calcular byte de entropía por byte como sugirió Nick Dandoulakis da una estimación muy pobre, ya que supone que cada byte es independiente. En los archivos de texto, por ejemplo, es mucho más probable tener una letra pequeña después de una letra que un espacio en blanco o puntuación después de una letra, ya que las palabras suelen tener más de 2 caracteres. Entonces, la probabilidad de que el siguiente carácter esté en el rango az se correlaciona con el valor del carácter anterior. No use la estimación aproximada de Nick para datos reales, use la relación de compresión gzip en su lugar.

Answer 10

Tengo dos años de retraso en responder, así que tenga en cuenta esto a pesar de tener pocos votos favorables.

Respuesta corta: utilice mis ecuaciones en negrita primera y tercera a continuación para obtener lo que la mayoría de la gente está pensando cuando dicen "entropía" de un archivo en bits. Usa la primera ecuación si quieres la entropía de Shannon, que en realidad es entropía / símbolo, como dijo 13 veces en su artículo, de lo que la mayoría de la gente no está enterada. Algunas calculadoras de entropía en línea usan esta, pero la H de Shannon es "entropía específica", no "entropía total", lo que ha causado tanta confusión. Usa la 1ª y la 2ª ecuación si quieres la respuesta entre 0 y 1 que es entropía / símbolo normalizado (no es bits / símbolo, sino una medida estadística verdadera de la "naturaleza entrópica" de los datos al permitir que los datos elijan su propia base de registro en lugar de asignar arbitrariamente 2, e, o 10).

Hay 4 tipos de entropía de archivos (datos) de N símbolos largos con n tipos únicos de símbolos. Pero tenga en cuenta que al conocer el contenido de un archivo, usted conoce el estado en el que se encuentra y, por lo tanto, S = 0. Para ser precisos, si tiene una fuente que genera una gran cantidad de datos a los que tiene acceso, entonces puede calcular la futura entropía / carácter futuro de esa fuente. Si usa lo siguiente en un archivo, es más exacto decir que está estimando la entropía esperada de otros archivos de esa fuente.

• Entropía Shannon (específica) H = -1 * suma (count_i / N * log (count_i / N))
  donde count_i es el número de veces que ocurrió el símbolo en N.
  Las unidades son bits / símbolo si el registro es la base 2, nats / símbolo si el registro es natural.
• Entropía específica normalizada: H / log (n)
  Las unidades son entropía / símbolo. Varía de 0 a 1. 1 significa que cada símbolo aparece con la misma frecuencia y cerca de 0 es donde todos los símbolos, excepto 1, ocurrieron solo una vez, y el resto de un archivo muy largo fue el otro símbolo. El registro está en la misma base que el H.
• Entropía absoluta S = N * H
  Las unidades son bits si log es base 2, nats si ln ()).
• Entropía absoluta normalizada S = N * H / log (n)
  La unidad es "entropía", varía de 0 a N. El registro está en la misma base que el H.

A pesar de que la última es la "entropía" más verdadera, la primera (entropía H de Shannon) es lo que todos los libros llaman "entropía" sin (la calificación necesaria en mi humilde opinión). La mayoría no aclara (como lo hizo Shannon) que es bits / símbolo o entropía por símbolo. Llamar a H "entropía" es hablar demasiado libremente.

Para archivos con la misma frecuencia de cada símbolo: S = N * H = N. Este es el caso para la mayoría de los archivos grandes de bits. La entropía no comprime los datos y, por lo tanto, ignora por completo cualquier patrón, por lo que 000000111111 tiene la misma H y S que 010111101000 (6 1 y 6 0 en ambos casos).

Como otros han dicho, usar una rutina de compresión estándar como gzip y dividir antes y después dará una mejor medida de la cantidad de "orden" preexistente en el archivo, pero eso está sesgado contra datos que se ajustan mejor al esquema de compresión. No existe un compresor perfectamente optimizado para fines generales que podamos usar para definir un "orden" absoluto.

Otra cosa a considerar: H cambia si cambia la manera en que se expresan los datos. H será diferente si selecciona diferentes agrupaciones de bits (bits, mordiscos, bytes o hex). Entonces se divide por log (n) donde n es el número de símbolos únicos en los datos (2 para binario, 256 para bytes) y H va de 0 a 1 (esto es normalización de la entropía de Shannon en unidades de entropía por símbolo) . Pero técnicamente, si solo se producen 100 de los 256 tipos de bytes, entonces n = 100, no 256.

H es una entropía "intensiva", es decir, es por símbolo que es análogo a la entropía específica en física que es entropía por kg o por mol. La entropía "extensa" regular de un archivo análogo a la física ''S es S = N * H donde N es el número de símbolos en el archivo. H sería exactamente análogo a una porción de un volumen de gas ideal. La entropía de la información no puede hacerse exactamente igual a la entropía física en un sentido más profundo porque la entropía física permite arreglos "ordenados" y desordenados: la entropía física resulta más que una entropía completamente aleatoria (como un archivo comprimido). Un aspecto de los diferentes Para un gas ideal hay un factor adicional de 5/2 para explicar esto: S = k * N * (H + 5/2) donde H = posibles estados cuánticos por molécula = (xp) ^ 3 / hbar * 2 * sigma ^ 2 donde x = ancho del cuadro, p = impulso total no direccional en el sistema (calculado a partir de energía cinética y masa por molécula), y sigma = 0,341 de acuerdo con el principio de incertidumbre que da solo el número de estados posibles dentro de 1 std dev.

Un poco de matemática proporciona una forma más corta de entropía extensa normalizada para un archivo:

S = N * H / log (n) = suma (count_i * log (N / count_i)) / log (n)

Las unidades de esto son "entropía" (que no es realmente una unidad). Está normalizado para ser una medida universal mejor que las unidades de "entropía" de N * H. Pero tampoco debe llamarse "entropía" sin clarificación porque la convención histórica normal es llamar erróneamente "entropía" H (que es contraria a las aclaraciones hechas en el texto de Shannon).

Answer 11

Una solución más simple: gzip el archivo. Use la proporción de tamaños de archivo: (tamaño de gzip) / (tamaño de original) como medida de aleatoriedad (es decir, entropía).

Este método no le da el valor absoluto exacto de la entropía (porque gzip no es un compresor "ideal"), pero es lo suficientemente bueno si necesita comparar la entropía de diferentes fuentes.