题目分析本题要求实现一种特殊的变长编码压缩方法。在传统ASCII\texttt{ASCII}ASCII编码中每个字符使用固定的888位二进制数表示。为了进一步压缩数据我们希望给出现频率较高的字符分配较短的编码给出现频率较低的字符分配较长的编码。然而变长编码会引入一个严重的问题解码时无法确定字符的边界。例如若a编码为11e编码为1111那么比特序列111111既可以解释为ae也可以解释为ea或aaa。为了解决这个问题题目采用了一种特殊的编码规则所有需要编码的字符按照出现频率从高到低排序。编码采用类似前缀码的结构但扩展方式特殊当某一长度的编码全部使用完毕后最后一个编码作为“扩展标记”表示后续还有更多位。具体的编码分配过程如下长度为iii的编码共有2i2^i2i种可能。从最长的可用长度开始实际上题目是从长度111开始分配每次使用当前长度下的一个编码给一个字符。如果当前长度下的可用编码数大于等于剩余待编码字符数则直接分配完毕。否则最后一个编码作为扩展标记剩余字符继续用更长的编码表示。题目给出的例子中a、e、i、o、u、y六个字符被编码为长度222的编码a00e01i10最后一个长度222的编码11作为扩展标记长度444的编码o1100u1101y11101111空闲解题思路核心问题给定一段文本统计其中不同字符的出现频率按照上述编码规则求编码后文本的最小总比特数。关键观察频率顺序为了最小化总比特数出现频率高的字符应该获得尽可能短的编码因此需要将字符按频率从高到低排序。编码分配规则设共有mmm个不同字符。我们按长度递增的顺序分配编码长度为111的编码有2122^12212个0和1。若m1m 1m1则最后一个编码1必须作为扩展标记实际只能分配111个编码。剩余字符进入长度为222的编码空间但注意扩展标记占用了一个编码空间。更一般地设当前编码长度为lenlenlen则该长度下可用的编码数量为2len2^{len}2len减去之前已分配的编码数。但题目描述的规则实际上是另一种理解从长度i1i1i1开始设剩余待分配字符数为remainremainremain如果2i−1≥remain2^i - 1 \ge remain2i−1≥remain则所有剩余字符都可以用长度为iii的编码分配每个字符独占一个编码且不需要扩展标记。否则只能分配2i−12^i - 12i−1个编码给2i−12^i - 12i−1个字符最后一个编码作为扩展标记剩余字符进入更长的编码分配。为什么是2i−12^i - 12i−1长度为iii的二进制串共有2i2^i2i个。其中111个必须作为“扩展标记”保留所以实际可分配的只有2i−12^i - 12i−1个。实际分配过程排序后的字符按频率从高到低依次分配尽可能短的编码。对于频率列表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因为282562^825628256已经足够覆盖所有ASCII\texttt{ASCII}ASCII字符实际上在扩展标记的累积下编码长度可能超过888但每层递归prefix增长很快剪枝。搜索树的深度有限分支因子为888最坏情况下的状态数可控。代码实现// Compress// UVa ID: 283// Verdict: Accepted// Submission Date: 2016-06-03// UVa Run Time: 0.250s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintcounter,codes(10);intminimalBits;// 深度优先搜索所有可能的编码长度分配方案// prefix: 当前已经分配的编码长度之和即扩展标记累积的比特数// index: 当前已经处理到频率列表中的第几个字符// bits: 到目前为止已经计算的总比特数voidbacktrack(intprefix,intindex,intbits){// 尝试所有可能的编码长度从1到8for(inti1;i8;i){// 如果当前长度下的编码总数2^i足以覆盖所有剩余字符if(indexcodes[i]counter.size()){intnext_bitsbits;// 剩余字符都使用长度为 (prefix i) 的编码for(intjindex;jcounter.size();j)next_bitscounter[j]*(prefixi);// 更新最优解minimalBitsmin(minimalBits,next_bits);}else{// 剩余字符数超过当前长度的编码总数// 只能分配 (codes[i] - 1) 个字符给当前长度// 最后一个编码作为扩展标记不分配给实际字符intnext_indexindex,next_bitsbits;for(intj1;jcodes[i];j)next_bitscounter[next_index]*(prefixi);// 剪枝如果当前累计比特数已经不小于已知最优解则不再继续搜索if(next_bitsminimalBits)backtrack(prefixi,next_index,next_bits);}}}intmain(intargc,char*argv[]){intcases;// 预处理长度为 i 的编码总数即 2^ifor(inti1;i8;i)codes[i]pow(2,i);string line;getline(cin,line);casesstoi(line);while(cases--){intn;getline(cin,line);nstoi(line);// 统计每个字符的出现频率mapchar,intfrequency;for(inti1;in;i){getline(cin,line);for(inti0;iline.length();i)frequency[line[i]];}// 将频率提取到 vector 中并按降序排序// 频率高的字符优先获得短编码counter.clear();for(autoitfrequency.begin();it!frequency.end();it)counter.push_back((*it).second);sort(counter.begin(),counter.end(),greaterint());// 初始化最优解为最大值开始深度优先搜索minimalBitsnumeric_limitsint::max();backtrack(0,0,0);coutminimalBitsendl;}return0;}
