Помощь - Поиск - Пользователи - Календарь
Полная версия: Подсчет энтропии источника информации.
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
Altair
(из лекции)
Энтропия это величина, вычисляемая по формуле:
Нажмите для просмотра прикрепленного файла

где P(xi) - вероятность появления символа xi в сообщении,
ni - число символов в сообщении объемом n.

Вопрос первый.
Я верно все записал, т.е. энтропия так считается ? Второй вопрос, пишу программу для подсчета :

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

double get_count (char x[], char c){
int i;
double res=0;
for (i=0; i<=strlen(x); i++) if (x[i]==c) res+=1;
return res;
}

double prob (char x[], char c){
return get_count(x,c) / strlen(x);
}


double coeff_entropy (char x[]) {
int i;
double res=0;
for (i=0; i<=strlen(x); i++) {
res+= prob(x,x[i]) * log2(prob(x,x[i]));
}
res=res*(-1);
return res;
}

int main () {
char s[80];
printf("Entropy\n Enter text...\n");
scanf("%s",&s);
printf("Entropy [s] = %f", coeff_entropy(s));
return 0;
}

выдается какой-то бред.
Для сообщения
1111111111111211111111
выдается энтропия 1.750737
а для 1234567890 -
3.654121
мне кажется результат не верен.
т.к. вторая строка гораздо больше уменьашет степень неопределенности...
где я ошибся ?
volvo
Олег, вопрос на засыпку: Что такое энтропия источника информации? Нас учили, что
Цитата
Чем больше энтропия источника, тем больше информации получают от него.
Откуда ты получишь больше информации, из первого сообщения, или из второго?

P.S. Кстати, у меня результаты на TC++ совершенно другие:
Entropy
Enter text...
1111111111111211111111
Entropy [s] = 4.031222
Entropy
Enter text...
1234567890
Entropy [s] = 8.413924

Altair
Цитата
у меня результаты на TC++ совершенно другие:

mega_chok.gif
кашмар. я на MinGW проверял. Ужас. Почему разные результаты ?
У нас вот какое определение:
Мерой количества информации является энтропия.
Энтропия показывает, на сколбко уменьшается степень неопределенности знаний получателя информации об интересубщем его объекте или явлении
volvo
Хм... Я бы делал вот так (я например так понимаю приведенную тобой формулу):

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

#define LOG2TO10 0.30102999566398119521373889472449
// Ну нету у меня в Turbo C этой функции, а MinGW в лом запускать : )
double log2(double x)
{
return log(x) / LOG2TO10;
}

int p_count[256];

void set_p(char *s) {

for(int i = 0; i < 256; ++i) p_count[i] = 0;

for(char *p = s; *p; p++)
p_count[*p] += 1;
}

double coeff_entropy (char *s) {

double res = 0.0;
for(int i = 0; i < 256; ++i)
if(p_count[i]) {
double T = ((double)p_count[i] / strlen(s));
res += (T * log2(T));
}
return (- res);
}

int main () {
char s[80];
printf("Entropy\n Enter text...\n");
scanf("%s",&s);

set_p(s);
printf("Entropy [s] = %f", coeff_entropy(s));
return 0;
}
Altair
1. самое важное - log2 в mingw считает что-то другое... у меня после замены на
Цитата
#define LOG2TO10 0.30102999566398119521373889472449
// Ну нету у меня в Turbo C этой функции, а MinGW в лом запускать smile.gif
double log2(double x)
{
return log(x) / LOG2TO10;
}

совсем другой результат получился.

ты генерируешь массив, p_count, в котором по индексу i записанно число посвторений символа с кодом i в тексте.
(функция set_p)
и дальше проходишь по всему алфавиту (по p_count), для каждого символа которые встретился , ты считаешь
вероятность как число вхождения деленное на длинну строки...
то есть я, в цикле суммировал значение P(x) для каждого символа строки а не алфавита.

Хорошо, но при строках с различными символами результаты должны совпадать!
а не совпадают... почему ?
Я проверил. Вход 1234
выход.
у меня -5.756463
у тебя -4.605170

