課本為西安電子科技大學《信息論與編碼理論》第二版铣减。
算數(shù)編碼兩個關(guān)鍵遞推公式
實現(xiàn)如下：
/**The class is used to Arithmeti Coding.
*tool：notepad++，jdk 1.8
*Date: 2018/5/31
*@author? JFLIU
*@version 1.0
*說明：由于時間原因脚作，沒有嚴格異常檢查徙歼，輸入合法性檢查，程序只能雙字節(jié)輸入變量（例如鳖枕，a1，a2桨螺，b1等）宾符。如果是二元編碼，請用a1灭翔，a2（不要出現(xiàn)a0）等代替0魏烫，1。一個遺憾是肝箱，不能想到一個合理的方式解決尾數(shù)截斷的進一哄褒。因為float，double在計算機的表示（IEEE 754標準）本人并不懂煌张。對于P(ui),F(ui)呐赡，沒有采用有理數(shù)（Java中沒有），編寫需要時間骏融，故直接用小數(shù)了链嘀。注意：本例中向量用下劃線表示了。
*/
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("請輸入字符集個數(shù): ");
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);
}
//分布函數(shù)
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程序運行結(jié)果
可見編碼為10001101110100误趴。
習題3.12
由于截斷霹琼，實際編碼為0101100111101。即最后一位應該補上一位。
