算术编码压缩算法

        算术编码，是图像压缩的主要算法之一。 是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤ n < 1.0)的小数n。

    工作原理：

在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。

例: 对一个简单的信号源进行观察，得到的统计模型如下：

60% 的机会出现符号 中性

20% 的机会出现符号 阳性

10% 的机会出现符号 阴性

10% 的机会出现符号 数据结束符. (出现这个符号的意思是该信号源'内部中止'，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了。)

算术编码可以处理的例子不止是这种只有四种符号的情况，更复杂的情况也可以处理，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。

编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据：

下一个要编码的符号

当前的区间(在编第一个符号之前，这个区间是[0,1), 但是之后每次编码区间都会变化)

编码器将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。

例: 对于前面提出的4符号模型:

中性对应的区间是 [0, 0.6)

阳性对应的区间是 [0.6, 0.8)

阴性对应的区间是 [0.8, 0.9)

数据结束符对应的区间是 [0.9, 1)

当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和使用的模型参数即可以解码重建得到该符号序列。

实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。在实用中，只要传输足够的该小数足够的位数(不论几进制)，以保证以这些位数开头的所有小数都位于结果区间就可以了。

例: 下面对使用前面提到的4符号模型进行编码的一段信息进行解码。编码的结果是0.538(为了容易理解，这里使用十进制而不是二进制；我们也假设我们得到的结果的位数恰好够我们解码。下面会讨论这两个问题)。

像编码器所作的那样我们从区间[0,1)开始，使用相同的模型，我们将它分成编码器所必需的四个子区间。分数0.538落在NEUTRAL坐在的子区间[0,0.6)；这向我们提示编码器所读的第一个符号必然是NEUTRAL，这样我们就可以将它作为消息的第一个符号记下来。

然后我们将区间[0,0.6)分成子区间：

中性 的区间是 [0, 0.36) -- [0, 0.6) 的 60%

阳性 的区间是 [0.36, 0.48) -- [0, 0.6) 的 20%

阴性 的区间是 [0.48, 0.54) -- [0, 0.6) 的 10%

数据结束符 的区间是 [0.54, 0.6). -- [0, 0.6) 的 10%

我们的分数 .538 在 [0.48, 0.54) 区间；所以消息的第二个符号一定是NEGATIVE。

我们再一次将当前区间划分成子区间：

中性 的区间是 [0.48, 0.516)

阳性 的区间是 [0.516, 0.528)

阴性 的区间是 [0.528, 0.534)

数据结束符 的区间是 [0.534, 0.540).

我们的分数 .538 落在符号 END-OF-DATA 的区间；所以，这一定是下一个符号。由于它也是内部的结束符号，这也就意味着编码已经结束。（如果数据流没有内部结束，我们需要从其它的途径知道数据流在何处结束——否则我们将永远将解码进行下去，错误地将不属于实际编码生成的数据读进来。）

同样的消息能够使用同样短的分数来编码实现如 .534、.535、.536、.537或者是.539，这表明使用十进制而不是二进制会带来效率的降低。这是正确的是因为三位十进制数据能够表达的信息内容大约是9.966位；我们也能够将同样的信息使用二进制分数表示为.10001010（等同于0.5390625），它仅需8位。这稍稍大于信息内容本身或者消息的信息熵，大概是概率为0.6%的 7.361位信息熵。（注意最后一个0必须在二进制分数中表示，否则消息将会变得不确定起来。）

算法代码（java）：

    

import java.util.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.*;
/**
 * 算术编码：无损数据压缩方法，将整个输入的消息编码为一个数，
 * 一个满足(0.0<=n<1.0)的小数n。
 * 编码只有三块数据需要考虑：下一个需要编码的符号、当前时间间隔、各符号的概率
 * 
 * 1.首先的准备工作——按照各信源信号好出现的频率，将[0, 1)这个区间分成若干段，那么每个信号源就会有自己对应的区间了；
 * 2.将[0, 1)这个区间设置为初始间隔；
 * 3.然后编码过程就是，按照待处理的信号，一个一个信号源读入，每读入一个信号，就将该信号源在[0, 1)上的范围等比例的缩小到最新得到的间隔中。
 * 4.然后依次迭代，不断重复进行步骤3，直到最后信号中的信源信号全部读完为止；
 * @author librah
 *
 */
public class ArithmeticCoding extends JFrame implements ActionListener{

