compress.java

《算法设计与分析》王晓东编著

public class Compress {
	static final int lmax=256;
	static final int header=11;
	static int m;
	
	public static void compress(int p[],int s[],int L[],int b[])
	{
		int n=p.length-1;
		s[0]=0;
		for (int i=1;i<=n;i++) {
			b[i]=length(p[i]);	/* 计算用多少位二进制数可以表示p[i] */		
			int bmax=b[i];
			s[i]=s[i-1]+bmax;
			L[i]=1;
			for (int j=2;j<=i && j<=lmax;j++) {
				if (bmax<b[i-j+1]) bmax=b[i-j+1];
				if (s[i]>s[i-j]+j*bmax) {
					s[i]=s[i-j]+j*bmax;
					L[i]=j;
				}
			}
			s[i]+=header;
		}
	}
	
	/* 计算最少用几位二进制数可以表示i */
	private static int length(int i)
	{
		int k=1;
		i=i/2;
		while (i>0) {
			k++;
			i=i/2;
		}
		return k;
	}
	
	private static void traceback(int n,int s[],int L[])
	{		
		if (n==0) return;
		traceback(n-L[n],s,L);
		s[m++]=n-L[n];
	}
	
	public static void output(int s[],int L[],int b[])
	{
		int n=s.length-1;
		System.out.println("The optimal value is "+s[n]);
		m=0;
		traceback(n,s,L);
		s[m]=n;		
		System.out.println("Decomposed into "+m+" segments");
		int t=0;
		for (int j=1;j<=m;j++) {
			L[j]=L[s[j]];
			int bmax=0;
			for (int k=1;k<=L[s[j]];k++)
			{
				t++;
				if (b[t]>bmax) bmax=b[t];
			}
			b[j]=bmax;
		}
		for (int j=1;j<=m;j++)
			System.out.println(L[j]+","+b[j]);
	}
	
	public static void main(String[] args) {
		/* 初始化原始图像的象素点灰度值序列,从下标1开始有效 */
		int[] p=new int[]{0,32,16,8,8,8,8,8,8,1,1,1,1,1,1,1,1,1,1,1};
		int n=p.length;
		int[] s=new int[n];
		int[] L=new int[n];
		int[] b=new int[n];
		
		/* 计算最优的压缩方案 */
		compress(p,s,L,b);
		
		/* 输出最优的压缩方案 */
		output(s,L,b);
	}
}