Энтропия(рассчет)

[Mfcer_]

даны две строки
строка источника данных
строка получателя

Может кто подскажет как вычеслить условную энтропию? Помогите функцией на С++. Спасибо.

[Serega]

Подскажи формулу условной энтропии и не вопрос =)

[Джон]

Офигеть!!! Чего только не бывает в жизни.
Serega, http://kirsoft.com.ru/freedom/KSNews_393.htm

Можно посчитать:
H=-P[i,j]*log2(P[i,j]), где P[i,j] - вероятность появления символа j, при условии что ему предшествовал символ i. Всё это суммируется по i и j . Только как с P[i,j] быть?

Как на основании:

даны две строки
строка источника данных
строка получателя

сделать функцию?

[Vorlon]

Джон, тут вроде об условной энтропии двух систем

Код:

H(B/A)= - Summ  Summ  p( ai, bj ) * log2( p( bj/ai ) )
           i     j

- условная энтропия системы B относительно системы A, p(...) - вероятности, которые можно получить из имеющихся строк, на сколько я понимаю.

Mfcer_, уточни вопрос.

[RXL]

Ну, по минусу в формуле можно понять, что P[i,j] есть число в диапазоне 1..0 (при P[i,j]==1 - log2(1)=0 и H=0, при 1>P[i,j]>0 log2(P[i,j])<0 и H>0, при P[i,j]->0  - H->+бесконечность).
Выдвигаю предположение, что P[i,j]=число_встречающихся_последовательностей_ij/Х , где главная задача - понять что есть Х. Вижу два варианта: Х - общее число пар символов в исследуемой строке, или Х - число возможных пар, составленных из уникальных символов, пресутствующих в строке. Как правильно - не знаю - не знаком с данным предметом.

А вот причем тут две строки - это загадка.

[Джон]

Mfcer_, уточни вопрос.

Дык и я про то же!

Формула вроде имеется, а вот как с данными. В смысле как в формулу "строку данных" подставить?  

[Vorlon]

RXL, это вроде к теории передачи информации относится, а две строки видимо для анализа канала связи, поскольку информационная характеристика канала определяется по формуле
I( A, B ) = H( B ) - H( A/B ) = H( A ) - H( B/A )
т. е. от энтропии получателя вычесть условную энтропию источника относительно этого же получателя. Но без более детальной информации о данных в строке, тут говорить не о чём.

К стати, отсюда можно определить пропускную способность канала
C = max( I(A,B) ) [бит/символ]

[NetRaider]

Формула вроде имеется, а вот как с данными. В смысле как в формулу "строку данных" подставить?

Для строки - (например строка "zzsxxxs"):
Сначала посчитать вхождение каждого символа(всего их 7):
z-2
s-2
x-3

Потом необходимо выяснить частоту появления каждого символа
z' = 2/7
s' = 2/7
x' = 3/7

