Android:香农

一款可译用来统计信息熵,进行二元香农、诺顿、哈夫曼编码,以及判断分组码是否唯一可译的Android APP。

统计信息熵

信息指的是各个事物运动的状态及状态变化的方式,它是使认识主体对某一事物的未知性或不确定性减少的有用知识。其基本概念就在于它的不确定性,任何已确定的事物都不含有信息。

香农(C.E.Shannon)提出的狭义信息论中,给出了一种信息量的度量方式,即信息熵(Information Entropy)。在热力学中,“熵”是用来表示分子状态混乱程度的物理量。香农把这个词借用过来,用于描述信源的不确定度。

某个信源发出的符号通常可以根据各种符号出现的概率来度量。根据信息的定义,概率大,出现的机会多,不确定性小,也就是包含的信息量小;概率小,出现的机会少,不确定性大,包含的信息量反而更多。由此入手,对符号的出现概率取倒数,这样得到的值就符合这个特性了。为了将这个值约束在一定范围内,不至于过大或过小,进一步对这个值取对数,这样就得到了某个概率为$p$的符号$x$的自信息量,具体公式为:$$ I(x_i) = - \log p(x_i) $$
对于包含多个符号的信息,其信息熵就取它们的平均信息量,即:$$ H(X) = -\sum_{i} p(x_i) \log p(x_i) $$

APP中,使用Java语言编写的统计信息熵程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// 符号数量统计与熵计算

package top.binweber.shannon;

import java.math.BigDecimal;
import java.util.Map;
import java.util.TreeMap;

public class EntropyCalculate {
private static int count;
private static Map<Character,Integer> amountMap;
private static Map<Character,Double> probabilityMap;

public EntropyCalculate() { // 初始化
count = 0; // 总符号数
amountMap = new TreeMap<>(); // 各符号数量Map
probabilityMap = new TreeMap<>(); // 各符号概率Map
}

public Map<Character,Integer> amountCal(String textStr) { // 数量统计
char[] chars = textStr.toCharArray(); // String转换为Char


for(int i = 0; i < chars.length; i++) { // 遍历,统计
if(!(chars[i] >= 'a' && chars[i] <= 'z' || chars[i] >= 'A' && chars[i] <= 'Z')) // 判断符号范围
continue;

count ++; // 总数统计
Integer amount = amountMap.get(chars[i]); // 获取符号的当前数量
if (amount != null) // 当前数量不为null
amount ++;
else // 当前数量为null
amount = 1;
amountMap.put(chars[i], amount); // 存入Map中
}

return amountMap;
}

public Map<Character,Double> probabilityCal() { // 概率计算
double pro = 0; // 概率

for(Map.Entry<Character, Integer> entry : amountMap.entrySet()) { // 遍历,统计
pro = (double) entry.getValue() / count; // 计算概率
BigDecimal bg = new BigDecimal(pro);
pro = bg.setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue(); // 保留3位小数
probabilityMap.put(entry.getKey(), pro); // 存入Map中
}

return probabilityMap;
}

public double entropyCal() { // 符号熵计算
double entropy = 0; // 符号熵

for(Double p : probabilityMap.values()) { // 遍历
entropy += -(p * Math.log(p) / Math.log(2)); // 符号熵计算
}

BigDecimal bg = new BigDecimal(entropy);
entropy = bg.setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue(); // 保留3位小数

return entropy;
}

public double entropyCal(Map<Character,Double> probMap) {
double entropy = 0;

for(Double p : probMap.values()) {
entropy += -(p * Math.log(p) / Math.log(2));
}

BigDecimal bg = new BigDecimal(entropy);
entropy = bg.setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue(); // 保留3位小数

return entropy;
}
}

香农编码