отчего так, я не пойму ?

я проверил, функция get_count уменя работает верно и prob тоже...
а сам цикл прозрачен, откуда такие глюки ?
вот мой вариант проги, на котором тестировал:

#include <stdio.h>
#include <string.h>
#include <math.h>
#define LOG2TO10 0.30102999566398119521373889472449
double _log2(double x)
{
return log(x) / LOG2TO10;
}
double get_count (char x[], char c){
int i;
double res=0;
for (i=0; i<=strlen(x); i++) if (x[i]==c) res+=1;
return res;
}

double prob (char x[], char c){
return get_count(x,c) / strlen(x);
}


double coeff_entropy (char x[]) {
int i,len=strlen(x);
double res=0.0;
for (i=0; i<=len; i++) {
res+= prob(x,x[i]) * _log2(prob(x,x[i]));
}
res=res*(1);
return res;
}

int main () {
char s[80];
printf("Entropy\n Enter text...\n");
scanf("%s",&s);
printf("Entropy [s] = %f", coeff_entropy(s));
//printf("Entropy [s] = %f", prob(s,'1'));
return 0;
}


добавил позже
ВСЕ. я понял почему.
for (i=0; i<=len; i++) {
strlen возвращает ведь длинну строки, а строку с 0 ... получается на 1 итерацию больше.
я заменил на
for (i=0; i< len; i++) {
теперь результаты совпадают.
Цитата
Entropy
Enter text...
1234
Entropy [s] = 4.605170
volvo
Олег, у тебя тут есть просто ошибки... Смотри:
for (i=0; i<=strlen(x); i++) if (x[i]==c) res+=1;
Это тебе что, Паскаль? Если i = strlen(x), то это - зевершающий нулевой символ строки, по идее он не должен считаться, это же НЕ информация... У меня он как раз не считается. Попробуй подправить везде, может это дает разброс результатов?

Во, и я о том же smile.gif
Altair
Все отлично.
Теперь осталось узнать, прогонять ли цикл по всем символам в строке или по алфавиту...
конечно скорее второе... завтра спрошу к преподавателя...
Altair
Итак.
Общее определение понятия истояника информации понятно, но есть еще и физическая интерпретация, понятия энтропия.
Энтропия показывает сколько нужно потратить минимально бит, для кодирования информации в сообщении.

Вот пример подсчета энтропии для строки символов:
Нажмите для просмотра прикрепленного файлаНажмите для просмотра прикрепленного файла

Вот окончательный вариант, правильной программы (написал только что, на основе программы volvo и моей старой)

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

int alf [256];

void init (){
for (int i=0; i<=255; i++) alf[i]=0;
}

double entropy (char *p) {
for (char *c=p, init(); *c!=0; c++) alf[*c] +=1;
double res=0, len=strlen(p);
for (int i=0; i<=255; i++) if (alf[i]!=0) res += ((double)alf[i] / len ) * log2((double)alf[i]/len);
return (-res);
}

int main () {
char s[80];
printf(" Enter message...\n");
scanf("%s",&s);
printf("Entropy H(x) = %f bit/symbol\nInfo I=n*H(x) = %d",entropy(s),(int)entropy(s)*strlen(s));
return 0;
}


тестирование, подтверждает пример:
Цитата

Enter message...
ctyl._ccc.__ttttt...__yy._lll.
Entropy H(x) = 2.526027 bit/symbol

Компилятор MinGW, а вот функция
#define LOG2TO10 0.30102999566398119521373889472449
// Ну нету у меня в Turbo C этой функции, а MinGW в лом запускать smile.gif
double log2(double x)
{
return log(x) / LOG2TO10;
}

видимо неверна, если с помощтю нее вычислять получается...
Цитата
Enter message...
ctyl._ccc.__ttttt...__yy._lll.
Entropy H(x) = 5.816391 bit/symbol
, что неверно.

Но вобщем вопрос решен.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.