	private static String str=null;
	//每个字符出现的频率
	private static TreeMap<Character, Integer> hm=null;
	//将每个字符固定频率
	private static TreeMap<Character, Double> hm1=null;
	//计算每个字符区间的最小值
	private static TreeMap<Character, Double> hm_min=null;
	//计算每个字符区间的最大值
	private static TreeMap<Character, Double> hm_max=null;
	private static int allCounts=0;
	//算术编码(小数形式)
	private static double code=0.0;
	//算术解码(字符串)
	private static String decode="";
	private JTextField jtf=null;
	private JTextField jtf2=null;
	private JButton jb2=null;
	private JTextField jtf3=null;
	private JButton jb3=null;
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		new ArithmeticCoding();
	}
	public ArithmeticCoding()
	{
		hm=new TreeMap<Character,Integer>();
		hm1=new TreeMap<Character,Double>();
		hm_min=new TreeMap<Character,Double>();
		hm_max=new TreeMap<Character,Double>();
		
		JLabel jl=new JLabel("请输入编码字符串:");
		jtf=new JTextField(20);
		JPanel jp1=new JPanel();
		jp1.add(jl);
		jp1.add(jtf);
		
		JLabel jl2=new JLabel("编码：");
		jtf2=new JTextField(20);
		jb2=new JButton("编码");
		jb2.addActionListener(this);
		JPanel jp2=new JPanel();
		jp2.add(jl2);
		jp2.add(jtf2);
		jp2.add(jb2);
		
		
		JLabel jl3=new JLabel("解码：");
		jtf3=new JTextField(20);
		jb3=new JButton("解码");
		jb3.addActionListener(this);
		JPanel jp3=new JPanel();
		jp3.add(jl3);
		jp3.add(jtf3);
		jp3.add(jb3);
		
		JPanel jp=new JPanel();
		jp.add(jp1);
		jp.add(jp2);
		jp.add(jp3);
		
		this.add(jp);
		this.setSize(400,300);
		this.setLocation(500,200);
		this.setTitle("算术压缩编码");
		this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		this.setVisible(true);
	}
	//统计各字符出现的频率
	public static void Count()
	{
		for(int i=0;i<str.length();i++)
		{
			char c=str.charAt(i);
			if(!hm.containsKey(c))
				hm.put(c, 1);
			else
			{
				int count=hm.get(c);
				hm.replace(c, ++count);
			}
		}
	}
	//输出字符的频率
	public static void Print()
	{
		for(char c:hm.keySet())
		{
			int count=hm.get(c);
			System.out.println(c+":"+count);
			
		}
	}
	//统计各字符的概率区间
	public static void MinMax(double min,double max)
	{
		//区间差
		double dec=max-min;
		int counts=0;
		for(char c:hm.keySet())
		{
			int count=hm.get(c);
			hm_min.put(c,min+((double)counts/allCounts)*dec);
			counts+=count;
			hm_max.put(c,min+((double)counts/allCounts)*dec);
			//System.out.println(c+":["+hm_min.get(c)+","+hm_max.get(c)+")");
		}
	}
	//算术编码(缩小概率区间)
	public static void Encoding()
	{
		double min=0;
		double max=1.0;
		for(int i=0;i<allCounts;i++)
		{
			char c=str.charAt(i);
			MinMax(min, max);
			code=hm_min.get(c);
			//不断修改其概率区间
			min=hm_min.get(c);
			max=hm_max.get(c);	
		}
		//生成指定范围内的随机数
		//code=Math.random()*(max-min)+min;
		System.out.println("Encode:"+code);
	}
	//算术解码
	public static void Decoding()
	{
		double min=0;
		double max=1.0;
		for(int i=0;i<allCounts;i++)
		{
			MinMax(min, max);
			for(char c:hm.keySet())
			{
				if(code>=hm_min.get(c)&&code<hm_max.get(c))
				{
					decode+=c;
					//不断修改其概率区间
					min=hm_min.get(c);
					max=hm_max.get(c);
				}
			}
			MinMax(min, max);
			
		}
		System.out.println("Decode:"+decode);
	}
	@Override
	public void actionPerformed(ActionEvent e) {
		// TODO 自动生成的方法存根
		str=jtf.getText().trim();
		hm=new TreeMap<Character,Integer>();
		hm1=new TreeMap<Character,Double>();
		hm_min=new TreeMap<Character,Double>();
		hm_max=new TreeMap<Character,Double>();
		allCounts=str.length();
		decode="";
		Count();
		if(e.getSource()==jb2)
		{
			jtf2.setText("");
			Encoding();
			jtf2.setText(code+"");
		}else if(e.getSource()==jb3)
		{
			Decoding();
			jtf3.setText(decode+"");
		}
	}
}

结果实现：