[工学]信息论与编码课程设计实验报告.doc

计算机与信息学院 信息论与编码课程设计 实验报告专 业 班 级 信息安全11-1班 学生姓名及学号 课程教学班号 0001 任 课 教 师 实验指导教师 实验地点 逸夫科技楼507 20132014学年第一学期实验一：对任意的符号序列（abbcccdddddeeeeee）进行n元Huffman的编码实现一、问题描述Huffman编码是一种常用的压缩编码方法，是Huffman与1952年为压缩文本文件建立的。它的基本原理是按照概率大小的顺序排列信源符号，并设法按逆顺序分配码字字长，使编码的码字为可辨识的。Huffman码是最佳码。本次课程设计主要是实现对任意的符号序列进行n元Huffman的编码。二、基本要求本程序需要达到的要求是：由使用者输入信源符号（如：abbcccdddddeeeeee）、编码的元数（n）。后运行程序，程序输出每个符号的编码以及信源符号串的编码。再将编码结果输入，译码得出原序列。三、测试数据1.输入符号序列为：abbcaddacaeffghgi 元数为：5四、算法思想本算法的n元编码过程实现如下：（1）将q 个信源按概率分布大小依次排列；（2）计算实际所需的信源符号数【根据公式：q =（n - 1）+ n】；（3）用0，1，2，n-1分别代表概率最小的n个信源符号，并将这n个概率最小的信源符号合并成一个新的符号，并将这n个符号标记为true。使得标记为false的符号数为q-n+1 个，构成的新信源S1； （4）把信源S1的符号仍按概率大小依递排列，并将其最后n 个概率最小的符号合并成一个符号，并分别用0，1，2，r-1码符号表示。这样就形成了标记为false的q-2(n-1)个符号组成的信源S2；（5）依次继续下去，直至信源最后只剩下n个符号为止。将这最后n个信源符号分别用n进制符号0，1，r-1 表示；（6）最后，通过递归函数从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即相应的码字。译码过程如下：（1）将输入的字符串转换成char类型数组，取出第一个字符，作为起始字符；（2）将取出的字符与编码后的编码结果进行比对。若一致则输出与编码结果对应的符号，并将char数组中的下一个字符作为起始字符。否则取char数组的前两个进行比对，如此循环下去。五、模块划分1.计算实际需要的符号数for(int i=0;i<sum;i+)timesi=0;for(int i=0;i<sum;i+)for(int j=0;j<get_sign.length;j+)if (signi=get_signj)timesi+;/System.out.print(timesi+" ");for(int i=0;)if(real_sum=i*(n-1)+n)<sum)i+;else break; 2. 建立Huffman结点class HuffmanNode /建立Huffman编码结点 public int frequency;public boolean flag;public char name;public String code;public HuffmanNode next;HuffmanNode(char name,int frequency,boolean flag)this.name=name;this.frequency=frequency;this.flag=flag;this.code=""this.next=null;3. 对HUFFMAN结点数组进行排序if(circle_times=1)for(int i=0;i<real_sum;i+)for(int j=i+1;j<real_sum;j+)if(node_arrayi.frequency>node_arrayj.frequency)HuffmanNode x;x=node_arrayi;node_arrayi=node_arrayj;node_arrayj=x;if(circle_times!=1)int j=real_sum-1;for(int i=real_sum-2;i>=0;i-)if(node_arrayi.frequency>node_arrayj.frequency)HuffmanNode x;x=node_arrayi;node_arrayi=node_arrayj;node_arrayj=x;j-; 4. 给出每个符号的码符号for(int i=0;i<real_sum;i+)if(count2!=n&&node_arrayi.flag=false)String temp=null;temp=Integer.toString(count2);/System.out.println(temp);node_arrayi.code=temp;/System.out.println(node_arrayi.name+" "+node_arrayi.code);count2+; 5. 合并n个符号node_arrayreal_sum=new HuffmanNode('*',combine,false);/建立新的huffman结点for(int i=0;i<real_sum;i+)if(count!=n&&node_arrayi.flag=false&&false_num!=n)combine=combine+node_arrayi.frequency;count+;node_arrayi.flag=true;node_arrayi.next=node_arrayreal_sum;/System.out.println(node_arrayi.name+" "+node_arrayi.next.frequency);/System.out.println(combine);node_arrayreal_sum.frequency=combine;real_sum+; 6.输出码符号序列的递归程序public void encode(HuffmanNode hn)if(hn.next!=null&&hn.next.code!=null)if(hn.next.flag!=false)encode(hn.next);hn.code=hn.next.code+hn.code;hn.flag=false;elsehn.code= hn.next.code+ hn.code;/System.out.println(hn.code); 7.译码程序class ButtonListener2 implements ActionListenerpublic void actionPerformed(ActionEvent e)String s = e.getActionCommand();if("开始译码" = s)ta.append("译码结果为："+"n");String get_yima;get_yima=tf3.getText();char yima_array;yima_array=get_yima.toCharArray();String str=String.valueOf(yima_array0);for(int i=0;i<yima_array.length;i+)for(int j=0;j<real_sum;j+)/System.out.println(str);if(str.equals(node_arrayj.code)&&node_arrayj.name!='*')ta.append(String.valueOf(node_arrayj.name);str=""/System.out.println("0");break;if(i<=yima_array.length-2)str=str+String.valueOf(yima_arrayi+1);六、源程序import javax.swing.*;import java.awt.Color;import java.awt.event.*;class HuffmanNode /建立Huffman编码结点 public int frequency;public boolean flag;public char name;public String code;public HuffmanNode next;HuffmanNode(char name,int frequency,boolean flag)this.name=name;this.frequency=frequency;this.flag=flag;this.code=""this.next=null;class N_Huffman_Jframe extends JFramestatic public int n;static public int sum;static public int real_sum;static public char sign=new char50;/存放输入的符号static public int times=new int50;ButtonListener bl =new ButtonListener();ButtonListener2 b2 =new ButtonListener2();JTextField tf1=new JTextField();JTextField tf2=new JTextField();JTextField tf3=new JTextField();JTextArea ta=new JTextArea();/N_Huffman_Jframe(String title)super(title);this.setSize(500,360);this.setLocation(400, 200);addWindowListener( / 窗口监听器new WindowAdapter() public void windowClosing(WindowEvent e) / 关闭所有窗体System.exit(0););JPanel p=new JPanel();p.setLayout(null);JLabel l1=new JLabel("请输入符号序列");l1.setFont(new java.awt.Font("微软雅黑",4,15);l1.setBounds(10, 13, 120,20);tf1.setBounds(125, 10,350, 30);JLabel l2=new JLabel("元数");l2.setBounds(355, 58, 50,20);l2.setFont(new java.awt.Font("微软雅黑",4,15);tf2.setBounds(395,55,80, 30);JButton ok=new JButton("确认");ok.setBounds(355, 100, 120, 35);ok.setBackground(Color.white);ok.setFont(new java.awt.Font("微软雅黑",4,15);ok.addActionListener(bl);JLabel l4=new JLabel("需要译码序列");l4.setFont(new java.awt.Font("微软雅黑",4,15);l4.setBounds(10, 250, 90, 20);tf3.setBounds(110, 245, 365, 30);JButton yima=new JButton("开始译码");yima.setBounds(170, 282, 200, 30);yima.setBackground(Color.white);yima.setFont(new java.awt.Font("微软雅黑",4,15);yima.addActionListener(b2);ta.setBounds(15, 50, 330, 180);ta.setLineWrap(true);JScrollPane jsp=new JScrollPane(ta);jsp.setBounds(15, 50, 330, 180);this.add(p);p.add(l1);p.add(tf1);p.add(l2);p.add(tf2);p.add(ok);p.add(l4);p.add(tf3);p.add(yima);p.add(jsp);this.setVisible(true); /递归函数public void encode(HuffmanNode hn)if(hn.next!=null&&hn.next.code!=null)if(hn.next.flag!=false)encode(hn.next);hn.code=hn.next.code+hn.code;hn.flag=false;elsehn.code= hn.next.code +hn.code;/System.out.println(hn.code);HuffmanNode node_array=new HuffmanNode200;class ButtonListener implements ActionListenerpublic void actionPerformed(ActionEvent e)String s = e.getActionCommand();if("确认" = s)ta.setText("");String str=tf1.getText();String str2=tf2.getText();n=Integer.parseInt(str2);char get_sign=str.toCharArray();sign0=get_sign0;/计算输入的符号数int jj=0;/sum = 1;for(int i=0;i<get_sign.length;i+)int t=0;for(int m=0;m<jj;m+)if(signm!=get_signi)t+;if(t=jj)signjj=get_signi;jj+;/符号数sum=jj;/System.out.println(sign);/sign 为符号数组/System.out.println("符号数为："+sum+"n");/计算真实需要的符号数for(int i=0;i<sum;i+)timesi=0;for(int i=0;i<sum;i+)for(int j=0;j<get_sign.length;j+)if (signi=get_signj)timesi+;/System.out.print(timesi+" ");for(int i=0;)if(real_sum=i*(n-1)+n)<sum)i+;else break;/System.out.println("n"+"huffman编码需要的符号数："+real_sum);/System.out.println("");/建立Huffman结点数组int ii;int cha=real_sum-sum;for(ii=0;ii<cha;ii+)node_arrayii=new HuffmanNode('*',0,false);for(;ii<real_sum;ii+)node_arrayii=new HuffmanNode(signii-cha,timesii-cha,false);/*for(int i=0;i<real_sum;i+)System.out.println(node_arrayi.name+" "+node_arrayi.frequency+" "+node_arrayi.flag);*/开始编码int circle_times=1;/记录while循环的次数while(true)int count=0;int count2=0;int combine=0;/每次n个符号频率相加的值int false_num=0;for(int i=0;i<real_sum;i+)if(node_arrayi.flag=false)false_num+;/对HUFFMAN结点数组进行排序if(circle_times=1)for(int i=0;i<real_sum;i+)for(int j=i+1;j<real_sum;j+)if(node_arrayi.frequency>node_arrayj.frequency)HuffmanNode x;x=node_arrayi;node_arrayi=node_arrayj;node_arrayj=x;if(circle_times!=1)int j=real_sum-1;for(int i=real_sum-2;i>=0;i-)if(node_arrayi.frequency>node_arrayj.frequency)HuffmanNode x;x=node_arrayi;node_arrayi=node_arrayj;node_arrayj=x;j-;/输出排序/*for(int i=0;i<real_sum;i+)System.out.println(node_arrayi.name+" "+node_arrayi.frequency+" "+node_arrayi.flag);System.out.print("n");*/给每个符号的码符号for(int i=0;i<real_sum;i+)if(count2!=n&&node_arrayi.flag=false)String temp=null;temp=Integer.toString(count2);/System.out.println(temp);node_arrayi.code=temp;/System.out.println(node_arrayi.name+" "+node_arrayi.code);count2+;/ 合并n个符号！node_arrayreal_sum=new HuffmanNode('*',combine,false);/建立新的huffman结点for(int i=0;i<real_sum;i+)if(count!=n&&node_arrayi.flag=false&&false_num!=n)combine=combine+node_arrayi.frequency;count+;node_arrayi.flag=true;node_arrayi.next=node_arrayreal_sum;/System.out.println(node_arrayi.name+" "+node_arrayi.next.frequency);/System.out.println(combine);node_arrayreal_sum.frequency=combine;real_sum+;/if(false_num=n)break;circle_times+;/for(int i=0;i<real_sum;i+)node_arrayi.flag=true;for(int i=0;i<real_sum;i+)encode(node_arrayi);/System.out.println("");for(int i=0;i<real_sum;i+)if(node_arrayi.name!='*')ta.append(node_arrayi.name+" "+node_arrayi.code); ta.append("n");/*for(int i=0;i<real_sum;i+)if(node_arrayi.next!=null)System.out.println(node_arrayi.name+" "+node_arrayi.next.frequency);*/for(int i=0;i<get_sign.length;i+)for(int j=0;j<real_sum;j+)if(get_signi=node_arrayj.name)ta.append(node_arrayj.code);ta.append("n");class ButtonListener2 implements ActionListenerpublic void actionPerformed(ActionEvent e)String s = e.getActionCommand();if("开始译码" = s)ta.append("译码结果为："+"n");String get_yima;get_yima=tf3.getText();char yima_array;yima_array=get_yima.toCharArray();String str=String.valueOf(yima_array0);for(int i=0;i<yima_array.length;i+)for(int j=0;j<real_sum;j+)/System.out.println(str);if(str.equals(node_arrayj.code)&&node_arrayj.name!='*')ta.append(String.valueOf(node_arrayj.name);str=""/System.out.println("0");break;if(i<=yima_array.length-2)str=str+String.valueOf(yima_arrayi+1);public class n_huffman_encode public static void main(String args)N_Huffman_Jframe nhj=new N_Huffman_Jframe("n元Huffman编码");七、测试情况 本程序测试结果符合实际，正确的输出了输入信源符号的Huffman编码并正确译码。实验三：对一灰度图像进行与Huffman结合的游程编码的设计实现一、问题描述游程编码又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码，是栅格数据压缩的重要编码方法。对于二值图有效。游程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号，使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。本次课程设计主要是实现对任意的符号序列进行游程编码，并将游程编码与Huffman编码、等长编码进行结合。最后再将得到的编码结果进行译码，输出原来的符号序列。二、基本要求本程序需要达到的要求是：由使用者输入灰度图像矩阵的行数（m）、列（n）以及数灰度图像矩阵序列（如：5553444444332322）。后运行程序，程序输出与Huffman编码、等长编码结合的又称编码。再将编码结果输入，译码得出原矩阵。三、测试数据1.输入 行数：3 列数：3 灰度图像矩阵为：111222333四、算法思想本程序编码的算法思想如下：（1）将输入的序列存入二维数组，并以行为单位记录符号出现的个数。（2）将符号名以及出现次数记录到rlc_node数组；（3）将rlc_node数组中的符号名进行Huffman编码，出现次数进行等长编码；（4）输出结果。本程序译码的算法思想如下：（1）首先，声明一个标识，f=1时进行Huffman译码，其思想同实验一，译码之后将f=0；（2）当f=0时，进行等长编码译码，将等长编码的二进制转换成十进制，输出结果并将f=1，如此循环下去，直到译完所有的码符号序列。五、模块划分1.建立游程编码结点class rlc_nodepublic int name;public int times;rlc_node()this.name=0;this.times=0;rlc_node(int name,int times)this.name=name;this.times=times;2.建立等长编码结点class dc_nodepublic String name;public int code_array;public String code;public int length;dc_node()this.code_array=new int50;this.name=""this.length=0;this.code=""for(int i=0;i<50;i+)this.code_arrayi=0;3. 将矩阵存入二维数组int a=new intmn;/存放矩阵int count1;int ii;int jj;String get=tf4.getText();char get1=get.toCharArray();/System.out.println(get1.length);for(count1=0;count1<m*n;)for(ii=0;ii<m;ii+)for(jj=0;jj<n;jj+)String temp;temp=String.valueOf(get1count1);count1+;aiijj=Integer.parseInt(temp);/System.out.print(temp);4. 形成数对rlc_node node_array=new rlc_noden*m;for(int i=0;i<m;i+)int count2=1;for(int j=0;j<n-1;j+)if(aij=aij+1