Welcome 微信登录

首页 / 操作系统 / Linux / Java 哈夫曼编码反编码的实现

Java 哈夫曼编码反编码的实现：
  1. //哈弗曼编码的实现类   
  2. public class HffmanCoding {  
  3.     private int charsAndWeight[][];// [][0]是 字符，[][1]存放的是字符的权值（次数）   
  4.     private int hfmcoding[][];// 存放哈弗曼树   
  5.     private int i = 0;// 循环变量   
  6.     private String hcs[];  
  7.   
  8.     public HffmanCoding（int[][] chars） {  
  9.         // TODO 构造方法   
  10.         charsAndWeight = new int[chars.length][2];  
  11.         charsAndWeight = chars;  
  12.         hfmcoding = new int[2 * chars.length - 1][4];// 为哈弗曼树分配空间   
  13.     }  
  14.   
  15.     // 哈弗曼树的实现   
  16.     public void coding（） {  
  17.         int n = charsAndWeight.length;  
  18.         if （n == 0）  
  19.             return;  
  20.         int m = 2 * n - 1;  
  21.         // 初始化哈弗曼树   
  22.         for （i = 0; i < n; i++） {  
  23.             hfmcoding[i][0] = charsAndWeight[i][1];// 初始化哈弗曼树的权值   
  24.             hfmcoding[i][1] = 0;// 初始化哈弗曼树的根节点   
  25.             hfmcoding[i][2] = 0;// 初始化哈弗曼树的左孩子   
  26.             hfmcoding[i][3] = 0;// 初始化哈弗曼树的右孩子   
  27.         }  
  28.         for （i = n; i < m; i++） {  
  29.             hfmcoding[i][0] = 0;// 初始化哈弗曼树的权值   
  30.             hfmcoding[i][1] = 0;// 初始化哈弗曼树的根节点   
  31.             hfmcoding[i][2] = 0;// 初始化哈弗曼树的左孩子   
  32.             hfmcoding[i][3] = 0;// 初始化哈弗曼树的右孩子   
  33.         }  
  34.   
  35.         // 构建哈弗曼树   
  36.         for （i = n; i < m; i++） {  
  37.             int s1[] = select（i）;// 在哈弗曼树中查找双亲为零的 weight最小的节点   
  38.             hfmcoding[s1[0]][1] = i;// 为哈弗曼树最小值付双亲   
  39.             hfmcoding[s1[1]][1] = i;  
  40.             hfmcoding[i][2] = s1[0];// 新节点的左孩子   
  41.             hfmcoding[i][3] = s1[1];// 新节点的右孩子   
  42.             hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];// 新节点的权值是左右孩子的权值之和   
  43.         }  
  44.   
  45.     }  
  46.   
  47.     // 查找双亲为零的 weight最小的节点   
  48.     private int[] select（int w） {  
  49.         // TODO Auto-generated method stub   
  50.         int s[] = { -1, -1 }, j = 0;// s1 最小权值且双亲为零的节点的序号 ， i 是循环变量   
  51.         int min1 = 32767, min2 = 32767;  
  52.         for （j = 0; j < w; j++） {  
  53.             if （hfmcoding[j][1] == 0） {// 只在尚未构造二叉树的结点中查找（双亲为零的节点）   
  54.                 if （hfmcoding[j][0] < min1） {  
  55.                     min2 = min1;  
  56.                     s[1] = s[0];  
  57.                     min1 = hfmcoding[j][0];  
  58.                     s[0] = j;  
  59.   
  60.                 } else if （hfmcoding[j][0] < min2） {  
  61.                     min2 = hfmcoding[j][0];  
  62.                     s[1] = j;  
  63.                 }  
  64.             }  
  65.         }  
  66.   
  67.         return s;  
  68.     }  
  69.   
  70.     public String[] CreateHCode（） {// 根据哈夫曼树求哈夫曼编码   
  71.         int n = charsAndWeight.length;  
  72.         int i, f, c;  
  73.         String hcodeString = "";  
  74.         hcs = new String[n];  
  75.         for （i = 0; i < n; i++） {// 根据哈夫曼树求哈夫曼编码   
  76.             c = i;  
  77.             hcodeString = "";  
  78.             f = hfmcoding[i][1]; // f 哈弗曼树的根节点   
  79.             while （f ！= 0） {// 循序直到树根结点   
  80.                 if （hfmcoding[f][2] == c） {// 处理左孩子结点   
  81.                     hcodeString += "0";  
  82.                 } else {  
  83.                     hcodeString += "1";  
  84.                 }  
  85.                 c = f;  
  86.                 f = hfmcoding[f][1];  
  87.             }  
  88.             hcs[i] = new String（new StringBuffer（hcodeString）.reverse（））;  
  89.         }  
  90.         return hcs;  
  91.     }  
  92.   
  93.     public String show（String s） {// 对字符串显示编码   
  94.         String textString = "";  
  95.         char c[];  
  96.         int k = -1;  
  97.         c = new char[s.length（）];  
  98.         c = s.toCharArray（）;// 将字符串转化为字符数组   
  99.         for （int i = 0; i < c.length; i++） {  
  100.             k = c[i];  
  101.             for （int j = 0; j < charsAndWeight.length; j++）  
  102.                 if （k == charsAndWeight[j][0]）  
  103.                     textString += hcs[j];  
  104.         }  
  105.         return textString;  
  106.   
  107.     }  
  108.   
  109.     // 哈弗曼编码反编译   
  110.     public String reCoding（String s） {  
  111.   
  112.         String text = "";// 存放反编译后的字符   
  113.         int k = 0, m = hfmcoding.length - 1;// 从根节点开始查询   
  114.         char c[];  
  115.         c = new char[s.length（）];  
  116.         c = s.toCharArray（）;  
  117.         k = m;  
  118.         for （int i = 0; i < c.length; i++） {  
  119.             if （c[i] == "0"） {  
  120.                 k = hfmcoding[k][2];// k的值为根节点左孩子的序号   
  121.                 if （hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0）// 判断是不是叶子节点，条件（左右孩子都为零）   
  122.                 {  
  123.                     text += （char） charsAndWeight[k][0];  
  124.                     k = m;  
  125.                 }  
  126.             }  
  127.             if （c[i] == "1"） {  
  128.                 k = hfmcoding[k][3];// k的值为根节点右孩子的序号   
  129.                 if （hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0）// 判断是不是叶子节点，条件（左右孩子都为零）   
  130.                 {  
  131.                     text += （char） charsAndWeight[k][0];  
  132.                     k = m;  
  133.                 }  
  134.   
  135.             }  
  136.         }  
  137.         return text;  
  138.     }  
  139. }  
  140.   
  141. 调用的时候直接调用该类就行了  
  142.   
  143. eg ：  
  144.   
  145. int chars[][] ；  
  146.   
  147. String s =“101010110”；  
  148.   
  149. HffmanCoding hfc = new HffmanCoding（chars）;  
  150.   
  151. hfc.coding（）;//哈弗曼树   
  152. String s[] = hfc.CreateHCode（）;//哈弗曼编码   
  153.   
  154. s=hfc.show（s）；  
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图