APP中,使用Java语言编写的香农编码过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package top.binweber.shannon;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class ShannonEncode {
private static Map<Character,Integer> cLengthMap; // 码长Map
private static Map<Character, String> codonMap; // 码字Map
private static List<Map.Entry<Character, Double>> probArrayList; //概率值List
private static double probs; // 累加概率
private static double aCLength; // 平均码长


public ShannonEncode(Map<Character,Double> probMap) { // 初始化
probs = 0.0;
aCLength = 0.0;
cLengthMap = new TreeMap<>();
codonMap = new TreeMap<>();

probArrayList = new ArrayList<>(probMap.entrySet()); // 按概率从大到小排序
Collections.sort(probArrayList,new Comparator<Map.Entry<Character,Double>>() {

public int compare(Map.Entry<Character,Double> o1, Map.Entry<Character,Double> o2) {
return o2.getValue().compareTo(o1.getValue());
}
});
}

public Map<Character, String> toShannon() { // 实现编码
double prob = 0;
int cLength = 0;

for(Map.Entry<Character,Double> entry:probArrayList) { // 由概率Map循环
prob = entry.getValue(); // 取出一个概率值
cLength = (int) Math.ceil(Math.log(1/prob)/Math.log((double)2)); // 计算码长,Math.ceil()-向上取整
cLengthMap.put(entry.getKey(), cLength); // 将算得的码长打包到Map
codonMap.put(entry.getKey(), colonCal(probs, cLength)); // 调用下面写好的colonCal方法,算得码字,打包到Map
aCLength += prob * cLength; // 计算平均码长
probs += prob; // 概率值累加
}

return codonMap;
}

private String colonCal(double probs, int nLength) { // 将累加概率转换为二进制(码字)
String coden = "";

for(int i = 0; i < nLength; i++) {
probs *= 2; // 累加概率乘以2
if(probs >= 1) {
probs -= 1;
coden += 1; // 大于1则取1
} else {
coden += 0; //小于1则取0
}
}

return coden;
}

public Map<Character, Integer> getCLengthMap() {
return cLengthMap;
}

public List<Map.Entry<Character, Double>> getProbArrayList() {
return probArrayList;
}

public double getACLength() {
BigDecimal bg = new BigDecimal(aCLength);
aCLength = bg.setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue();
return aCLength;
}

}

费诺编码

APP中,使用Java语言编写的费诺编码过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
package top.binweber.shannon;

import android.util.Log;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class FanoEncode {
private static Map<Character,Integer> cLengthMap; // 码长Map
private static Map<Character, String> codonMap; // 码字Map
private static List<Map.Entry<Character, Double>> probArrayList; // 概率List
private static double aCLength; // 平均码长

public FanoEncode(Map<Character,Double> probMap) { // 初始化
aCLength = 0.0;
cLengthMap = new TreeMap<>();
codonMap = new TreeMap<>();

probArrayList = new ArrayList<>(probMap.entrySet()); // 将概率Map按概率值递减排列放到概率List
Collections.sort(probArrayList,new Comparator<Map.Entry<Character,Double>>() {

public int compare(Map.Entry<Character,Double> o1, Map.Entry<Character,Double> o2) {
return o2.getValue().compareTo(o1.getValue());
}
});

}

public Map<Character, String> toFano() {
double[] pros = new double[probArrayList.size()]; // 概率值数组

int i = 0;
for(Map.Entry<Character,Double> entry:probArrayList) {
pros[i] = entry.getValue(); // 从概率List中取出概率值放入数组
i++;
}

String[] codon = getGroup(pros, 0, pros.length - 1); // 调用方法,得到编码

int j = 0;
for(Map.Entry<Character,Double> entry:probArrayList) {
codonMap.put(entry.getKey(), codon[j]); // 将各码字放进codonMap
cLengthMap.put(entry.getKey(), codon[j].length()); // 将各长放进cLengthMap
aCLength += pros[j] * codon[j].length(); // 计算平均码长
j++;
}

return codonMap;
}

private String[] getGroup(double[] pros, int i, int j) { // 输入概率值数组,得到其中索引为i到j编码结果
int middle = 0; // 分组点索引
String[] codens = new String[pros.length]; // 存储编码结果

for (int k = 0; k < pros.length; k++) {
codens[k] = ""; // 编码结果初始化
}

if(i < j) { // 索引i小于索引
double sum = 2; // 用以比较的中间量(初始值随便取一个大于1的即可)
for(int k = i; k <= j; k++) { // 循环找到中位值的索引
if(Math.abs(sumGroup(pros,i,k) - sumGroup(pros, k+1, j)) < sum) { // 如过两部分累加和之差小于中间量
sum = Math.abs(sumGroup(pros, i, k) - sumGroup(pros, k+1, j)); // 将两部分累加和之差作为中间量
middle = k; // 更新分组点的索引
}
}

String[] codens_1 = getGroup(pros, i, middle); // 递归获得前半部分编码
String[] codens_2 = getGroup(pros, middle+1, j); // 递归获得后半部分编码

for(int k = i; k <= middle; k++) { // 对前半部分编码
codens[k] = "0" + codens_1[k];
}

for(int k = middle + 1; k <= j ; k++) { // 对后半部分编码
codens[k] = "1" + codens_2[k];
}
}

return codens;
}

private double sumGroup(double[] pros,int i, int j) { // 累加概率数组索引i到j的值
double sum = 0.0;

for(int k = i; k <= j; k++) {
sum += pros[k];
}

return sum;
}

public Map<Character, Integer> getCLengthMap() {
return cLengthMap;
}

public List<Map.Entry<Character, Double>> getProbArrayList() {
return probArrayList;
}

public double getACLength() {
BigDecimal bg = new BigDecimal(aCLength);
aCLength = bg.setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue();
return aCLength;
}

}

