1328_电文的翻译

给出若干字符及每个字符对应的权值，请对所给的电文进行翻译。

设字符集及频度如下表：

字符    ' '(空格)  A   B   C   D   E   F   G   H   I   J   K   L   M
频度    186       64  13  22  32  103 21  15  47  57  1   5   32  20

字符    N   O   P   Q   R   S   T   U   V   W   X   Y   Z
频度    57  63  15  1   48  51  80  23  8   18  1   16  1

请根据各字符的出现频率，对这个字符集构造一棵最优二叉树，然后根据编制一套Huffman编码。为了确保最优二叉树的唯一性，规定在构造最优二叉树过程中，较小的做左子树，较大一点的做右子树，相等时，先出现的做左子树。并约定对字符编码时采取“左0右1”的规则。（如果不作以上约定，那么可以生成多棵同构的最优二叉树）

这些准备工作做好之后，你和你的战友（根据电视剧的经验，一般来说是一个异性）被派遣到敌人内部潜伏。由于你们都有这套编码，所以你们的联络方式就是采用相同的编码收发密电。

下面，请对输入的字符串进行编码，并对接收到的密电进行解码。

（说一句题外话，如果你想进一步对电文进行加密，只需把上表的字符次序打乱即可。你甚至可以再搞一个对应表，如O对应A，I对应B... ，但这样一来，可能会失去Huffman编码“最短”的特性）

输入的第一行是一个正整数M，表示有M行字符串（明文）要进行编码。字符都是大写字母，以及空格。

接下来是M行字符。每行字符不超过1000个

接下来一行是一个正整数N，表示有N行密码需要解码。

接下来是N行密码。每行不超过5000个'0'或'1'

请把M行字符串翻译为电文输出，一串电文一行。

接着把N行电文解码为字符串，一串字符一行。

2
ARE YOU HUNGRY
I LOVE YOU
2
1000110100011111110001000101000100101111010001001011111000101011110000110010110011110000111111011001111000110101100000010111101100110011101110100010
01101111011110011100000010111100011100100001111110110011001

1010001001011110001110010000111100010000101111000010010100011
01101111011110011100000010111100011100100001
YES WHERE ARE WE GOING TO HAVE DINNER
I LOVE YOU TOO

Huffman编码详解

Huffman编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉20%~90%。这里考虑的数据指的是字符串序列。要理解Huffman编码，先要理解Huffman树，即最优二叉树，是一类带权路径长度最短的树。

   路径是指从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。

   树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和.

Huffman树是指所有叶子结点的二叉树中带权路径长度最小的二叉树.

   当给定了n个叶子结点的权值后，构造出的最优二叉树的结点数目m就确定了，即m=2n-1 ，所以可用一维结构树组来存储最优二叉树。

#define MAXLEAFNUM 50    /* 最优二叉树中最大叶子数目 */

struct node
{
   char ch; /* 当前结点表示的字符，对于非叶子结点，此域不用 */
   int weight; /* 当前结点的权值 */
   int parent; /* 当前结点的父结点的下标，为0时表示无父结点 */
   int lchild,rchild; /* 当前结点的左，右孩子结点的下标，为0时表示无孩子结点 */
}HuffmanTree[2 * MAXLEAFNUM];

typedef char *HuffmanCode[MAXLEAFNUM + 1]；

/* 创建最优二叉树 */
/* 数组c[0..n-1]和w[0..n-1]存放了n个字符及其概率，构造Huffman树HT */
void createHTree( HuffmanTree HT, char *c, int *w, int n )
{
   int i, s1, s2;
   if (n <= 1)
       return;

   /* 根据n个权值构造n棵只有根结点的二叉树 */
   for (i=1; i<=n; i++)
   {
       HT[i].ch = c[i-1];
       HT[i].weight = w[i-1];
       HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
   }
   for (; i<2*n; ++i)
   {
       HT[i].parent = 0;
       HT[i].lchild = 0;
       HT[i].rchild = 0;
   }
   /* 构造Huffman树 */
   for (i=n+1; i<2*n; i++)
   {
   /* 从HT[1..i-1]中选择parent为0且weight最小的两棵树，其序号为s1和s2 */
   select(HT,i-1,s1,s2);
   HT[s1].parent = i;
   HT[s2].parent = i;
   HT[i].lchild = s1;
   HT[i].rchild = s2;
   HT[i].weight = HT[s1].weight + HT[s2].weight;
   }
}

