Mfcer_
Гость
|
|
« : 05-12-2003 14:41 » |
|
даны две строки строка источника данных строка получателя
Может кто подскажет как вычеслить условную энтропию? Помогите функцией на С++. Спасибо.
|
|
|
Записан
|
|
|
|
Serega
Гость
|
|
« Ответ #1 : 05-12-2003 14:52 » |
|
Подскажи формулу условной энтропии и не вопрос =)
|
|
|
Записан
|
|
|
|
Джон
просто
Администратор
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] быть? Как на основании: даны две строки строка источника данных строка получателя
сделать функцию?
|
|
|
Записан
|
Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома. "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
|
|
« Ответ #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/Х , где главная задача - понять что есть Х. Вижу два варианта: Х - общее число пар символов в исследуемой строке, или Х - число возможных пар, составленных из уникальных символов, пресутствующих в строке. Как правильно - не знаю - не знаком с данным предметом.
А вот причем тут две строки - это загадка.
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
Джон
просто
Администратор
Offline
Пол:
|
|
« Ответ #5 : 05-12-2003 16:09 » |
|
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__
Команда клуба
Offline
|
|
« Ответ #8 : 06-12-2003 12:25 » |
|
Уточни вопрос : Есть две строки CString источника и получателя. Мне нужно вычеслить условную энтропию системы H(Z/S) (где Z - получателя S - отправтеля) А можете дать готовую функцию на Си, пожалуйста. А то мне через 2 дня сдавать надо, а я .... не могу это сделать
|
|
|
Записан
|
|
|
|
Mfcer__
Команда клуба
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++ »
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #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, не преувеличивай , могу вкратце объяснить: Пусть у нас есть текст написанный с помощью алфавита из m символов, тогда кол-во информации на символ с номером i определяется по такой формуле I( Ai ) = - log2 p( Ai ) [бит] где Ai - символ алфавита а p( Ai ) - вероятность его появления в тексте. Ну а энтропия, это мат ожидание I( Ai ), т. е. среднее кол-во информации на один символ H( A ) = Summ [ p( Ai ) log2 p(Ai) ] , i = 1 ... mОдин любопытный момент - согласно расчетам в русском тексте 70% символов лишние (в тексте а не в алфавите).
|
|
|
Записан
|
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #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 »
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #14 : 08-12-2003 19:57 » |
|
кто-нибудь другой помоги
чичас попробую... но могу не успеть...
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #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__
Команда клуба
Offline
|
|
« Ответ #16 : 08-12-2003 21:41 » |
|
Спасибо огромное (это я тоже счас буду использовать), но :oops: :arrow: мне слегка нужно другое : условная энтропия систему (то есть есть получатель,а есть источник) условная энтропия по двум строкам , который получил получатель и которую послал источник. (это как бы надо смоделировать на компьютере)
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #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++ »
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #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++ »
|
Записан
|
|
|
|
|
|
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 » |
|
ну там вроде самая частая - "е" (или "ё" - хрен пойми ) , затем "а" ... Четко подметил, чем чаще символ встречается, тем меньше информации он в себе содержит
|
|
|
Записан
|
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #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++ »
|
Записан
|
|
|
|
|