算术编码Java实现

课本为西安电子科技大学《信息论与编码理论》第二版。

算术编码两个关键递推公式

实现如下：

/**The class is used to Arithmeti Coding.

    *tool：notepad++，jdk 1.8

    *Date: 2018/5/31

    *@author  JFLIU

    *@version 1.0

    *说明：由于时间原因，没有严格异常检查，输入合法性检查，程序只能双字节输入变量（例如，a1，a2，b1等）。如果是二元编码，请用a1，a2（不要出现a0）等代替0，1。一个遗憾是，不能想到一个合理的方式解决尾数截断的进一。因为float，double在计算机的表示（IEEE 754标准）本人并不懂。对于P(ui),F(ui)，没有采用有理数（Java中没有），编写需要时间，故直接用小数了。注意：本例中向量用下划线表示了。

*/

import java.util.Scanner;

import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

//随机变量类

class RandomVariable {

    private double possibility = 0;

    private String randomVariableName = null;

RandomVariable() {

}

RandomVariable(double possibility, String randomVariableName) {

    this.possibility = possibility;

    this.randomVariableName = randomVariableName;

}

public void setPossibility(double possibility) {

    this.possibility = possibility;

}

public void setRandomVaribleName(String randomVariableName) {

    this.randomVariableName = randomVariableName;

}

public void setRandomVarible(String randomVariableName, double possibility) {

    this.randomVariableName = randomVariableName;

    this.possibility = possibility;

}

public double getPossibility() {

    return this.possibility;

}

public String getRandomVaribleName() {

    return this.randomVariableName;

}

}

public class ArithmetiCoding {

    private static int num = 0;

    private static double p_ui = 1.f;

    private static double p_uiAdd1 = 0.f;

    private static double puiAdd1 = 0.f;

    private static double f_ui = 0.f;

    private static double f_uiAdd1 = 0.f;

    private static double fuiAdd1 = 0.f;

    private static int n_ui = 0;

    private static RandomVariable[] randomVariable = null;

    private static int theNumOfCharacterSet = 0;

    private static List  list = new  ArrayList();

public static void main(String args[]) {

    Scanner in = new Scanner(System.in);

    System.out.print("请输入字符集个数: ");

    try {

        num = in.nextInt();

        if(num <= 0) {

            System.out.println("输入值应该大约0！");

            System.exit(0);

        }

        } catch(Exception e) {

            System.out.println("输入含有非法字符！");

            System.exit(0);

        }

    inputFunction(num);

    input();

    }

public static void inputFunction(int num) {

    randomVariable = new RandomVariable[num];

    Scanner in = new Scanner(System.in);

    for(int i=0; i < randomVariable.length; i++)
        randomVariable[i]=new RandomVariable();


    for(int i = 0; i < num; i++) {

        System.out.print("请输入字符" + (i+1) +"及其概率: ");
        randomVariable[i].setRandomVarible(in.next(),in.nextDouble());

    list.add(randomVariable[i]);

    }

}

public static void input() {

    int index = 0;

    String temp = "0.";

    Scanner in = new Scanner(System.in);

    System.out.print("信源序列，以逗号分割: ");

    String str = in.nextLine();

        String[] splitstr=str.split(",");

    System.out.println();

    System.out.println("序号\tui\tP(ui)\t\tF(ui)\t\tn(ui)\tS");

    System.out.println((index++) + "  \t空\t1  \t\t 0  \t\t 0  \t");

    for(int i = 0;i < splitstr.length; i++){

        fuiAdd1 = distributionFunction(splitstr[i]);

        f_uiAdd1Function();

            puiAdd1 = list.get(index(splitstr[i])-1).getPossibility();

        p_uiAdd1Function();

        n_ui = (int)(Math.ceil(-1*Math.log(p_uiAdd1)/Math.log(2)));

        double binary = f_uiAdd1;

        for(int j = 0; j < n_ui; j++) {

            binary *= 2;

            temp += (int)binary;

            binary = binary - (int)binary;

        }

    System.out.println((index++)+"\t"+splitstr[i]+"\t"+String.format("%-12s",p_uiAdd1)+"\t"+String.format("%-10s",f_uiAdd1)+"\t"+n_ui+"\t"+temp);

    f_ui = f_uiAdd1;

    p_ui = p_uiAdd1;

    temp = "0.";

        }

}

public static int index(String randomVariableName) {

    String temp = "";

    for(int i = 1; i < randomVariableName.length(); i++) {

        temp += randomVariableName.charAt(i);

    }

    return Integer.parseInt(temp);

}

//分布函数

public static double distributionFunction(String randomVariableName) {

    double possibilityDistribution = 0.f;

    for(int i = 0; i < index(randomVariableName) - 1; i++) {

        possibilityDistribution += list.get(i).getPossibility();

    }

    return possibilityDistribution;

}

//递推公式

public static void p_uiAdd1Function() {

    p_uiAdd1 = p_ui * puiAdd1;

}

public static void f_uiAdd1Function() {

    f_uiAdd1 = f_ui + p_ui * fuiAdd1;

}

}

课本P65例3.4.3程序运行结果

可见编码为10001101110100。

习题3.12

由于截断，实际编码为0101100111101。即最后一位应该补上一位。
简书-算术编码java实现