Энтропия сообщения, С++ Builder Опции

[18192123]

Требуется определить энтропию сообщения при условии независимости символов и при условии попарной зависимости символов..
Что касается 1-го случая -
H = -сумма (i=1,m)pi * log pi, логарифм берётся по основанию два, а pi - вероятность появления i-го символа..
Здесь проблем не возникает...нахождение вероятности не вызывает трудностей..
Во 2-м случае:
H = -1/2*сумма (i) сумма(j) pij * log pij, pij - вероятность появления пары символов. И как раз с этой вероятностью pij проблемка - не пойму, как её получить..

struct str
{
        char symbol; // очередной символ алфавита
        unsigned int count; // частота появления
        float probability; // вероятность
};
typedef str STR;
STR Alph[n];
int amount=0; //кол-во всех символов в сообщении

.....

i=0;
while (Alph[i].count)
{
 Alph[i].probability=(float)(Alph[i].count)/(amount); //нашли вероятность pi
 i++;
}

......
//и дальше вычисляем энтропию на основе pi
float entropy(int i)
{
 float Hp=(float)((-1)*Alph[i].probability*((log10(Alph[i].probability))/(log10(2))));
 return Hp;
}

.......

void __fastcall TFormTIPiS1::BitBtnHpClick(TObject *Sender)
{
 float HpAll=0;
 int i=0;
 while (Alph[i].count)
 {
  HpAll+=entropy(i);
  i++;
 }

}

Объясните пожалуйста, а что нужно делать, чтобы найти вероятность pij (при условии попарной зависимости символов)?

[volvo]

а что нужно делать, чтобы найти вероятность pij (при условии попарной зависимости символов)?

Собирать статистику, насколько часто в языке, на котором написано сообщение, встречаются те или иные двухбуквенные сочетания. Для русского языка может быть полезной вот это: Новый частотный словарь русской лексики (приведены количества встреченных сочетаний двух букв... Те сочетания, которые не были встречены, отсутствуют: их вероятность = 0. Собственно вероятности можно получить если делить число совпадений для каждого двухбуквенного сочетания на общую сумму всех совпадений...). Для других языков - надо искать (или составлять самостоятельно) другие частотные словари...

[18192123]

Собирать статистику, насколько часто в языке, на котором написано сообщение, встречаются те или иные двухбуквенные сочетания. Для других языков - надо искать (или составлять самостоятельно) другие частотные словари...

У меня сообщения на голландском..
И что будет значить составлять самостоятельно частотный словарь (составить всё возможные пары, проверить какие из них и по сколько раз встречаются в сообщении, и тогда, чтобы получить вероятность, количество конкретной пары поделить на общее количество возможных пар)?

Сообщение отредактировано: 18192123 - 21.02.2009 15:06

[volvo]

(составить всё возможные пары, проверить какие из них и по сколько раз встречаются в сообщении, и тогда, чтобы получить вероятность, количество конкретной пары поделить на общее количество возможных пар)?

Нет... У тебя не сообщение, которое само по себе, а сообщение на голландском языке Значит, тебе надо будет взять несколько объемных текстов на этом языке, и проанализировать вероятность, с которой в текстах встречаются все двухбуквенные комбинации... Чем объёмнее тексты (и чем их больше), тем ближе к истине будет такой словарь... Можно попробовать найти частотные словари для голландского языка...

[18192123]

Нет... У тебя не сообщение, которое само по себе, а сообщение на голландском языке Значит, тебе надо будет взять несколько объемных текстов на этом языке, и проанализировать вероятность, с которой в текстах встречаются все двухбуквенные комбинации... Чем объёмнее тексты (и чем их больше), тем ближе к истине будет такой словарь... Можно попробовать найти частотные словари для голландского языка...

А если не все комбинации встретятся? Такое может быть?

[volvo]

Если не встретятся при просмотре достаточно больших объемов - значит, их вероятности стремятся к нулю.

[18192123]

Пытаюсь сформировать массив структур, в котором каждая будет хранить ин-цию о паре символов...

define nn 1000
struct str
{
        char symbol;
        unsigned int count;
        float probability;
};
typedef str STR;
STR TWO[nn];
char *fileIn;
char two[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

...........
for (i=1;i<=26;i++)
 for (j=1;j<=26;j++)  {
  TWO[26*(i-1)+j].symbol=(char)strcat((char*)(&TWO[26*(i-1)+j].symbol),(char*)(&two[i]));
  TWO[26*(i-1)+j].symbol=(char)strcat((char*)(&TWO[26*(i-1)+j].symbol),(char*)(&two[j]));
  Memo1->Lines->Add(TWO[26*(i-1)+j].symbol);
 }

т.е. в TWO[1] хочу получить aa, в TWO[2] - ab и т.д.. а получается "Ь и ф...."
Подскажите, как добиться желаемого результата?

[volvo]

т.е. в TWO[1] хочу получить aa, в TWO[2] - ab и т.д..

Ты по определению этого не добьешься... Потому что char может хранить только один символ, а не строку... Я бы на твоем месте сделал таблицу:

struct p
{
	unsigned int count;
	float probability;
};
p table[26][26];

// ...

	for(int i = 0; i < 26; i++)
		for(int j = 0; j < 26; j++) {
			table['a' + i]['a' + j].count = 0;
			table['a' + i]['a' + j].probability = 0.0;
		}

и заполнять проще, индекс по вертикали - номер первой буквы от 'a', по горизонтали - номер второй буквы... Только не забудь все буквы привести к одному регистру, и если есть какие-то спец. символы в голландском языке, то и их надо будет учесть...

[18192123]

Появились проблемы с записью в файл значения энтропии..

char *fileOut;
//.........
if (SaveDialog1->Execute()) {
     fileOut=OpenDialog1->FileName.c_str();
    }
//............
 FILE *f;
 f=fopen(fileOut,"w");
 Ho = log10(CSpinEdm->Value)/log10(2);
 fprintf(f,"%f",Ho); // вот здесь вылетает программа.. с ошибкой
//...

Скажите пожалуйста, в чём дело?

Сообщение отредактировано: volvo - 26.02.2009 22:36

[volvo]

Оберни вызов функции fopen обработкой ошибки, и посмотри, что будет:

		FILE *f;
		if((f = fopen(fileOut,"w")) != NULL) {
			float Ho = log10(CSpinEdm->Value)/log10(2);
			fprintf(f,"%f",Ho); 
			fclose(f);
		}
		else ShowMessage("Cannot open file");

А теперь внимательно посмотри, чему у тебя присваивается fileOut...

[Altair]

Кстати была уже такая тема:
Подсчет энтропии источника информации.
Мы с Вольво делали.

[18192123]

volvo,Altair, спасибо!