「C-assign-2008-10-30」の編集履歴(バックアップ)一覧はこちら
「C-assign-2008-10-30」(2008/11/13 (木) 01:26:57) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
//c++/linenumber
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#define ALPH 26
#define LENGTH 20
#define AINDEX(c) ((isupper(c)) ? (c) - 'A' : (c) - 'a')
#define LOG2(x) (log10(x) / log10(2.0))
typedef struct _AlphabetPair
{
int former;
int latter;
double probability;
} AlphabetPair;
typedef struct _AlphabetSingle
{
int character;
double entropy;
} AlphabetSingle;
typedef struct _AlphabetTwo
{
int memberA;
int memberB;
double distance;
} AlphabetPair_for_Db;
//縦横で二次元配列を表示
void showCrossTable(const int[][ALPH], int, int);
//P(y when x)を算出
double Py_when_x(const int[][ALPH], int, int);
//上を先に作ったので、これを代入して配列に収めるだけの関数
void set_map_P(const int[][ALPH], double [][ALPH], AlphabetPair *, AlphabetPair *);
//上からエントロピーの算出
void set_map_entropy(const double[][ALPH], double [], AlphabetSingle *, AlphabetSingle *);
//バタチャリヤ距離の算出
double distance(const double [][ALPH], int indexA, int indexB);
//バタチャリヤ距離の最大最小の検出
void scan_distance(const double [][ALPH], AlphabetPair_for_Db *, AlphabetPair_for_Db *);
int main()
{
int i,j,c;
int counter[ALPH][ALPH];
double prob[ALPH][ALPH];
double entropy[ALPH];
char lastCharacter = 0;
AlphabetPair mini_pair = {0,0,1};
AlphabetPair maxi_pair = {0,0,0};
AlphabetSingle mini_ent= {0,0};
AlphabetSingle maxi_ent= {0,0};
AlphabetPair_for_Db mini_dpair = {0,0,-1};
AlphabetPair_for_Db maxi_dpair = {0,0,0};
//init
for( i=0; i < ALPH; ++i)
for(j=0; j < ALPH; ++j)
counter[i][j] = 0;
//get characters
while( (c=getchar()) != EOF)
{
if( isalpha(c) && isalpha(lastCharacter) )
++counter[AINDEX(lastCharacter)][AINDEX(c)];
lastCharacter = c;
}
showCrossTable(counter, ALPH, ALPH);
set_map_P(counter, prob, &mini_pair, &maxi_pair);
printf( "max:x=%d(%c),y=%d(%c),p=%lf\n"
"min:x=%d(%c),y=%d(%c),p=%lf\n"
,maxi_pair.former , maxi_pair.former + 'A'
,maxi_pair.latter , maxi_pair.latter + 'A'
,maxi_pair.probability
,mini_pair.former , mini_pair.former + 'A'
,mini_pair.latter , mini_pair.latter + 'A'
,mini_pair.probability);
set_map_entropy(prob, entropy, &mini_ent, &maxi_ent);
printf( "max:x=%d(%c),entropy=%f bit\n"
"min:x=%d(%c),entropy=%f bit\n"
,maxi_ent.character , maxi_ent.character + 'A'
,maxi_ent.entropy
,mini_ent.character , mini_ent.character + 'A'
,mini_ent.entropy);
scan_distance(prob, &mini_dpair, &maxi_dpair);
printf( "max:x1=%d(%c),x2=%d(%c),distance=%f\n"
"min:x1=%d(%c),x2=%d(%c),distance=%f\n"
,maxi_dpair.memberA , maxi_dpair.memberA + 'A'
,maxi_dpair.memberB , maxi_dpair.memberB + 'A'
,maxi_dpair.distance
,mini_dpair.memberA , mini_dpair.memberA + 'A'
,mini_dpair.memberB , mini_dpair.memberB + 'A'
,mini_dpair.distance);
for(i=0; i<ALPH; ++i)
printf("%2d(%c):%e\n", i, i+'A', distance(prob, i, i));
return 0;
}
void showCrossTable(const int data[][ALPH], int n_x, int n_y)
{
int i,j;
printf(" ");
for(i=0; i<ALPH; ++i)
//printf("%*s%c", 7, "", i+'A');
printf("\t%c",i+'A');
putchar('\n');
for(i=0; i<n_x; ++i)
{
putchar(i+'A');
for(j=0; j<n_y; ++j)
//printf(" %*d", 7, data[i][j]);
printf("\t%d",data[i][j]);
putchar('\n');
}
}
double Py_when_x(const int data[ALPH][ALPH], int x, int y)
{
int i;
int data_x = 0;
for(i=0; i<ALPH; ++i)
data_x += data[x][i];
if(data_x <= 0)
return 0;
return (double)data[x][y] / data_x;
}
void set_map_P(const int data[ALPH][ALPH], double container[][ALPH], AlphabetPair *mini, AlphabetPair *maxi)
{
int i,j;
for(i=0; i<ALPH; ++i)
{
for(j=0; j<ALPH; ++j)
{
container[i][j] = Py_when_x(data, i, j);
if(mini->probability > container[i][j] && container[i][j] > 0)
{
mini->former = i;
mini->latter = j;
mini->probability = container[i][j];
}
if(maxi->probability < container[i][j])
{
maxi->former = i;
maxi->latter = j;
maxi->probability = container[i][j];
}
}
}
}
// dataは今回は確率
void set_map_entropy(const double data[][ALPH], double container[], AlphabetSingle *mini, AlphabetSingle *maxi)
{
int i,j;
for(i=0; i<ALPH; ++i)
{
container[i] = 0;
for(j=0; j<ALPH; ++j)
container[i] += (data[i][j] == 0) ? 0 : (- LOG2(data[i][j]) * data[i][j]);
if(container[i] < mini->entropy || mini->entropy == 0)
{
mini->character = i;
mini->entropy = container[i];
}
if(container[i] > maxi->entropy)
{
maxi->character = i;
maxi->entropy = container[i];
}
}
}
double distance(const double data[][ALPH], int indexA, int indexB)
{
int i;
double distance = 0;
for(i=0; i < ALPH; ++i)
distance += sqrt(data[indexA][i] * data[indexB][i]);
return -log(distance);
}
void scan_distance(const double data[][ALPH], AlphabetPair_for_Db *mini, AlphabetPair_for_Db *maxi)
{
int i,j;
double d;
for(i=0; i < ALPH; ++i)
{
for(j= i+1; j<ALPH; ++j)
{
d = distance(data, i, j);
if(maxi->distance < d)
{
maxi->memberA = i;
maxi->memberB = j;
maxi->distance = d;
}
if(mini->distance > d || mini->distance <= 0)
{
mini->memberA = i;
mini->memberB = j;
mini->distance = d; // 冗長!引数つきコンストラクタがほしい。
}
}
}
}
//c++
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#define ALPH 26
#define LENGTH 20
#define AINDEX(c) ((isupper(c)) ? (c) - 'A' : (c) - 'a')
#define LOG2(x) (log10(x) / log10(2.0))
typedef struct _AlphabetPair
{
int former;
int latter;
double probability;
} AlphabetPair;
typedef struct _AlphabetSingle
{
int character;
double entropy;
} AlphabetSingle;
typedef struct _AlphabetTwo
{
int memberA;
int memberB;
double distance;
} AlphabetPair_for_Db;
//縦横で二次元配列を表示
void showCrossTable(const int[][ALPH], int, int);
//P(y when x)を算出
double Py_when_x(const int[][ALPH], int, int);
//上を先に作ったので、これを代入して配列に収めるだけの関数
void set_map_P(const int[][ALPH], double [][ALPH], AlphabetPair *, AlphabetPair *);
//上からエントロピーの算出
void set_map_entropy(const double[][ALPH], double [], AlphabetSingle *, AlphabetSingle *);
//バタチャリヤ距離の算出
double distance(const double [][ALPH], int indexA, int indexB);
//バタチャリヤ距離の最大最小の検出
void scan_distance(const double [][ALPH], AlphabetPair_for_Db *, AlphabetPair_for_Db *);
int main()
{
int i,j,c;
int counter[ALPH][ALPH];
double prob[ALPH][ALPH];
double entropy[ALPH];
char lastCharacter = 0;
AlphabetPair mini_pair = {0,0,1};
AlphabetPair maxi_pair = {0,0,0};
AlphabetSingle mini_ent= {0,0};
AlphabetSingle maxi_ent= {0,0};
AlphabetPair_for_Db mini_dpair = {0,0,-1};
AlphabetPair_for_Db maxi_dpair = {0,0,0};
//init
for( i=0; i < ALPH; ++i)
for(j=0; j < ALPH; ++j)
counter[i][j] = 0;
//get characters
while( (c=getchar()) != EOF)
{
if( isalpha(c) && isalpha(lastCharacter) )
++counter[AINDEX(lastCharacter)][AINDEX(c)];
lastCharacter = c;
}
showCrossTable(counter, ALPH, ALPH);
set_map_P(counter, prob, &mini_pair, &maxi_pair);
printf( "max:x=%d(%c),y=%d(%c),p=%lf\n"
"min:x=%d(%c),y=%d(%c),p=%lf\n"
,maxi_pair.former , maxi_pair.former + 'A'
,maxi_pair.latter , maxi_pair.latter + 'A'
,maxi_pair.probability
,mini_pair.former , mini_pair.former + 'A'
,mini_pair.latter , mini_pair.latter + 'A'
,mini_pair.probability);
set_map_entropy(prob, entropy, &mini_ent, &maxi_ent);
printf( "max:x=%d(%c),entropy=%f bit\n"
"min:x=%d(%c),entropy=%f bit\n"
,maxi_ent.character , maxi_ent.character + 'A'
,maxi_ent.entropy
,mini_ent.character , mini_ent.character + 'A'
,mini_ent.entropy);
scan_distance(prob, &mini_dpair, &maxi_dpair);
printf( "max:x1=%d(%c),x2=%d(%c),distance=%f\n"
"min:x1=%d(%c),x2=%d(%c),distance=%f\n"
,maxi_dpair.memberA , maxi_dpair.memberA + 'A'
,maxi_dpair.memberB , maxi_dpair.memberB + 'A'
,maxi_dpair.distance
,mini_dpair.memberA , mini_dpair.memberA + 'A'
,mini_dpair.memberB , mini_dpair.memberB + 'A'
,mini_dpair.distance);
for(i=0; i<ALPH; ++i)
printf("%2d(%c):%e\n", i, i+'A', distance(prob, i, i));
return 0;
}
void showCrossTable(const int data[][ALPH], int n_x, int n_y)
{
int i,j;
printf(" ");
for(i=0; i<ALPH; ++i)
//printf("%*s%c", 7, "", i+'A');
printf("\t%c",i+'A');
putchar('\n');
for(i=0; i<n_x; ++i)
{
putchar(i+'A');
for(j=0; j<n_y; ++j)
//printf(" %*d", 7, data[i][j]);
printf("\t%d",data[i][j]);
putchar('\n');
}
}
double Py_when_x(const int data[ALPH][ALPH], int x, int y)
{
int i;
int data_x = 0;
for(i=0; i<ALPH; ++i)
data_x += data[x][i];
if(data_x <= 0)
return 0;
return (double)data[x][y] / data_x;
}
void set_map_P(const int data[ALPH][ALPH], double container[][ALPH], AlphabetPair *mini, AlphabetPair *maxi)
{
int i,j;
for(i=0; i<ALPH; ++i)
{
for(j=0; j<ALPH; ++j)
{
container[i][j] = Py_when_x(data, i, j);
if(mini->probability > container[i][j] && container[i][j] > 0)
{
mini->former = i;
mini->latter = j;
mini->probability = container[i][j];
}
if(maxi->probability < container[i][j])
{
maxi->former = i;
maxi->latter = j;
maxi->probability = container[i][j];
}
}
}
}
// dataは今回は確率
void set_map_entropy(const double data[][ALPH], double container[], AlphabetSingle *mini, AlphabetSingle *maxi)
{
int i,j;
for(i=0; i<ALPH; ++i)
{
container[i] = 0;
for(j=0; j<ALPH; ++j)
container[i] += (data[i][j] == 0) ? 0 : (- LOG2(data[i][j]) * data[i][j]);
if(container[i] < mini->entropy || mini->entropy == 0)
{
mini->character = i;
mini->entropy = container[i];
}
if(container[i] > maxi->entropy)
{
maxi->character = i;
maxi->entropy = container[i];
}
}
}
double distance(const double data[][ALPH], int indexA, int indexB)
{
int i;
double distance = 0;
for(i=0; i < ALPH; ++i)
distance += sqrt(data[indexA][i] * data[indexB][i]);
return -log(distance);
}
void scan_distance(const double data[][ALPH], AlphabetPair_for_Db *mini, AlphabetPair_for_Db *maxi)
{
int i,j;
double d;
for(i=0; i < ALPH; ++i)
{
for(j= i+1; j<ALPH; ++j)
{
d = distance(data, i, j);
if(maxi->distance < d)
{
maxi->memberA = i;
maxi->memberB = j;
maxi->distance = d;
}
if(mini->distance > d || mini->distance <= 0)
{
mini->memberA = i;
mini->memberB = j;
mini->distance = d;
}
}
}
}
表示オプション
横に並べて表示:
変化行の前後のみ表示: