有一段仅由大写字母构成的字符串，根据每个字母出现的频率，对其进行 Hufuman 编码，编码步骤如下:

步骤一:构建频率数据表。

数据表根据字母出现的频率从小到大排序构建。如仅由 A、B、C、D、E、F组成的字符串“ABCDEFABCDEFBDEFBFBFBFBBE”,统计出6个字母各自出现的频率,并按频率升序(频率一样，按字母升序排)排序，排序后得到的频率数据表，如第9题图a所示:

步骤二:构建编码表。

从频率最小开始选择相邻两个频率(若频率相同，取最前面)，将左边的编码设置为“0”，右边的编码设置为“1”。如将第9题图a中序号0对应的频率2编码为0，序号1对应的频率2编码为 1。再将两个频率之和组成新的数据，按照递增顺序插入到频率数据表中，如果两个频率之和与频率数据表中的频率值相同时，放在相同值最后一个值的右边，并将插入位置作为这两个频率对应序号的链接点。例如，将第9题图a中序号0和序号1对应的频率之和4，按递增顺序插入到频率数据表的序号4的位置上，频率数据表中的序号4及后面的数据往后移动，并设置序号0和序号1的链接点为序号 4，序号0和序号1频率的编码设置如第9题图b所示。

第9 题图b 步骤三:重复步骤二，构建出编码表如第 9题图c所示。依次构建后面未设置频率的编码，直到未设置编码的频率仅有一个,

步骤四:构建二叉树。

所有序号的链接关系构成一棵二叉树，如第9题图d所示，圆圈中的数字表示“序号”，圆圈下方的数字表示该序号对应的编码，圆圈旁边的字母表示该序号对应的字母。

步骤五:Hufinan 编码。

每个字母对应的 Huffman 编码为从树根沿最短路径到达叶子节点所经过的“0”、“1”编码串。如字母“℃”的编码为“001”。根据此方法，可以用每个字母的 Hufnan 编码对原字符串进行无损压缩。对于仅由单个字母组成的字符串，比如“AAA”，则该字母的 Huffman 编码为“0”

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com