【Android】香农APP

一款可译用来统计信息熵，进行二元香农、诺顿、哈夫曼编码，以及判断分组码是否唯一可译的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语言编写的统计信息熵程序如下：

// 符号数量统计与熵计算

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语言编写的香农编码过程如下：

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语言编写的费诺编码过程如下：

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语言编写的哈夫曼编码过程如下：

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语言编写的判断可译码的程序如下：

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 完成初稿