Рассчитать энтропию файла

Я пытался найти эту функцию более двух часов в Google, форумах, википедии и на многих других форумах, но не смог ее найти. Как я могу это сделать? Я попробовал следующее, но это не сработало.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdint.h>

static unsigned int mylog2 (unsigned int val) {
unsigned int ret = -1;
while (val != 0) {
val >>= 1;
ret++;
}
return ret;
}

int main(int argc, char **argv)
{
FILE            *pFile;
int             i;              // various loop index
int             j;              // filename loop index
int             n;              // Bytes read by fread;
int             size;           // Filesize
float           entropy;
float           temp;           // temp value used in entropy calculation
long            alphabet[256];
unsigned char   buffer[1024];/* do this for all files */
for(j = 1; j < argc; j++)
{
/* initialize all values */
size = 0;
entropy = 0.0;
memset(alphabet, 0, sizeof(long) * 256);

pFile = fopen(argv[j], "rb");
if(pFile == NULL)
{
printf("Failed to open `%s`\n", argv[j]);
continue;
}

/* Read the whole file in parts of 1024 */
while((n = fread(buffer, 1, 1024, pFile)) != 0)
{
/* Add the buffer to the alphabet */
for (i = 0; i < n; i++)
{
alphabet[(int) buffer[i]]++;
size++;
}
}
fclose(pFile);

/* entropy calculation */
for (i = 0; i < 256; i++)
{
if (alphabet[i] != 0)
{
temp = (float) alphabet[i] / (float) size;
entropy += -temp * mylog2(temp);
}
}
printf("%02.5f [ %02.5f ]\t%s\n", entropy, entropy / 8, argv[j]);
} // outer for
return 0;
}

Я знаю, что делаю это неправильно. В Python это кажется намного проще, в Python это так:

import sys
import math

if len(sys.argv) != 2:
print "Usage: file_entropy.py [path]filename"sys.exit()

# read the whole file into a byte array
f = open(sys.argv[1], "rb")
byteArr = map(ord, f.read())
f.close()
fileSize = len(byteArr)
print 'File size in bytes:'
print fileSize
print

# calculate the frequency of each byte value in the file
freqList = []
for b in range(256):
ctr = 0
for byte in byteArr:
if byte == b:
ctr += 1
freqList.append(float(ctr) / fileSize)
# print 'Frequencies of each byte-character:'
# print freqList
# print

# Shannon entropy
ent = 0.0
for freq in freqList:
if freq > 0:
ent = ent + freq * math.log(freq, 2)
ent = -ent
print 'Shannon entropy (min bits per byte-character):'
print ent
print
print 'Min possible file size assuming max theoretical compression efficiency:'
print (ent * fileSize), 'in bits'
print (ent * fileSize) / 8, 'in bytes'

###  Modifications to file_entropy.py to create the Histogram start here ###
### by Ken Hartman  www.KennethGHartman.com

import numpy as np
import matplotlib.pyplot as plt

N = len(freqList)

ind = np.arange(N)  # the x locations for the groups
width = 1.00        # the width of the bars

#fig = plt.figure()
fig = plt.figure(figsize=(11,5),dpi=100)
ax = fig.add_subplot(111)
rects1 = ax.bar(ind, freqList, width)
ax.set_autoscalex_on(False)
ax.set_xlim([0,255])

ax.set_ylabel('Frequency')
ax.set_xlabel('Byte')
ax.set_title('Frequency of Bytes 0 to 255\nFILENAME: ' + sys.argv[1])

plt.show()

Как добиться того же в C ++? Надеюсь, кто-нибудь ответит на самом деле.

2

Решение

Вы не должны вычислять интегральную часть логарифма в базе 2. Для вычисления логарифма в базе 2 в C вы можете использовать log2 от math.h,

0

Другие решения

Энтропия Шеннона H= -1*sum(p_i*log(p_i)) где число Пи это частота каждого символа i (сумма) и результат в битах на символ, если основание журнала равно 2, «Натс» если база журнала n. Но оно меняется, если вы меняете способ выражения данных, т. Е. Если одни и те же данные выражаются в битах, байтах и ​​т. Д. Таким образом, вы можете разделить на лог (n) где n — количество доступных символов (2 для двоичного, 256 для байтов), а H будет варьироваться от 0 до 1 (это нормализованная интенсивная энтропия Шеннона).

Вышеуказанная энтропия является «Интенсивный» форма, то есть на символ, который аналогичен конкретной энтропии в физике, на кг или на моль. Обычная «обширная» энтропия, как физическая энтропия S=N*H где N — количество символов в файле. Немного математики с вышеупомянутым H дает нормализованная экстенсивная энтропия для файла, где «n» — это число различных символов «i» (2 для двоичного, 256 для байтов):

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

Для файлов с одинаковой частотой каждого символа это дает S=N, Энтропия не выполняет никакого сжатия данных и, таким образом, полностью игнорирует любые шаблоны, поэтому 000000111111 имеет те же H и S, что и 010111101000 (6 и 6 в обоих случаях).

0

По вопросам рекламы [email protected]