哈夫曼编码

APP中,使用Java语言编写的哈夫曼编码过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package top.binweber.shannon;

import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;

class TreeNode { // 树节点类

public double prob; // 结点概率值
public String codeword = ""; // 码字
public TreeNode left; // 左子节点
public TreeNode right; // 右子节点

public TreeNode(double data){
this.prob = data;
}
}

public class HuffmanEncode {
private static Map<Character, Integer> cLengthMap; // 码长Map
private static Map<Character, String> codonMap; // 码字Map
private static List<Map.Entry<Character, Double>> probArrayList; // 概率List
private static double aCLength; // 平均码长
private static List<String> codonList; // 码字List


public HuffmanEncode(Map<Character, Double> probMap) { // 初始化
aCLength = 0.0;
cLengthMap = new TreeMap<>();
codonMap = new TreeMap<>();
codonList = new ArrayList<>();

probArrayList = new ArrayList<>(probMap.entrySet()); // 将概率Map按概率值递减排列放到概率List
Collections.sort(probArrayList, new Comparator<Map.Entry<Character, Double>>() {

public int compare(Map.Entry<Character, Double> o1, Map.Entry<Character, Double> o2) {
return o2.getValue().compareTo(o1.getValue());
}
});
}

public Map<Character, String> toHuffman() { // 进行编码
List<TreeNode> list = new ArrayList<>(); // 用于存放节点的List

int i = 0;
for(Map.Entry<Character,Double> entry:probArrayList) {
double prob = entry.getValue(); // 取出概率值
TreeNode root = new TreeNode(prob); // 创建新节点
list.add(i, root); // 将新节点加入list
i ++;
}

createTree(list); // 由list中的节点创建哈夫曼树
TreeNode root = (TreeNode)list.get(0); // 得到根节点
list.clear(); // 清空list
printTree(root); // 获得编码结果

int j = 0;
for(Map.Entry<Character,Double> entry:probArrayList) {
codonMap.put(entry.getKey(), codonList.get(j));
cLengthMap.put(entry.getKey(), codonList.get(j).length());
aCLength += entry.getValue() * codonList.get(j).length();
j ++;
}

return codonMap;
}

private void createTree(List<TreeNode> list){ // 创建一棵哈夫曼树
double prob1 = (list.get(list.size() - 1)).prob; // 取出倒数第一个节点的概率
double prob2 = (list.get(list.size() - 2)).prob; // 取出倒数第二个节点的概率
double prob_sum = prob1 + prob2; // 两个最小的概率值相加

TreeNode root = new TreeNode(prob_sum); // 用相加的概率创建一个新节点

root.left = (list.get(list.size() - 1)); // 将倒数第一个作为左子节点
root.right = (list.get(list.size() - 2)); // 将倒数第二个作为右子节点
list.remove(list.size() - 1); // 已经list中加上树上的节点删除
list.remove(list.size() - 1);

sortList(list, root); // 将新的节点加到list里,并排序

if(list.size() > 1){
createTree(list); // 只要list里面还有节点,就递归创建树
}
}

private void sortList(List<TreeNode> list,TreeNode root){ // 将某个节点插入list,排序
if(list.size() == 0){
list.add(root); // list为空时直接插入
}else{
int i;
for(i = 0; i < list.size(); i++){
if(list.get(i).prob <= root.prob){ // 循环比较大小
list.add(i, root); // 插入
break;
}
}

if(i == list.size()) { // 到最后,直接插入
list.add(i, root);
}
}
}

private void printTree(TreeNode root){ // 使用广度优先查找算法,层次遍历哈夫曼树各节点

Queue<TreeNode> queue = new ArrayDeque<>(); // 节点队列

queue.offer(root); // 将根节点入队
while(!queue.isEmpty()) { // 队列非空,不断执行

root = queue.poll(); // 将一个节点出队

if (root.left != null) { // 该节点的左子节点非空
root.left.codeword = root.codeword + "0"; // 左子节点码字加0
queue.offer((root.left)); // 左子节点入队
}
if (root.right != null) { // 该节点的右子节点非空
root.right.codeword = root.codeword + "1"; // 右子节点码字加1
queue.offer((root.right)); // 右子节点入队
}

if (root.left == null && root.right == null) { // 节点为叶子结点
codonList.add(root.codeword); // 将节点的码字存储起来
}
}

}

public Map<Character, Integer> getCLengthMap() {
return cLengthMap;
}

public List<Map.Entry<Character, Double>> getProbArrayList() {
return probArrayList;
}

public double getACLength() {
BigDecimal bg = new BigDecimal(aCLength);
aCLength = bg.setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue();
return aCLength;
}
}

