gencode.c

/*
 * ハフマン符号化アルゴリズムの実装.
 *
 * Author:  hidetake
 * Time-stamp:  <03/05/22 20:17:31 hidetake>
 */
#include <stdio.h>
#include <malloc.h>

//#define  SHOW_TRACE

/* トレース表示の切替え. */
#ifdef SHOW_TRACE
#define  TRACE(i)    (i)
#else
#define  TRACE(i)
#endif


/* 情報源. */
struct information_source {
  int n;              /* 情報源記号数. */
  
  char **a;           /* 情報源記号の文字列. [n][width] */
  float *p;           /* 出現確率. [2n-1] */
  
  int *node_table;    /* ノード変換テーブル. [2n-1] */
  int *link_l;        /* 隣接する第1ノード. [n-1] */
  int *link_r;        /* 隣接する第2ノード. [n-1] */
};


/* debug. */
void show_table( struct information_source *infs )
{
  int i, n = infs->n;

  for( i = 0; i < 2*n - 1; i++ )
    printf( "p[%d]\t= %f\n", i, infs->p[i] );
  putchar( '\n' );

  for( i = 0; i < 2*n - 1; i++ )
    printf( "node_table[%d]\t= %d\n", i, infs->node_table[i] );
  putchar( '\n' );

  for( i = 0; i < n - 1; i++ )
    printf( "link_l[%d]\t= %d, link_r[%d]\t= %d\n",
	    i, infs->link_l[i], i, infs->link_r[i] );
  putchar( '\n' );
}


/* exchange variable. */
inline void swapf( float *a, float *b )
{
  float t = *a;
  *a = *b, *b = t;
}

inline void swapi( int *a, int *b )
{
  int t = *a;
  *a = *b, *b = t;
}


/* 配列から最小の2つを探す. pmin1 < pmin2 */
void find_min2( float a[], int n, int *pmin1, int *pmin2 )
{
  int m1, m2, i;

  if( a[0] < a[1] )
    m1 = 0, m2 = 1;
  else
    m1 = 1, m2 = 0;
  
  for( i = 2; i < n; i++ )
    if( a[i] < a[m1] )
      m2 = m1, m1 = i;
    else if( a[i] < a[m2] )
      m2 = i;
  
  if( m1 < m2 )
    *pmin1 = m1, *pmin2 = m2;
  else
    *pmin1 = m2, *pmin2 = m1;
}


/* 符号木の生成. */
void build_tree( struct information_source *infs )
{
  int b, i, j;
  int n = infs->n, e = n;
  
  TRACE( printf( "***  n = %d,e = %d\n", n, e ) );
  TRACE( show_table( infs ) );
  
  for( b = n - 1; b > 0; b--, e++ ) {
    /* 最小の2数を求める. */
    find_min2( infs->p, b + 1, &i, &j );
    
    /* ノード間にリンクを張る. */
    infs->link_l[e - n] = infs->node_table[i];
    infs->link_r[e - n] = infs->node_table[j];
    TRACE( printf( "***  l[%d] ← %d, r[%d] ← %d\n",
		   e, infs->node_table[i], e, infs->node_table[j] ) );
    
    /* 整列. */
    infs->p[e] = infs->p[i];
    infs->node_table[e] = infs->node_table[i];
    TRACE( printf( "***  p[%d] ← p[%d], t[%d] ← %d\n", e, i, e, i ) );
    
    infs->p[i] += infs->p[j];
    infs->node_table[i] = e;
    TRACE( printf( "***  p[%d] +← p[%d], t[%d] ← %d\n", i, j, i, e ) );
    
    /* 最後尾要素の入れ替え. */
    if( j != b ) {
      swapf( &infs->p[j], &infs->p[b] );
      swapi( &infs->node_table[j], &infs->node_table[b] );
      TRACE( printf( "***  p[%d] ←→ p[%d]\n", j, b ) );
    }
    
    TRACE( printf( "***  b = %d, i = %d, j = %d, e = %d\n", b, i, j, e ) );
    TRACE( show_table( infs ) );
  }
}


/* 情報源定義の読み込み. */
int create_information_source( struct information_source *infs, char filename[] )
{
  int n, width, i;
  
  /* ファイルを開く. */
  FILE *fp = fopen( filename, "r" );
  if( !fp )
    return 0;
  
  /* ヘッダにある個数を読み込む. */
  if( !fscanf( fp, "%d", &n ) )
    return 0;
  infs->n = n;
  
  /* ヘッダにある記号文字数を読み込む. */
  if( !fscanf( fp, "%d", &width ) )
    return 0;
  width++;
  
  /* 配列の生成. */
  infs->a = (char**)malloc( n * sizeof(char*) );
  infs->p = (float*)malloc( (2*n - 1) * sizeof(float) );
  
  /* 定義を読み込む. */
  for( i = 0; i < n; i++ ) {
    infs->a[i] = (char*)malloc( width * sizeof(char) );
    fscanf( fp, " %s %f", infs->a[i], &infs->p[i] );
  }
  
  fclose( fp );

  /* 配列の生成. */
  infs->node_table = (int*)malloc( (2*n - 1) * sizeof(int) );
  infs->link_l = (int*)malloc( (n - 1) * sizeof(int) );
  infs->link_r = (int*)malloc( (n - 1) * sizeof(int) );
  
  for( i = 0; i < n; i++ )
    infs->node_table[i] = i;
  
  return 1;
}


/* 符号語の表示. */
static void show_node( struct information_source *infs, int e, char buf[], int depth )
{
  int n = infs->n, l = infs->link_l[e - n], r = infs->link_r[e - n];
  
  TRACE( printf( "***  e = %d, l = %d, r = %d, buf = \"%s\"\n", e, l, r, buf ) );
  
  /* 葉に到達した場合は表示. */
  if( e < n ) {
    printf( "%s\t%s\n", infs->a[e], buf );
    return;
  }
  
  buf[depth] = '1';
  show_node( infs, l, buf, depth + 1 );
  buf[depth] = '\0';
  
  buf[depth] = '0';
  show_node( infs, r, buf, depth + 1 );
  buf[depth] = '\0';
}

void show_code_table( struct information_source *infs )
{
  int n = infs->n;
  char *code_string = (char*)calloc( n, sizeof(char) );
  
  show_node( infs, n*2 - 2, code_string, 0 );
}


int main( int argc, char *argv[] )
{
  struct information_source infs;
  
  if( argc != 2 ) {
    fprintf( stderr, "使い方: %s 情報源の定義ファイル\n", argv[0] );
    return 1;
  }
  
  /* 情報源の定義を読み込む. */
  if( !create_information_source( &infs, argv[1] ) ) {
    fprintf( stderr, "%s: ファイル %s から情報源定義を読み込めません.\n", argv[0], argv[1] );
    return 1;
  }
  
  /* 符号木の生成. */
  build_tree( &infs );
  
  /* 符号語の表示. */
  show_code_table( &infs );
  
  return 0;
}