Теперь определяется энтропия каждого символа (модуль логарифма - |log2(f)|)
ez = |log2(z')| = |log2(2/7)|
es = |log2(s')| = |log2(2/7)|  
ex = |log2(x')| = |log2(1/7)|

Далее необходимо проссумировать для каждого символа в строке:
 
es1 = ez*2 + es*2 + ex*3

Получилась энтропия для одной строки(es1)

[Mfcer__]

Уточни вопрос

:
Есть две строки CString источника и получателя.
Мне нужно вычеслить условную энтропию системы H(Z/S) (где Z - получателя S - отправтеля)

А можете дать готовую функцию на Си, пожалуйста.
А то мне через 2 дня  сдавать надо, а я .... не могу это сделать

[Mfcer__]

У меня получилось вот так, но это не правильно. Где здесь ошибка:

Код:

  int i,j;
  float t=0;
  float **data;//[1 << (sizeof(TCHAR)*8)][1 << (sizeof(TCHAR)*8)];
  data = new float*[(1 << (sizeof(TCHAR)*8))];
   for(i=0;i<(1 << (sizeof(TCHAR)*8));i++)
	   data[i] = new float[(1 << (sizeof(TCHAR)*8))];
  for(i=0;i<(1 << (sizeof(TCHAR)*8));i++)
	  for(j=0;j<(1 << (sizeof(TCHAR)*8));j++)
		  data[i][j]=NULL;
  for(i=0;i<m_Data.GetLength();i++)
	  for(j=0;j<m_Reverse.GetLength();j++)
		  data[(_TUCHAR)m_Reverse[j]][(_TUCHAR)m_Data[i]]++;
  for(i=0;i<(1 << (sizeof(TCHAR)*8));i++)
  {
	  t=0.0f;
	  for(j=0;j<(1 << (sizeof(TCHAR)*8));j++)
            t += data[i][j];
	  for(j=0;j<(1 << (sizeof(TCHAR)*8));j++)
		  if((t>0.0f)&&(data[i][j]!=0))
		  {
		    data[i][j] /= t;
			CString te;
			te.Format("%f",data[i][j]);
		//	AfxMessageBox(te);
		  }
  }
  t=0.0f;
  for(i=0;i<Num;i++)
	  for(j=0;j<(1 << (sizeof(TCHAR)*8));j++)
	  {
	    if(data[info[i].ch][j]>0.0f)
		  t+=info[i].P*data[info[i].ch][j]*((float)(log(1.0f/data[info[i].ch][j])/log(2)));
	  }
  for(i=0;i<(1 << (sizeof(TCHAR)*8));i++)
	  delete[] data[i];
  delete[] data;
  return t;

[Алексей++]

:arrow: про физический смысл энтропии мне, конечно, как до Африки пешком, но об коде - уточни, что именно неправильно, либо компиляция не завершается, либо прога не робит?

 :arrow: начнём с того, что непонятно, где заголовок функции

  :arrow: такое использование массивов требует аккуратности, надеюсь у тебя её есть

data[j]

я бы сделал так

int imax,jmax;
imax=...;
jmax=...;
float data = new float[ imax * jmax ];
...;
data[i*jmax + j ]=...;


 :arrow: и делай комментарии - в чужих программах разбираться трудно

[Vorlon]

Mfcer__, извини, с кодом разбираться влом, мож кто-нить другой поможет.

про физический смысл энтропии мне, конечно, как до Африки пешком

Алексей1153,  не преувеличивай   , могу вкратце объяснить:

Пусть у нас есть текст написанный с помощью алфавита из m символов, тогда кол-во информации на символ с номером i определяется по такой формуле
I( Ai ) = - log2 p( Ai ) [бит]
где Ai - символ алфавита а p( Ai ) - вероятность его появления в тексте.
Ну а энтропия, это мат ожидание I( Ai ), т. е. среднее кол-во информации на один символ
H( A ) = Summ [ p( Ai ) log2 p(Ai) ] , i = 1 ... m

Один любопытный момент - согласно расчетам в русском тексте 70% символов лишние (в тексте а не в алфавите).

[Mfcer__]

Mfcer__, извини, с кодом разбираться влом, мож кто-нить другой поможет.

кто-нибудь другой помоги...    

[Алексей++]

70% символов лишние (в тексте а не в алфавите).

ну там вроде самая частая - "е" (или "ё" - хрен пойми  ) , затем "а" ...

 :arrow:
кстати, Mfcer__, у тебя часто встречается выражение

(1 << (sizeof(TCHAR)*8 ))

- вычисли его один раз

DWORD MySIZE = 1 << (sizeof(TCHAR)*8 );

и дальше юзай ,, таким образом повысятся читабельность программы, а заодно выяснится любопытный факт - а вообще хватит 32 бита под? 

[Алексей++]

кто-нибудь другой помоги

чичас попробую... но могу не успеть...

[Алексей++]

NetRaider,  твоими определениями: энтропия для строки

Код:

float Entr(BYTE TheString, int Len)
{
	int i;
	//пусть Nsym – количество оригинальных символов
	int Nsym =...;
	//Сначала посчитать вхождение каждого символа
	int *entr=new int[Nsym];
	for(i=0; i< Len; i++) entr[TheString[i]]++;

	// Потом необходимо выяснить частоту появления каждого символа
	double *freq=new double [Nsym];
	for(i=0; i< Nsym; i++) freq[i]=1.0/(( double)freq[i]);
	
	//Теперь определяется энтропия каждого символа (модуль логарифма - |log2(f)|)	
	double *entrN=new double [Nsym];
	for(i=0; i< Nsym; i++)entrN[i]=abs(log(freq[i])/log(2));

	//Далее необходимо проссумировать для каждого символа в строке
	double sum=0;
	for(i=0; i< Nsym; i++) sum+= entrN[i];

	delete []entr;
	delete []freq;
	delete []entrN;
	return sum;	
}

[Mfcer__]

Спасибо огромное (это я тоже счас буду использовать), но  :oops:     :arrow:  мне слегка нужно другое :

условная энтропия систему (то есть есть получатель,а есть источник)
условная энтропия по двум строкам , который получил получатель и которую послал источник.
(это как бы надо смоделировать на компьютере)

[Алексей++]

Выдвигаю предположение, что P[i,j]=число_встречающихся_последовательностей_ij/Х , где главная задача - понять что есть Х. Вижу два варианта: Х - общее число пар символов в исследуемой строке, или Х - число возможных пар, составленных из уникальных символов, пресутствующих в строке. Как правильно - не знаю - не знаком с данным предметом.

а если кажные 2 соседних символа заменить на другой символ:

пример: есть строки
S: a a b c d b d d d d a a a d d d
Z: a c a d d d b b c

в них есть пАры символов (ставим им в соответствие новые символы)
aa - A, ab - B, bc - C, cd - D, db - E, bd - F, dd - G, da - H, ad - I, ac - J, ca - K, bb - L

исходные строки (с элементами BYTE )заменяем на новые
(с элементами WORD )

S: a a b c d b d d d d a a a d d d
Sn: ABCDEFGGGHAAIGG

Z: a c a d d d b b c
Zn: JKIGGELC

теперь известно
1) число_встречающихся_последовательностей_ij = количеству появлений в строках соответствующего паре ij нового символа
2) Х1 - общее число пар символов в исследуемой строке = сумме длин новых строк
3) Х2 - число возможных пар, составленных из уникальных символов = длине буфера с новыми символами

