前言： 最近在学习哈夫曼编码时碰到了许多好玩且精妙的算法，不由自主的想把它提取出来。今天提取出如何在知道字符对应的前缀编码表后将目标编码反解码为字符串。
前缀编码 如果在一个编码方案中,任何一个编码都不是其他任何编码的前缀(最左子串),则称该编码是前缀编码。
比如给出以下编码表： i:11, k:100, e:101 ,l:00 ,a:011 ,j:0100 ,v:0101 我们不难发现每个字符对应的编码都不是其他字符对应编码的前缀。前缀编码可用于无损压缩。
那么题目来了： 给出以下一串编码： 1100111001010011100101001110010101000110101011 再根据下面的编码表： i:11, k:100, e:101 ,l:00 ,a:011 ,j:0100 ,v:0101 将此串编码反编成对应的字符串。
解题思路： 1.将编码表以“编码–>字符"形式存入到map集合中 2.用字符串分割将编码串从第一个开始分割，比如首先分割第一位，得到”1“，尝试从map中以key为”1“取value，当取出为空，则说明map没有对应编码表，继续向后切割，取”11“，再次从map中以key取值，于是发现取到了字符 “i”,放入到list集合中去，那么取出部分便不再切割，接着取”0“，取”00“…直到编码取完。 3.根据取完后的list字符集拼成字符串即可。
参考代码如下：
在这里插入代码片public class Main3 { public static void main(String[] args) { //首先根据上面的编码表将编码对应字符分别存入到key，value中 Map<String,Character> map=new HashMap<String,Character>(); map.put("11",'i'); map.put("100",'k'); map.put("101",'e'); map.put("00",'l'); map.put("011",'a'); map.put("0100",'j'); map.put("0101",'v'); String pwd="1100111001010011100101001110010101000110101011"; //创建一个集合类，存放字符 List<Character> list=new ArrayList<>(); for(int i=0;i<pwd.length();) { int count=1; boolean flag=true;//判断是否拿到了字符 Character b=null; while(flag) { //递增取出key1 //i不动，让count移动，指定匹配下一个字符 String key=pwd.substring(i,i+count); b=map.get(key); if(b==null) {//说明没有匹配到 count++; }else {//说明匹配到了 flag=false; } } list.add(b); i+=count; } for(char c:list) { System.out.print(c); } } }输出结果：
