Подсчет энтропии источника информации., С\С++ Опции

[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++ совершенно другие:

кашмар. я на 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 в лом запускать 
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), то это - зевершающий нулевой символ строки, по идее он не должен считаться, это же НЕ информация... У меня он как раз не считается. Попробуй подправить везде, может это дает разброс результатов?

Во, и я о том же

[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

, что неверно.

Но вобщем вопрос решен.