C-assign-2008-10-30 - alabama_country @Wiki

#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;
			}
		}
	}
}