теперь осталось посчитать условную энтропию (правда пока неизвестно, что же есть X - придётся подставлять либо X1 либо X2)

Код:

//считаем количество уникальных символов
ZSymbs=...; SSymbs=...;
//создаём для них буфера
BYTE *ZBuf=new BYTE[ZSymbs];
BYTE *SBuf=new BYTE[SSymbs];
//заполняем их
...
//создаём буфер для новых символов, для начала длиной ZSymbs*SSymbs
WORD *NewBuf=new WORD[ZSymbs*SSymbs];
//находим уникальные пары и записываем в соотв слово по два символа - то есть получатся коды новых символов размерностью вдвое большей старых.
...
//Корректируем длину NewBuf
NewBuf=...;

//создаём буфера для новых строк длиной 
WORD *ZNewBuf=new WORD[ZSymbs-1];
WORD *SNewBuf=new WORD[SSymbs-1];
//заполняем их, используя ZBuf, SBuf и NewBuf
...

блин, не успеваю:(  - пора на работу ... может кто продолжит

[Алексей++]

ну вот, вроде (правда возможны косяки    )

double Entropia(BYTE *ZBuf, BYTE *SBuf, int ZLen; int SLen) -----
функция вычисляет энтропию для двух строк типа BYTE.

double Entr(WORD *ZSString, int Len)  ----
функция вычисляет энтропию для двух строк типа WORD. Её несложно перегрузить для типа BYTE

правда нахождение уникальных символов не успел сделать - опять ухожу из дома

Код:

double Entropia(BYTE *ZBuf, BYTE *SBuf, int ZLen; int SLen)
{
	//ZLen, SLen - длины строк 
	// ZBuf, SBuf- буфера со строками
	
	//общая длина двух строк с новыми символами
	ZSLen=ZSymbs+SSymbs-2;
	
	//создаём буфера для новых строк длиной на единицу короче
	WORD *ZNewBuf=new WORD[ZSymbs-1]; 
	WORD *SNewBuf=new WORD[SSymbs-1]; 
	//заполняем их, используя ZBuf, SBuf
	//два соседних символа образуют старший и младший байты кода двойного символа
	for(i=0;i<(ZSymbs-1);i++) ZNewBuf=( (WORD) ZBuf[i] )<<8 || ZBuf[i+1];
	for(i=0;i<(SSymbs-1);i++) SNewBuf=( (WORD) SBuf[i] )<<8 || SBuf[i+1];
		
	//объединяем строки
	WORD *ZS_String=new WORD[ZSLen]; 
	for(i=0; i<ZSymbs-1; i++) ZS_String[i]=ZNewBuf[i];
	for(i=ZSymbs-1; i<ZSLen; i++) ZS_String[i]=SNewBuf[i-(ZSymbs-1)];
	
	//считаем энтропию для объединённой строки

	double en=Entr(ZS_String, ZSLen);
	delete [] ZNewBuf; 
	delete [] SNewBuf;
	delete [] ZS_String;
	return en;
}

double Entr(WORD *ZSString, int Len) 
{
	int i; 
	//создаём буфер NewList для списка новых символов,
	//для начала длиной NewListLen=Len
	WORD *NewList=new WORD[Len]; 
	//находим уникальные символы в строке ZSString
	... 
	//Корректируем длину NewListLen
	NewListLen=...; //=количество уникальных символов
	//Сначала посчитать вхождение каждого символа 
	int *entry=new int[65536]; 
	for(i=0; i< Len; i++) entry[ZSString[i]]++; 

	// Потом необходимо выяснить частоту появления каждого символа 
	double *freq=new double [65536]; 
	for(i=0; i< NewListLen; i++) freq[i]=((double)1) / doublefreq[i]; 
    
	//Теперь определяется энтропия каждого символа (модуль логарифма - |log2(f)|)    
	double *entropiaN=new double [65536]; 
	for(i=0; i< NewListLen; i++)entropiaN[i]=abs( log(freq[i]) / log(2) ); 

	//Далее необходимо проссумировать для каждого символа в строке 
	double sum=0; 
	for(i=0; i< NewListLen; i++) sum+= entropiaN[i]; 

	delete []entry; 
	delete []freq; 
	delete []entropiaN; 
	return sum;    
}

[Mfcer__]

СПАСИБО ОГРОМНОЕ          :!:   :arrow:  

[Mfcer__]

если какте - нибудь ошибки замечу, то сообщу сюда. еще раз спасибо.

[Vorlon]

Mfcer__, не торопись радоваться, я думал что ты здорово в этом шаришь и сам расскажешь как посчитать, поэтому решил особо не объяснять формулы, но похоже придется.

Еще раз формула условной энтропии

Код:

H(B/A)= - Summ  Summ  p( ai, bj ) * log2( p( bj/ai ) ) 
           i     j 

p( ai, bj )= p( ai ) * p( bj/ai )

A - источник
B - приемник
p(ai) - вероятность передачи символа ai
p( bj/ai ) - вероятность приема bj, при условии что передан ai

Если мы будем принимать все без ошибок, то энтропии источника и приемника совпадут, это значит, что условная энтропия =NULL

При написании проги следует также учесть, что

Код:

 Lim ( x * log2( x ) ) = 0
x -> 0

Думаю этого объяснения достаточно что бы самому функцию написать

[Vorlon]

ну там вроде самая частая - "е" (или "ё" - хрен пойми    ) , затем "а" ...

Четко подметил, чем чаще символ встречается, тем меньше информации он в себе содержит

[Алексей++]

без ошибок, то энтропии источника и приемника совпадут,

ну так, блин, всё проще, чем на самом деле!

double EZ= Entr(ZString, ZLen);
double ES= Entr(SString, SLen);
//дальше - сравниваем EZ и ES и всё.

где Entr - функция

Код:

double Entr(BYTE *TheString, int Len) 
{
   int i; 
   BYTE *NewList=new BYTE[Len]; 
   //находим уникальные символы в строке TheString 
   NewList[0]=TheString[0]; NewListLen=1;
   bool f_new;
   for(i=0; i<Len; i++ ) 
   {//сканируем строку
       f_new=true;
       for(j=0; j<NewListLen;j++)
       {//сканируем уже найденные уникальные символы
           if(TheString[i] == NewList[j]) { f_new=false; break;}
       }
       //f_new показывает наличие неповторного символа
       if (f_new) TheString[(++NewListLen)-1]=TheString[i];
   }
   //теперь NewListLen==количество уникальных символов 

   //расчёт энтропии
   int *entry=new int[256]; 
   for(i=0; i< Len; i++) entry[TheString[i]]++; 
   double *freq=new double [256]; 
   for(i=0; i< NewListLen; i++) freq[i]=((double)1) / freq[i]; 
   double *entropiaN=new double [256]; 
   for(i=0; i< NewListLen; i++)entropiaN[i]=abs( log(freq[i]) / log(2) ); 
   double sum=0; 
   for(i=0; i< NewListLen; i++) sum+= entropiaN[i]; 
   delete []entry; 
   delete []freq; 
   delete []entropiaN; 
   return sum;    
}