首页 > 代码库 > BWT 压缩解压缩算法介绍 poj 1147
BWT 压缩解压缩算法介绍 poj 1147
poj上1147题，
题意：任意一个长度为N的字符串，循环左移一个字符长度，这样形成N个新字符串，将这N个字符串按字典顺序排序，从上到下取得排序后的每行最后一列的的所有字符，求排序后的第一行字符串？
举个简单例子：
原串为： 0 0 0 1 1
那么循环左移排序后的矩阵为：
0 0 0 1 1
0 0 1 1 0
0 1 1 0 0
1 0 0 0 1
1 1 0 0 0
那么我们得到最后列的字符串为: 1 0 0 1 0
现在我们只知道最后列的字符串 1 0 0 1 0，让我们求循环左移排序后的第一列 即： 0 0 0 1 1
嗯，介绍完毕，
原始思路：我们从 10010得到 原串中包含3个0 和 2个1，由于排序后的是字典顺序，我们可以肯定得到第一列的顺序为 0 0 0 1 1（这个需要体会下）。
现在我们知道最后一列L,和第一列F:
F L
0 x x x 1
0 x x x 0
0 x x x 0
1 x x x 1
1 x x x 0
由于所有的串都是左移一个字符得到的，所以我们可以得到如下顺序：10 00 00 11 01
我们把他们按从小到大排序：00 00 01 10 11
我们取排序后的第二个字符组成串： 0 0 1 0 1
没错，这个就是第二列的字符串，以此类推，可以求得所有的列串，那么第一行的字符串就出来了。
嗯，这个算法上是可行的，但是，时间复杂度为O(n^2),
有没有更好的办法呢？答案是肯定的，下面给大家介绍下时间复杂度为O(n)的算法：（网上有许多的介绍，许多描述的都很难懂，我找了半天资料，在百度文库里有BWT的详细介绍地址为：http://wenku.baidu.com/link?url=FbW3XlPlUXLDW_G78Oze5XzynYA2NQyChjLhSo39hR-D5sh9PTphKr8k-J3fjb4NtLTMp1Kib72mLc0EkFoHOa7A8tNJ0_uvmtWgNZG_FKe）
我们设
* M[c]表示字符c在F中的首位置,
* C[i]表示L[i]字符在i位置之前出现过的次数,
* 由此L[i]前一个字符在数组L中的位置可由C[i]+M[L[i]]推出
由于我们只要求第一行的内容，那么i=0,
用上面的例子计算：i=0的前一个字符串在L中的位置按上面公式计算得到：4. 。。。以此类推：所有顺序：L[0 , 3 , 4 , 2 , 1]
那么得到顺序为：1 1 0 0 0
倒过来： 0 0 0 1 1 便是答案；
知道了算法，代码实现起来就非常容易了：
package poj1147;/** * M[c]表示字符c在F中的首位置, * C[i]表示L[i]字符在i位置之前出现过的次数, * 由此L[i]前一个字符在数组L中的位置可由C[i]+M[L[i]]推出 */import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[]args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); int i; int[]a=new int[n]; int[]b=new int[n]; int[]res = new int[n]; for(i=0;i<n;i++){ int value =http://www.mamicode.com/ s.nextInt(); a[i]=value; b[i]=value; } Arrays.sort(b); int I=0; int j=0; while(j<a.length){ res[j]=a[I]; I = getCI(I,a)+getMc(a[I],b); j++; } for(int k=0;k<n;k++){ System.out.print(res[n-k-1]+" "); } } public static int getCI(int n,int []a){ int count=0; for(int i=0;i<n;i++ ){ if(a[i]==a[n]){ count++; } } return count; } public static int getMc(int val,int[]a){ int i; for(i=0;i<a.length;i++){ if(a[i]==val){ break; } } return i; }}