java哈夫曼树的编码解码.zip

package suanfaji; import java.util.*; public class HFmanTree { public Treejie tou; public Map<String,String> map; public Map<String,String> fanmap; public String erjinzhi; public String yuan; public HFmanTree() { } public HFmanTree(String yuan) { create(yuan); this.map=getbianma(); this.fanmap=getbianma2(map); this.erjinzhi=getErJinZhi(fanmap,yuan); this.yuan=erZhuanString(erjinzhi,map); } /** * 创建一个哈夫曼树； * @param s */ public void create(String s){ List<Treejie> list=new ArrayList<>(); Map<String,Integer> map=hfman(s); Set<String> set=map.keySet(); for(String d:set){ Treejie c=new Treejie(d,map.get(d)); list.add(c); } while(list.size()!=1){ kuaipai(list,0,list.size()-1); Treejie x=list.get(0); Treejie y=list.get(1); list.remove(0); list.remove(0); Treejie dai=new Treejie(x.shu+y.shu); dai.left=x; dai.right=y; list.add(dai); } tou=list.get(0); } /** * 将二进制数字转换为字符串 * @param result * @param map * @return */ public String erZhuanString(String result,Map<String,String> map){ String hei=""; String daan=""; Map<String,String> map2=map; for(int i=0;i<result.length();i++){ hei=hei+result.charAt(i); if(map2.containsKey(hei)){ daan=daan+map2.get(hei); hei=""; } } return daan; } /** * 得到一个二进制编码 * @param map * @param ss * @return */ public String getErJinZhi(Map<String,String> map,String ss){ Map<String,String> map1=map; String result=""; for(int i=0;i<ss.length();i++){ result=result+map1.get(ss.charAt(i)+""); } return result; } /** * 得到一个字符与哈夫曼编码的对应关系 * @return */ public Map<String,String> getbianma(){ Treejie zhegeshu=this.tou; Map<String,String> map=new HashMap<>(); String b=""; biali(zhegeshu,map,b); return map; } /** * 得到一个字符与哈夫曼编码的反过来的对应关系 * @param map * @return */ public Map<String,String> getbianma2(Map<String,String> map){ Set<Map.Entry<String, String>> entries = map.entrySet(); Map<String,String> map1=new HashMap<>(); for(Map.Entry<String, String> s:entries){ map1.put(s.getValue(),s.getKey()); } return map1; } private static void biali(Treejie t, Map<String, String> map, String b){ if(t.left==null && t.right==null){ map.put(b, t.value); return; } if(t.left!=null){ biali(t.left,map,b+"0"); } if (t.right!=null ){ biali(t.right,map,b+"1"); } } private static void kuaipai(List<Treejie> list, int left, int right){ int i=left; int j=right; if(left>right){ return; } Treejie temp=list.get(left); while(i!=j){ while(list.get(j).shu>=temp.shu && i<j){ j--; } while(list.get(i).shu<=temp.shu && i<j){ i++; } Treejie mid=list.get(j); Treejie mid2=list.get(i); list.set(j,mid2); list.set(i,mid); } Treejie zan=list.get(i); list.set(left,zan); list.set(i,temp); kuaipai(list,left,j-1); kuaipai(list,j+1,right); } private static Map<String,Integer> hfman(String s){ Map<String,Integer> map=new HashMap<>(); for(int i=0;i<s.length();i++){ if(map.containsKey(s.charAt(i)+"")){ int re= map.get(s.charAt(i)+""); map.put(s.charAt(i)+"",re+1); }else{ map.put(s.charAt(i)+"",1); } } return map; } public static void main(String[] args) { HFmanTree tree=new HFmanTree("sdfcvxgrsdfwerwrgsadddaqqwegx"); System.out.println(tree.erjinzhi); System.out.println(tree.fanmap); System.out.println(tree.yuan); } }