• 应用Huffman编码
  假设有一个包含100 000个字符的数据文件要压缩存储。各字符在该文件中的出现频度见下表。仅有6种不同字符出现过，字符a出现了45000次。

一个字符编码问题。大小为100000个字符的一个数据文件仅包含字符a~f，每个字符出现的频度如表中所示。如果对每个字符赋予一个三位的编码，则该文件可被编码为300000位。如果利用表中的可变长度编码，该文件可被编码为224000位。

可以用很多种方式来表示这样一个文件。采用固定长度编码，则需要三位二进制数字来表示六个字符：a=000，b=001，…，f=101。这种方法需要300000来对整个原文件编码。

而可变长度编码是对频度高的字符赋以短编码，而对频度低的字符赋以较长一些的编码。表1显示了这种编码，其中一位串0表示a，四位串1100表示f。这种编码方式需要（45*1+13*3+12*3+16*3+9*4+5*4）*1000 = 224000位来表示整个文件，即可压缩掉约25%。这其实就是最优字符编码（Huffman编码）

• 前缀编码

我们这里考虑的编码方案中，没有一个编码是另一个编码的前缀。这样的编码称为前缀编码（或许“无前缀编码“是个更好的名字，但是前缀编码是标准的书面语）。

对任何一种二进制字符编码来说编码总是简单的，这只要将文件中表示每个字符的编码并置起来即可。利用表1的可变长度编码，把包含三个字符的文件abc编成

0 . 101 . 100 = 0 101 100,其中"."表示并置。

在前缀编码中解码也是很方便的。因为没有一个码是其他码的前缀，故被编码文件的开始处的编码是确定的。我们只要识别出第一个编码，将它翻译成原文字符，再对余下的编码文件重复这个解码过程即可。在我们的例子中，可将串001 011 101唯一地分析为0.0.101.1101，因此可解码为aabe。

解码过程需要有一种关于前缀编码的方便表示，使得初始编码可以很容易地被识别出来。有一种表示方法就是叶子为给定字符的二叉树。在这种树中，我们将一个字符的编码解释为从根至该字符的路径，其中0表示"转向左子节点"，1表示"转向右子节点"。如下给出最优二叉树，如下图。

以下给出查找最优二叉树叶子结点编码的算法

typedef char *HuffmanCode[MAXLEAFNUM + 1];

/* n个叶子结点在Huffman树HT中的下标为1~n  */
/* 第i（1<= i <= n）个叶子的编码存放HC[i]中 */
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n)
{
   char *cd;
   int i, start, c, f;
   if (n<=1)
       return;

   /* 分配n个字节的内存，用来存放当前得到的编码 */
   /* n个叶子结点最大的编码长度为n所以分配n个字节 */
   cd = (char*)malloc(n)
   cd[n-1] = ‘\0’;
   for (i=1; i<=n; i++)
   {
       start = n -1;
       for (c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
       /* 从叶子结点开始查找编码
          叶子结点的父结点的左子树为叶子结点，则编码为0
          否则就为父结点的右子树，则编码为1 */
           if (HT[f].lchild = = c) cd[--start] = ‘0’;
           else cd[--start] = ‘1’;
       /* 分配内存，分配内存的字节数为当前得到的字符编码数 */
       HC[i] = (char*)malloc(n-start);
       strcpy(HC[i], &cd[start]);
   }
   free(cd);
}

译码算法为：

   从根结点出发，按二进制位串中的0和1确定是进入左分支还是右分支，当到达叶子结点时译出该叶子对应的字符。数据文件（包含编码）未结束，则回到根结点继续进行上述过程。

   给出如下函数：

/* 利用具有n个叶子结点的最优二叉树（存储在数组HT中）进行译码，叶子的下标为1~n，buff指向数据文件的编码序列 */
void Decoding( HuffmanTree HT, int n, char *buff )
{
   int p = 2*n-1; /* 指向根结点 */
   while (*buff)
   {
       if ((*buff) = = ‘0’) p = HT[p].lchild; /* 进入左分支 */
       else p = HT[p].rchild; /* 进入右分支 */
       /* 到达一个叶子结点 */
       if（HT[p].lchild = = 0 && HT[p].rchild = = 0）
       {
           printf(“%c”, HT[p].ch);
           p = 2*n-1; /* 回到根结点 */
       }
   buff++;
   }
}