一、霍夫曼编码
1.算法分析
霍夫曼编码是变长编码的一种，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。
霍夫曼编码的具体步骤如下：
1）将信源符号的概率升序排队。
2）把两个最小的概率相加，形成一个新的概率集合，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率１。
3）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。
4）将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
2.题目解析
1.数据结构：
提到霍夫曼编码必须要提到霍夫曼树，所以首先要定义树：节点存放字符与权重（即字符出现次数），还要有左右两个孩子，考虑到最后分配码字的过程，还可以加上深度优先遍历的实现函数。数据结构如下：
2.实现过程：
首先是获取字符，我采用txt文件的方式存储字符串（直接输入读取更简单所以我介绍这种方式），读取过程中直接统计字符与其出现次数，存储在Map中。
然后开始建树，将Map中的字符与频率建成哈夫曼树节点，然后存放在链表LinkedList中；再将链表中的树节点按权重大小升序排列。
开始循环遍历，每次取出最小的两个树节点（也就是在链表中前两个），加和后成为新树，链接上左右两个子树，再按升序放回链表，直至只剩一个树节点。
深度优先遍历分配码字即可。
运行结果如下：
二、香农-费诺编码
1.算法分析
步骤如下：
1.将信源符号按照其概率大小，从大到小排列；
2.将这一组信源符号分成概率之和尽可能接近或者相等的一组（即两组分别的概率和之间的差尽可能小！）；
3.将上面一组符号编码成0，下面一组编码成1，反之亦可；
4.将已经分好的组重复步骤2,3，直到不能再进行分组为止；
5.从左到右一次写出码字。
2.题目解析
1.数据结构：
费诺编码我没有建树，因为要将所有字符按频率大小降序排列，为了方便排序，我设计了txt类，存储字符与频数，数据结构如下：
2.实现算法：
首先从文件中读取字符，步骤同上，存储在Map中；
将Map中存储的数据以txt的形式存储在链表中，降序排列；
再将频数转成频率（小数）；
因为费诺编码要把所有信符分为两组，重复直至每组只剩下一个信号，所以选择递归实现：终止条件为只剩下一个信号（即开始等于结束）；分成大小差不多的两部分：因为降序排列，所以从第一个开始，以前i个信符的频率和的二倍减总和的差为基准，最小的即为所求；然后进行左右递归。
运行结果如下：
三、算术编码
1.算法分析
算术编码的编码对象是一则消息或一个字符序列，其编码思路是将消息或字符序列表示成0和1之间的一个间隔上的一个浮点小数。 在进行算术编码之前，需要对字符序列中每个字符的出现概率进行统计，根据各字符出现概率的大小，将每个字符映射到[0 ，1]区间上的某个子区间中。然后，在利用递归算法，将整个字符序列映射到[0，1]区间上的某个间隔中。在进行编码时，只需从该间隔中任选一个小数，将其转化为二进制数。 符号序列越长，编码表示他的间隔就越小，表示这个间隔所需的二进制位数就越多，编码输出的码字就越长。
在进行编码过程中，随着信息的不断出现，子区间按下列规律减小：
a.新子区间左端=前子区间左端+当前子区间左端×前子区间长度
b.新子区间长度=前子区间长度×当前子区间长度
2.题目解析
1.数据结构：定义qujian类存储区间前后端；
2.实现过程：
首先读取字符串，统计每个字符的上下端点。然后按照公式进行计算直至算到最后一个字符；最转换成二进制取公共部分，忽略0. 即可完成编码。
编码结果如下：
四、比较分析
1.霍夫曼编码特点：
1.Huffman码的编码方法保证了概率大的符号对应短码，概率小的符号对应长码，而且短码得到充分利用。
2.每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同(二元编码情况)。
3.每次缩减信源的最长两个码字有相同的码长。
这三个特点保证了所得的Huffman码一定是最佳码。
4.霍夫曼编码是无损压缩中效率较高的一种编码方式，但压缩过程复杂，运算量大。
2.香农费诺编码特点：
1.香农费诺编码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。
2.香农费诺编码不一定是最佳码。因为香农费诺编码方法不一定能使短码得到充分利用。当信源符号较多时，若有一些符号概率分布很接近，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。
3.香农费诺编码相较于霍夫曼编码更加方便、快捷。
3.算术编码特点：
1.算术编码是比霍夫曼编码的压缩性能更优的一种变长编码方式，，可以采用比霍夫曼编码更少的码字。
2.算术编码的实现方法比霍夫曼更复杂，但是编码效率高。
4.结果比较：
霍夫曼编码：
香农-费诺编码：
可见，香农费诺<霍夫曼。
对于相同字符串，三种方式的编码结果：
可见霍夫曼编码效率小于算术编码，而香农-费诺编码的压缩效率不一定好。
五、代码
代码文件目录：
arithmetic.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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174package Arithmetic; import java.io.*; import java.util.HashMap; import java.util.Map; import java.util.Optional; /** * Description: * date: 2022/4/9 16:10 * * @author 颜霸灿烈 */ public class arithmetic { static int sum =0; static StringBuffer s=new StringBuffer(); private static class qujian{ double start=0.0; double end=0.0; qujian(double start,double end) { this.start=start; this.end=end; } } static Map<Character,qujian> data=new HashMap<>(); static Map<Character,Integer>txts; //字符串直接给 public static Map<Character,Integer> read(){ Map<Character,Integer> res=new HashMap<>(); res.put('A',400); res.put('B',200); res.put('C',160); res.put('D',120); res.put('E',60); res.put('F',40); res.put('G',20); sum=1000; qujian q1=new qujian(0,0.4); data.put('A',q1); qujian q2=new qujian(0.4,0.6); data.put('B',q2); qujian q3=new qujian(0.6,0.76); data.put('C',q3); qujian q4=new qujian(0.76,0.88); data.put('D',q4); qujian q5=new qujian(0.88,0.94); data.put('E',q5); qujian q6=new qujian(0.94,0.98); data.put('F',q6); qujian q7=new qujian(0.98,1); data.put('G',q7); System.out.println("原字符及频率："); for(char key:res.keySet()) { int value=res.get(key); System.out.print(key+":"+value+" "); } System.out.println(); return res; } //从文件中读取字符串 public static Map<Character,Integer> readtxt() throws IOException { String fileName="src/code.TXT"; Map<Character,Integer> txts=new HashMap<>(); File file = new File(fileName); FileInputStream fis = new FileInputStream(file); InputStreamReader isr = new InputStreamReader(fis); BufferedReader br = new BufferedReader(isr); String line; System.out.println("原字符串为："); while((line = br.readLine()) != null){ System.out.println(line); for (int i = 0; i < line.length(); i++) { char tmp=line.charAt(i); sum++; s.append(tmp); if(txts.containsKey(tmp)) { int n=txts.get(tmp); n++; txts.put(tmp,n); } else { txts.put(tmp,1); } } } // for(char key : txts.keySet()){ // int value = txts.get(key); // System.out.println(key+":"+value); // } br.close(); return txts; } //压缩 public static void compress() throws IOException { txts=readtxt(); // qujian q1=new qujian(0,0.2); // data.put('a',q1); // qujian q2=new qujian(0.2,0.5); // data.put('b',q2); // qujian q3=new qujian(0.5,0.9); // data.put('c',q3); // qujian q4=new qujian(0.9,1.0); // data.put('d',q4); // String ss="bcadc"; double start=0; double end=0; for (char key:txts.keySet()) { double fre=txts.get(key)*1.0/sum; start=end; end+=fre; qujian tmp=new qujian(start,end); data.put(key,tmp); } String ss=s.toString(); double L=0; double H=1; for (int i = 0; i < ss.length(); i++) { char tmp=ss.charAt(i); qujian qj=data.get(tmp); double n=H-L; H=L+qj.end*n; L=L+qj.start*n; } String l=decimal2Binary(L); String r=decimal2Binary(H); StringBuffer res=new StringBuffer(); for (int i = 0; i < l.length(); i++) { if(l.charAt(i)==r.charAt(i)) { res.append(l.charAt(i)); } else{ res.append('1'); break; } } System.out.println("算术编码结果为"+res); System.out.println("编码长度为"+res.length()); } //纯小数十进制变二进制 public static String decimal2Binary(double value){ StringBuilder stringBuilder = new StringBuilder(); int count = 100; // 限制小数部分位数 double num = 0; while (value > 0.0000000001) { count--; if (count == 0) { return stringBuilder.toString(); } num = value * 2; if (num >= 1) { stringBuilder.append(1); value = num - 1; } else { stringBuilder.append(0); value = num; } } return stringBuilder.toString(); } public static void main(String[] args) throws IOException { compress(); } }
Fano.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
151
152
153
154
155
156
157
158
159
160package Fano; import Huffman.HuffmanTree; import java.io.*; import java.util.*; import static java.lang.Math.abs; /** * Description: * date: 2022/4/8 21:07 * * @author 颜霸灿烈 */ public class Fano { static int res=0; static int cnt = 0; // static int sum=0;//字符总数 static LinkedList<txt>datas;//存储降序频率 static Map<Character,String> fenocode=new HashMap<>();//存储最后的编码结果 //方便降序 private static class txt{ char data;//字符 int num;//频数 public txt(char data,int num){ this.data=data; this.num=num; } } public static Map<Character,Integer> read(){ Map<Character,Integer> res=new HashMap<>(); res.put('A',400); res.put('B',200); res.put('C',160); res.put('D',120); res.put('E',60); res.put('F',40); res.put('G',20); sum=1000; System.out.println("原字符及频率："); for(char key:res.keySet()) { int value=res.get(key); System.out.print(key+":"+value+" "); } System.out.println(); return res; } //从文件中读取统计字符频率 public static Map<Character,Integer> readtxt() throws IOException { String fileName="src/code.TXT"; Map<Character,Integer> txts=new HashMap<>(); File file = new File(fileName); FileInputStream fis = new FileInputStream(file); InputStreamReader isr = new InputStreamReader(fis); BufferedReader br = new BufferedReader(isr); String line; System.out.println("原字符串为："); while((line = br.readLine()) != null){ System.out.println(line); for (int i = 0; i < line.length(); i++) { char tmp=line.charAt(i); sum++; if(txts.containsKey(tmp)) { int n=txts.get(tmp); n++; txts.put(tmp,n); } else { txts.put(tmp,1); } } } br.close(); return txts; } /*统计频率*/ static double getSum(LinkedList<Double> p, int begin, int end){ double sum = 0; for(int i = begin ; i <= end ; i++){ sum += p.get(i); } return sum; } //递归实现 static void Fanocode(LinkedList<Double> p, int begin, int end, String code){ // 边界条件 if(begin >= end){ fenocode.put(datas.get(cnt).data,code); cnt++; return; } // 找到分界值 double sum = getSum(p,begin,end); int index = -1; // 初值设定 double minNum = sum; // 设定最小值 double tempSum = 0; // 前几个的和 for(int i = begin ; i <= end ; i++){ tempSum += p.get(i); if(abs(sum-2*tempSum) < minNum){ index = i; // 记录当前最小的值 minNum = abs(sum-2*tempSum); // 更新最小值 } else{ break; } } // 递归左边部分 Fanocode(p,begin,index,code+'0'); // 左边添加0 // 递归右边部分 Fanocode(p,index+1,end,code+'1'); //右边添加1 } //实现压缩 public static void compressact() throws IOException { //读取文件中的字符串 Map<Character,Integer>txts; // txts=read(); txts=readtxt(); //降序排列 datas=new LinkedList<txt>(); for(char key:txts.keySet()) { int value=txts.get(key); txt tmp=new txt(key,value); datas.add(tmp); } Collections.sort(datas,new Comparator<txt>(){ public int compare(txt a,txt b){ return (int) b.num-a.num; } }); //转化成频率 LinkedList<Double>p=new LinkedList<>(); for (int i = 0; i < datas.size(); i++) { double fre=datas.get(i).num*1.0/sum; p.add(fre); } String code=""; System.out.println("香农-费诺编码结果："); Fanocode(p,0,txts.size()-1,code); for(char key:fenocode.keySet()) { String value=fenocode.get(key); res+=(value.length()*txts.get(key)); System.out.print(key+":"+value+" "); } System.out.println(); System.out.println("压缩后总长度："+res); } public static void main(String[] args) throws IOException { compressact(); } }
Huffman.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
110package Huffman; import java.io.*; import java.util.*; //代码仅供参考，不一定正确，有错误请指正！ public class Huffman{ static int res=0; static HashMap<Character,String> CodingMap; public static Map<Character,Integer> read(){ Map<Character,Integer> res=new HashMap<>(); res.put('A',400); res.put('B',200); res.put('C',160); res.put('D',120); res.put('E',60); res.put('F',40); res.put('G',20); return res; } //从文件中读取统计字符频率 public static Map<Character,Integer> readtxt() throws IOException { String fileName="src/code.TXT"; Map<Character,Integer> txts=new HashMap<>(); File file = new File(fileName); FileInputStream fis = new FileInputStream(file); InputStreamReader isr = new InputStreamReader(fis); BufferedReader br = new BufferedReader(isr); String line; System.out.println("原字符串为："); while((line = br.readLine()) != null){ System.out.println(line); for (int i = 0; i < line.length(); i++) { char tmp=line.charAt(i); if(txts.containsKey(tmp)) { int n=txts.get(tmp); n++; txts.put(tmp,n); } else { txts.put(tmp,1); } } } // for(char key : txts.keySet()){ // int value = txts.get(key); // System.out.println(key+":"+value); // } br.close(); return txts; } //压缩编码 public static void compressact()throws IOException{ Map<Character,Integer>txts; txts=read(); // txts=readtxt(); LinkedList<HuffmanTree> forest=new LinkedList<HuffmanTree>(); CodingMap=new HashMap<>(); System.out.println("字符及频率如下："); //建树 for(char key : txts.keySet()){ int value = txts.get(key); forest.add(new HuffmanTree(value,key)); System.out.print(key+":"+value+" "); } System.out.println(""); Collections.sort(forest,new Comparator<HuffmanTree>(){ public int compare(HuffmanTree a, HuffmanTree b){ return (int) (a.weight-b.weight); } });//排序 while(forest.size()>1){ HuffmanTree a = forest.removeFirst(); HuffmanTree b = forest.removeFirst();//取出前两个 HuffmanTree c = new HuffmanTree(a.weight+b.weight);//增加新的节点 c.lChild=a;//连接ac c.rChild=b;//连接bc int index=0;//用来记录应该插入的位置 for(;index<forest.size();index++) { if (forest.get(index).weight >= c.weight) { forest.add(index, c); break; } } //如果森林里没有比它大的，则插在末尾 if(index>= forest.size()) forest.add(index,c); } HuffmanTree result=forest.get(0); result.dfs(CodingMap,""); System.out.println("霍夫曼编码结果如下："); for(char key : CodingMap.keySet()){ String value = CodingMap.get(key); res+=(value.length()*txts.get(key)); System.out.print(key+":"+value+" "); } System.out.println(); System.out.println("压缩后总长度："+res); } public static void main(String[] args) throws IOException { compressact(); } }
HuffmanTree.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
42package Huffman; import java.util.HashMap; /** * Description: * date: 2022/4/8 19:35 * * @author 颜霸灿烈 */ public class HuffmanTree{ public int weight;//出现频率 public char data;//字符 public HuffmanTree lChild,rChild;//左右两个还在 public HuffmanTree(int weight){ this.weight=weight; }//构造函数 public HuffmanTree(int weight,char data){ this.weight=weight; this.data=data; } /*深度优先遍历分配码字*/ public void dfs(HashMap<Character,String> cm, String prefix){ int count=0;//记录有几个孩子 if(lChild!=null){ lChild.dfs(cm,prefix+"0"); //左孩子边为0 count++;//有一个孩子 } if(rChild!=null){ rChild.dfs(cm,prefix+"1"); //右孩子边为1 count++;//有两个孩子 } if(count==0){//一个孩子都没有，叶子节点 cm.put(data,prefix); } } }
最后
以上就是自觉雪糕最近收集整理的关于数字图像处理：压缩编码的全部内容，更多相关数字图像处理内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复