判断唯一可译码

APP中,使用Java语言编写的判断可译码的程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package top.binweber.shannon;

import java.util.ArrayList;

public class UniqueDecode {

private boolean result; // 判断结果
private ArrayList<String> codonList; // 码字集
private ArrayList<String> suffixList; // 后缀集

public UniqueDecode(ArrayList<String> codonList) { // 初始化
result = true; // 默认唯一可译
this.codonList = codonList;
suffixList = new ArrayList<>();
}

public boolean compare() { // 比较判断
String suffix = null;

cp: for(int i = 0; i < codonList.size(); i++) {
for(int j = i + 1; j < codonList.size(); j++) {
String codon1 = codonList.get(i); // 取出两个码字
String codon2 = codonList.get(j);

suffix = compareCodon(codon1,codon2); // 获得尾随后缀

if(!result) { // 已判断出非唯一可译
break cp; // 跳出循环
}

if(suffix != null && !suffixList.contains(suffix)) { // 尾随后缀不为null,且尾随后缀集b不包含该后缀
suffixList.add(suffix); // 收集获得的尾随后缀
}
}
}

compareList(codonList, suffixList, suffix); // 比较码字集与尾随后缀集

return result;
}

public ArrayList<String> getSuffixList() {
return suffixList;
}

private String compareCodon(String codon1, String codon2) { // 比较两个码字
String suffix = null; // 尾随后缀初始化为null

if(codon1.equals(codon2)) { // 如果有两个码字相同,奇异码
result = false; // 非唯一可议
}

if(result) {
if(codon1.startsWith(codon2)) // 如果码字1以码字2作为开头
suffix = codon1.substring(codon2.length(), codon1.length()); // 从码字2中取出尾随后缀

if(codon2.startsWith(codon1)) // 如果码字2以码字1作为开头
suffix = codon2.substring(codon1.length(), codon2.length()); // 从码字1中取出尾随后缀
}

return suffix; // 返回尾随后缀
}

private void compareList(ArrayList<String> a, ArrayList<String> b, String suffix) { // 比较码字集和尾随后缀集
boolean flag = false; // 继续递归判断标志

String codon1,codon2;

cp: for(int i = 0; i < a.size(); i++) { // 循环
for(int j = 0; j < b.size(); j++) {
codon1 = a.get(i); // 从a中取出一个码字1
codon2 = b.get(j); // 从b中取出一个尾随后缀
suffix = compareCodon(codon1,codon2); // 比较码字1、2,获得尾随后缀

if(!result) { // 已经判断出是非唯一可译
break cp; // 跳出循环
}

if(suffix != null && !b.contains(suffix)) { // 尾随后缀不为null,且尾随后缀集b中不包含该后缀
b.add(suffix); // 尾随后缀加入b中
flag = true; // 需要继续判断
break cp; // 跳出循环
}
// 当前尾随后缀为null或得到的是重复的尾随后缀则继续循环
}
}

if(flag) {
compareList(a, b, suffix); // 继续递归进行判断
}

}
}

APP

“香农”APP运行的部分截图如下:

判断唯一可译码

编码界面

编码结果

参考资料

  1. APP下载-网盘
  2. APP程序开源-Github
  3. Java实现三种信源编码-iteye
  4. 唯一可译码判决准则-csdn

更新历史:

  • 2018.6.24 完成初稿
文章作者: Hugsy
文章链接: http://binweber.top/2018/06/24/android_shannon/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Weber
支付宝打赏~
微信打赏~