Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Энтропия(рассчет)  (Прочитано 19718 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mfcer_
Гость
« : 05-12-2003 14:41 » 

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

Может кто подскажет как вычеслить условную энтропию? Помогите функцией на С++. Спасибо.
Записан
Serega
Гость
« Ответ #1 : 05-12-2003 14:52 » 

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

de
Offline Offline
Пол: Мужской

« Ответ #2 : 05-12-2003 15:12 » 

Офигеть!!! Чего только не бывает в жизни. Я шокирован!
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] быть?

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


сделать функцию? Ага
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Vorlon
Гость
« Ответ #3 : 05-12-2003 15:59 » 

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

Код:
H(B/A)= - Summ  Summ  p( ai, bj ) * log2( p( bj/ai ) )
           i     j
- условная энтропия системы B относительно системы A, p(...) - вероятности, которые можно получить из имеющихся строк, на сколько я понимаю.

Mfcer_, уточни вопрос.
« Последнее редактирование: 23-11-2007 15:22 от Алексей1153++ » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 05-12-2003 16:06 » 

Ну, по минусу в формуле можно понять, что 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/Х , где главная задача - понять что есть Х. Вижу два варианта: Х - общее число пар символов в исследуемой строке, или Х - число возможных пар, составленных из уникальных символов, пресутствующих в строке. Как правильно - не знаю - не знаком с данным предметом.

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #5 : 05-12-2003 16:09 » 

Цитата: Vorlon
Mfcer_, уточни вопрос.

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

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Vorlon
Гость
« Ответ #6 : 05-12-2003 19:49 » 

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

К стати, отсюда можно определить пропускную способность канала
C = max( I(A,B) ) [бит/символ]
Записан
NetRaider
Гость
« Ответ #7 : 06-12-2003 06:48 » 

Цитата

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



Для строки - (например строка "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__
Команда клуба

ru
Offline Offline

« Ответ #8 : 06-12-2003 12:25 » 

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

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

ru
Offline Offline

« Ответ #9 : 07-12-2003 10:54 » 

У меня получилось вот так, но это не правильно. Где здесь ошибка:
Код:
  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;
« Последнее редактирование: 23-11-2007 15:24 от Алексей1153++ » Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #10 : 08-12-2003 10:13 » 

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

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

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

data[j]


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

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


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

Vorlon
Гость
« Ответ #11 : 08-12-2003 17:32 » 

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

Цитата: Алексей1153

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

Алексей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__
Команда клуба

ru
Offline Offline

« Ответ #12 : 08-12-2003 19:49 » 

Цитата

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

кто-нибудь другой помоги...     Так больше нельзя...
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #13 : 08-12-2003 19:55 » 

Цитата
70% символов лишние (в тексте а не в алфавите).
ну там вроде самая частая - "е" (или "ё" - хрен пойми  Отлично ) , затем "а" ...

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

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

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

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

и дальше юзай ,, таким образом повысятся читабельность программы, а заодно выяснится любопытный факт - а вообще хватит 32 бита под?  Улыбаюсь
« Последнее редактирование: 13-04-2006 21:24 от Алексей1153 » Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #14 : 08-12-2003 19:57 » 

Цитата

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


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

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #15 : 08-12-2003 20:37 » 

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;
}
« Последнее редактирование: 23-11-2007 15:27 от Алексей1153++ » Записан

Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #16 : 08-12-2003 21:41 » 

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

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

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #17 : 09-12-2003 03:39 » 

Цитата
Выдвигаю предположение, что 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
...


блин, не успеваю:(  - пора на работу ... может кто продолжит
« Последнее редактирование: 23-11-2007 15:31 от Алексей1153++ » Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #18 : 09-12-2003 11:45 » 

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

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;   
}
« Последнее редактирование: 23-11-2007 15:32 от Алексей1153++ » Записан

Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #19 : 09-12-2003 12:09 » 

Я шокирован! СПАСИБО ОГРОМНОЕ Отлично   Жжешь  Быть такого не может  Улыбаюсь  Отлично  :!:   :arrow:   Ага
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #20 : 09-12-2003 12:18 » 

если какте - нибудь ошибки замечу, то сообщу сюда. еще раз спасибо.
Записан
Vorlon
Гость
« Ответ #21 : 09-12-2003 17:25 » 

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

Думаю этого объяснения достаточно что бы самому функцию написать Ага
« Последнее редактирование: 23-11-2007 15:34 от Алексей1153++ » Записан
Vorlon
Гость
« Ответ #22 : 09-12-2003 18:02 » 

Цитата: Алексей1153

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

Четко подметил, чем чаще символ встречается, тем меньше информации он в себе содержит Улыбаюсь
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


WWW
« Ответ #23 : 09-12-2003 20:06 » 

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

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

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;   
}
« Последнее редактирование: 23-11-2007 15:35 от Алексей1153++ » Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines