UVa 283 Compress

题目分析

本题要求实现一种特殊的变长编码压缩方法。在传统ASCII\texttt{ASCII}ASCII编码中，每个字符使用固定的888位二进制数表示。为了进一步压缩数据，我们希望给出现频率较高的字符分配较短的编码，给出现频率较低的字符分配较长的编码。

然而，变长编码会引入一个严重的问题：解码时无法确定字符的边界。例如，若a编码为11，e编码为1111，那么比特序列111111既可以解释为ae，也可以解释为ea或aaa。

为了解决这个问题，题目采用了一种特殊的编码规则：

1. 所有需要编码的字符按照出现频率从高到低排序。
2. 编码采用类似前缀码的结构，但扩展方式特殊：当某一长度的编码全部使用完毕后，最后一个编码作为“扩展标记”，表示后续还有更多位。
3. 具体的编码分配过程如下：
   • 长度为iii的编码共有2i2^i2i种可能。
   • 从最长的可用长度开始，实际上题目是从长度111开始分配，每次使用当前长度下的一个编码给一个字符。
   • 如果当前长度下的可用编码数大于等于剩余待编码字符数，则直接分配完毕。
   • 否则，最后一个编码作为扩展标记，剩余字符继续用更长的编码表示。

题目给出的例子中，a、e、i、o、u、y六个字符被编码为：

• 长度222的编码：a=00，e=01，i=10
• 最后一个长度222的编码11作为扩展标记
• 长度444的编码：o=1100，u=1101，y=1110
• 1111空闲

解题思路

核心问题

给定一段文本，统计其中不同字符的出现频率，按照上述编码规则，求编码后文本的最小总比特数。

关键观察

1. 频率顺序：为了最小化总比特数，出现频率高的字符应该获得尽可能短的编码，因此需要将字符按频率从高到低排序。

2. 编码分配规则：设共有mmm个不同字符。我们按长度递增的顺序分配编码：

   • 长度为111的编码有21=22^1=221=2个：0和1。
   • 若m>1m > 1m>1，则最后一个编码1必须作为扩展标记，实际只能分配111个编码。
   • 剩余字符进入长度为222的编码空间，但注意扩展标记占用了一个编码空间。

   更一般地，设当前编码长度为lenlenlen，则该长度下可用的编码数量为2len2^{len}2len减去之前已分配的编码数。但题目描述的规则实际上是另一种理解：

   从长度i=1i=1i=1开始，设剩余待分配字符数为remainremainremain：

   • 如果2i−1≥remain2^i - 1 \ge remain2i−1≥remain，则所有剩余字符都可以用长度为iii的编码分配（每个字符独占一个编码，且不需要扩展标记）。
   • 否则，只能分配2i−12^i - 12i−1个编码给2i−12^i - 12i−1个字符，最后一个编码作为扩展标记，剩余字符进入更长的编码分配。

3. 为什么是2i−12^i - 12i−1：长度为iii的二进制串共有2i2^i2i个。其中111个必须作为“扩展标记”保留，所以实际可分配的只有2i−12^i - 12i−1个。

4. 实际分配过程：排序后的字符按频率从高到低，依次分配尽可能短的编码。对于频率列表counter[0...m-1]（降序），我们需要决定：

   • 有多少字符获得长度为111的编码
   • 有多少字符获得长度为222的编码
   • ……

   而编码长度的分布必须满足：对于每个长度iii，分配的数量不超过2i−12^i - 12i−1，并且长度递增。

算法设计

本题使用DFS\texttt{DFS}DFS回溯搜索所有可能的编码长度分配方案，计算每种方案的总比特数，取最小值。

状态定义：

• prefix：当前已经分配的编码长度之和（即已经用于表示前缀的比特数）
• index：当前已经处理到频率列表的第index个字符（从000开始）
• bits：到目前为止已经计算的总比特数

为什么搜索深度有限

由于ASCII\texttt{ASCII}ASCII字符一共只有256256256种可能，因此最多有256256256个不同字符。编码长度从111开始，每次扩展增加当前长度，但实际递归中prefix累计的是当前路径上所有“扩展标记”的长度之和。当prefix超过某个上限时，搜索会自动剪枝（因为next_bits已经超过当前最优解）。

频率统计与排序

首先统计输入文本中每个字符的出现频率，然后按频率降序排序。频率高的字符优先获得短编码，这符合贪心思想。由于搜索会遍历所有可能的分配方案，最终得到的一定是最优解。

复杂度分析

• 最多有256256256个不同字符。
• 编码长度最大为888，因为28=2562^8=25628=256已经足够覆盖所有ASCII\texttt{ASCII}ASCII字符（实际上在扩展标记的累积下，编码长度可能超过888，但每层递归prefix增长，很快剪枝）。
• 搜索树的深度有限，分支因子为888，最坏情况下的状态数可控。

代码实现

// Compress// UVa ID: 283// Verdict: Accepted// Submission Date: 2016-06-03// UVa Run Time: 0.250s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<int>counter,codes(10);intminimalBits;// 深度优先搜索所有可能的编码长度分配方案// prefix: 当前已经分配的编码长度之和（即扩展标记累积的比特数）// index: 当前已经处理到频率列表中的第几个字符// bits: 到目前为止已经计算的总比特数voidbacktrack(intprefix,intindex,intbits){// 尝试所有可能的编码长度，从1到8for(inti=1;i<=8;i++){// 如果当前长度下的编码总数（2^i）足以覆盖所有剩余字符if(index+codes[i]>=counter.size()){intnext_bits=bits;// 剩余字符都使用长度为 (prefix + i) 的编码for(intj=index;j<counter.size();j++)next_bits+=counter[j]*(prefix+i);// 更新最优解minimalBits=min(minimalBits,next_bits);}else{// 剩余字符数超过当前长度的编码总数// 只能分配 (codes[i] - 1) 个字符给当前长度// 最后一个编码作为扩展标记，不分配给实际字符intnext_index=index,next_bits=bits;for(intj=1;j<codes[i];j++)next_bits+=counter[next_index++]*(prefix+i);// 剪枝：如果当前累计比特数已经不小于已知最优解，则不再继续搜索if(next_bits<minimalBits)backtrack(prefix+i,next_index,next_bits);}}}intmain(intargc,char*argv[]){intcases;// 预处理长度为 i 的编码总数，即 2^ifor(inti=1;i<=8;i++)codes[i]=pow(2,i);string line;getline(cin,line);cases=stoi(line);while(cases--){intn;getline(cin,line);n=stoi(line);// 统计每个字符的出现频率map<char,int>frequency;for(inti=1;i<=n;i++){getline(cin,line);for(inti=0;i<line.length();i++)frequency[line[i]]++;}// 将频率提取到 vector 中并按降序排序// 频率高的字符优先获得短编码counter.clear();for(autoit=frequency.begin();it!=frequency.end();it++)counter.push_back((*it).second);sort(counter.begin(),counter.end(),greater<int>());// 初始化最优解为最大值，开始深度优先搜索minimalBits=numeric_limits<int>::max();backtrack(0,0,0);cout<<minimalBits<<endl;}return0;}