UVa 741 Burrows Wheeler Decoder
题目描述Burrows‑Wheeler\texttt{Burrows‑Wheeler}Burrows‑Wheeler变换BWT\texttt{BWT}BWT是一种用于数据压缩的有效变换。给定一段输入文本SSS长度nnn生成其所有循环左移得到的nnn个字符串按字典序排列成矩阵PPP取最后一列LLL长度nnn以及原输入文本在矩阵PPP中的行号rrr从111开始即构成BWT\texttt{BWT}BWT编码。本题要求实现逆变换给定最后一列LLL和行号rrr恢复出原始文本。输入格式输入包含多个测试实例每个实例两行。第一行为最后一列LLL由大写字母组成不含空格第二行为一个整数rrr表示原输入文本在排序矩阵中的行号。输入以行END和整数0结束该实例不处理。输出格式对于每个实例输出一行即恢复出的原始文本。每个实例的输出之间用空行分隔。样例输入NNBAAA 4 OMOEULCG 1 END 0样例输出BANANA COGUMELO题目分析BWT\texttt{BWT}BWT逆变换的核心是利用最后一列LLL重构出排序矩阵PPP。已知PPP的每一行是原文本的一个循环移位且PPP按字典序排列。因此PPP的第一列FFF就是LLL排序后的结果因为矩阵按行排序第一列自然升序。对于每个字符ccc其在LLL中第kkk次出现在FFF中第kkk次出现位置即为该字符在排序矩阵中的上一列位置即LFLFLF映射。从给定行rrr开始利用LFLFLF映射逐列向左移动即可还原原始文本的字符序列从第一列到最后一列。另一种等价方法反复将LLL的字符插入到已有行的开头并重新排序迭代nnn次即可得到完整的排序矩阵直接取第r−1r-1r−1行即为原文本。由于n≤300n \le 300n≤300该方法的复杂度可接受。解题思路采用迭代重建矩阵的方法具体步骤如下步骤1\texttt{1}1. 读入最后一列LLL和行号rrr若LLL为END且r0r 0r0则终止。步骤2\texttt{2}2. 初始化一个字符串数组rotaterotaterotate包含nnn个空字符串代表矩阵的nnn行。步骤3\texttt{3}3. 循环执行nnn次nnn为LLL的长度将LLL中的每个字符依次插入到rotaterotaterotate中每一行的最前面即当前列。对rotaterotaterotate数组按字典序排序。步骤4\texttt{4}4. 循环结束后rotaterotaterotate即为完整的排序矩阵PPP其中第r−1r-1r−1行000基就是原始文本。步骤5\texttt{5}5. 输出该行字符串并在不同实例之间输出空行。该算法的时间复杂度为O(n2logn)O(n^2 \log n)O(n2logn)空间复杂度O(n2)O(n^2)O(n2)对于n≤300n \le 300n≤300完全可行。代码实现// Burrows Wheeler Decoder// UVa ID: 741// Verdict: Accepted// Submission Date: 2018-03-21// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net//// https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0,row;string message;while(cinmessage){cinrow;if(messageENDrow0)break;intnmessage.length();string rotate[n];for(inti0;in;i){for(intj0;jn;j)rotate[j].insert(rotate[j].begin(),message[j]);sort(rotate,rotaten);}if(cases0)cout\n;coutrotate[row-1]\n;}return0;}总结本题通过反复向每一行前端插入最后一列字符并重新排序逐步还原完整的排序矩阵从而得到原始文本。该方法直观且易于实现虽然时间复杂度略高但n≤300n \le 300n≤300的限制下足以在要求时间内完成。理解BWT\texttt{BWT}BWT的逆变换原理是关键排序矩阵的每一列都可以通过前一列加上排序操作递推得到。该解法展示了BWT\texttt{BWT}BWT可逆性的核心思想是压缩算法中经典问题的良好练习。