Java实现哈夫曼编码和解码

2022-03-05 07:51:27

最近无意中想到关于api返回值加密的问题，譬如我们的api需要返回一些比较敏感或者重要不想让截获者得到的信息，像如果是做原创图文的，文章明文返回的话则有可能被抓包者窃取。

关于请求时加密的方式比较多，像常见的如阿里某api就是根据所有参数ascii码升序排序并加盐加密，这样能避免黑客篡改请求值。那关于返回值加密的，我觉得用哈夫曼编码就不错。

大家都知道哈夫曼是用来做压缩解压的算法，通过哈夫曼压缩后的数据其实就相当于加密了，我们可以把返回值用哈夫曼算法压缩得到一串的0101，然后再随便头尾补个乱码什么的值，到客户端再把乱码去除，在一定程度上就能让截获者迷惑了，而且传输的数据量也小了一些，节省流量。

这里有一篇是讲java实现哈夫曼的。

题目：将一个字符串进行哈夫曼编码；编码过程中，会得到每个字符的编码，通过已知的每个字符的编码对之前的编码进行解码。

分析：

首先是哈夫曼编码算法，引用李泽年写的《多媒体技术教程》中对哈夫曼编码算法的描述：

•;
  • // 字符出现的次数
  • private int frequency = 0;
  • public char getC() {
  • return c;
  • }
  • public void setC(char c) {
  • this.c = c;
  • }
  • public int getFrequency() {
  • return frequency;
  • }
  • public void setFrequency(int frequency) {
  • this.frequency = frequency;
  • }
  • @Override
  • public String toString() {
  • return "Data [c=" + c + ", frequency=" + frequency + "]";
  • }
  • @Override
  • public int compareTo(Data o) {
  • if (this.frequency < o.getFrequency()) {
  • return -1;
  • } else if (this.frequency > o.getFrequency()) {
  • return 1;
  • } else {
  • return 0;
  • }
  • }
  • }

    • [java] view plain copy
    1. package com.liyuncong.algorithms.algorithms_huffman;
    2. import java.util.Map;
    3. /**
    4. * 对字符串编码后的结果：包括编码后的字符串和字符/编码对
    5. * @author yuncong
    6. *
    7. */
    8. public class EncodeResult {
    9. // 字符串编码后的结果
    10. private String encode;
    11. // 字符编码对
    12. private Map<Character, String> letterCode;
    13. public EncodeResult(String encode, Map<Character, String> letterCode) {
    14. super();
    15. this.encode = encode;
    16. this.letterCode = letterCode;
    17. }
    18. public String getEncode() {
    19. return encode;
    20. }
    21. public Map<Character, String> getLetterCode() {
    22. return letterCode;
    23. }
    24. }

    [java] view plain copy
    1. package com.liyuncong.algorithms.algorithms_huffman;
    2. public interface HuffmanAlgorithm {
    3. /**
    4. * 编码字符串。
    5. * @param str 指定的需要编码的字符串
    6. * @return 编码结果
    7. */
    8. public EncodeResult encode(String str);
    9. /**
    10. * 根据编码结果返回原来的字符串。
    11. * @param decodeResult 原来字符串的编码结果。
    12. * @return 解码出来的字符串。
    13. */
    14. public String decode(EncodeResult encodeResult);
    15. }

    [java] view plain copy
    1. package com.liyuncong.algorithms.algorithms_huffman;
    2. import java.util.ArrayList;
    3. import java.util.HashMap;
    4. import java.util.Map;
    5. import java.util.Set;
    6. import com.liyuncong.application.commontools.FileTools;
    7. public abstract class HuffmanAlgorithmAbstract implements HuffmanAlgorithm {
    8. @Override
    9. public EncodeResult encode(String str) {
    10. ArrayList<Node> letterList = toList(str);
    11. Node rootNode = createTree(letterList);
    12. Map<Character, String> letterCode = getLetterCode(rootNode);
    13. EncodeResult result = encode(letterCode, str);
    14. return result;
    15. }
    16. /**
    17. * 把一个字符串转化为节点列表
    18. * @param letters
    19. * @return
    20. */
    21. private ArrayList<Node> toList(String letters) {
    22. ArrayList<Node> letterList = new ArrayList<Node>();
    23. Map<Character, Integer> ci = new HashMap<Character, Integer>();
    24. for (int i = 0; i < letters.length(); i++) {
    25. Character character = letters.charAt(i);
    26. if (!ci.keySet().contains(character)) {
    27. ci.put(character, 1);
    28. } else {
    29. Integer oldValue = ci.get(character);
    30. ci.put(character, oldValue + 1);
    31. }
    32. }
    33. Set<Character> keys = ci.keySet();
    34. for (Character key : keys) {
    35. Node node = new Node();
    36. Data data = new Data();
    37. data.setC(key);
    38. data.setFrequency(ci.get(key));
    39. node.setData(data);
    40. letterList.add(node);
    41. }
    42. return letterList;
    43. }
    44. protected abstract Node createTree(ArrayList<Node> letterList);
    45. /**
    46. * 编码字符串。
    47. * @param letterCode 字符/编码对集合。
    48. * @param letters 指定的需要编码的字符串。
    49. * @return 编码结果
    50. */
    51. private EncodeResult encode(Map<Character, String> letterCode, String letters) {
    52. StringBuilder encode = new StringBuilder();
    53. for (int i = 0, length = letters.length(); i < length; i++) {
    54. Character character = letters.charAt(i);
    55. encode.append(letterCode.get(character));
    56. }
    57. EncodeResult result = new EncodeResult(encode.toString(), letterCode);
    58. return result;
    59. }
    60. /**
    61. * 获得所有字符编码对
    62. *
    63. * @param rootNode哈夫曼树的根节点
    64. * @return 所有字符编码对
    65. */
    66. private Map<Character, String> getLetterCode(Node rootNode) {
    67. Map<Character, String> letterCode = new HashMap<Character, String>();
    68. // 处理只有一个节点的情况
    69. if (rootNode.getLeftChild() == null && rootNode.getRightChild() == null) {
    70. letterCode.put(rootNode.getData().getC(), "1");
    71. return letterCode;
    72. }
    73. getLetterCode(rootNode, "", letterCode);
    74. return letterCode;
    75. }
    76. /**
    77. * 先序遍历哈夫曼树,获得所有字符编码对。
    78. *
    79. * @param rooNode 哈夫曼树根结点
    80. * @param suffix 编码前缀，也就是编码这个字符时，之前路径上的所有编码
    81. * @param letterCode 用于保存字符编码结果
    82. */
    83. private void getLetterCode(Node rooNode, String suffix,
    84. Map<Character, String> letterCode) {
    85. if (rooNode != null) {
    86. if (rooNode.getLeftChild() == null
    87. && rooNode.getRightChild() == null) {
    88. Character character = rooNode.getData().getC();
    89. letterCode.put(character, suffix);
    90. }
    91. getLetterCode(rooNode.getLeftChild(), suffix + "0", letterCode);
    92. getLetterCode(rooNode.getRightChild(), suffix + "1", letterCode);
    93. }
    94. }
    95. public String decode(EncodeResult decodeResult) {
    96. // 解码得到的字符串
    97. StringBuffer decodeStr = new StringBuffer();
    98. // 获得解码器
    99. Map<String, Character> decodeMap = getDecoder(decodeResult
    100. .getLetterCode());
    101. // 解码器键集合
    102. Set<String> keys = decodeMap.keySet();
    103. // 待解码的（被编码的）字符串
    104. String encode = decodeResult.getEncode();
    105. // 从最短的开始匹配之所以能够成功，是因为哈夫曼编码的唯一前缀性质
    106. // 临时的可能的键值
    107. String temp = "";
    108. // 改变temp值大小的游标
    109. int i = 1;
    110. while (encode.length() > 0) {
    111. temp = encode.substring(0, i);
    112. if (keys.contains(temp)) {
    113. Character character = decodeMap.get(temp);
    114. decodeStr.append(character);
    115. encode = encode.substring(i);
    116. i = 1;
    117. } else {
    118. i++;
    119. }
    120. }
    121. return decodeStr.toString();
    122. }
    123. /**
    124. * 获得解码器，也就是通过字母/编码对得到编码/字符对。
    125. *
    126. * @param letterCode
    127. * @return
    128. */
    129. private Map<String, Character> getDecoder(Map<Character, String> letterCode) {
    130. Map<String, Character> decodeMap = new HashMap<String, Character>();
    131. Set<Character> keys = letterCode.keySet();
    132. for (Character key : keys) {
    133. String value = letterCode.get(key);
    134. decodeMap.put(value, key);
    135. }
    136. return decodeMap;
    137. }
    138. }
    [java] view plain copy
    1. package com.liyuncong.algorithms.algorithms_huffman;
    2. import java.util.ArrayList;
    3. import java.util.HashMap;
    4. import java.util.Map;
    5. import java.util.Set;
    6. /**
    7. * 算法实现参考《多媒体技术教程》
    8. * @author yuncong
    9. *
    10. */
    11. public class HuffmanAlgorithmImpl1 extends HuffmanAlgorithmAbstract {
    12. /*
    13. * 创建哈夫曼树； 丢失了letterList中的数据，深拷贝letterList是需要完善的地方
    14. */
    15. @Override
    16. protected Node createTree(ArrayList<Node> letterList) {
    17. init(letterList);
    18. while (letterList.size() != 1) {
    19. int size = letterList.size();
    20. // 小的节点放在右边（眼睛看到的左边）
    21. Node nodeLeft = letterList.get(size - 1);
    22. Node nodeRight = letterList.get(size - 2);
    23. Node nodeParent = new Node();
    24. nodeParent.setLeftChild(nodeLeft);
    25. nodeParent.setRightChild(nodeRight);
    26. Data data = new Data();
    27. data.setFrequency(nodeRight.getData().getFrequency()
    28. + nodeLeft.getData().getFrequency());
    29. nodeParent.setData(data);
    30. letterList.set(size - 2, nodeParent);
    31. letterList.remove(size - 1);
    32. sort(letterList);
    33. }
    34. Node rootNode = letterList.get(0);
    35. return rootNode;
    36. }
    37. /**
    38. * 初始化 让节点列表有序
    39. */
    40. private void init(ArrayList<Node> letterList) {
    41. sort(letterList);
    42. }
    43. /**
    44. * 冒泡排序，把小的放在最后
    45. */
    46. private void sort(ArrayList<Node> letterList) {
    47. int size = letterList.size();
    48. // 处理只有一个元素的情况，也就是说，不需要排序
    49. if (size == 1) {
    50. return;
    51. }
    52. for (int i = 0; i < size; i++) {
    53. for (int j = 0; j < size - 1 - i; j++) {
    54. if (letterList.get(j).getData().getFrequency() < letterList
    55. .get(j + 1).getData().getFrequency()) {
    56. Node tempNode = letterList.get(j);
    57. letterList.set(j, letterList.get(j + 1));
    58. letterList.set(j + 1, tempNode);
    59. }
    60. }
    61. }
    62. }
    63. }

    [java] view plain copy
    1. package com.liyuncong.algorithms.algorithms_huffman;
    2. import static org.junit.Assert.*;
    3. import org.junit.Test;
    4. public class HuffmanAlgorithmImpl1Test {
    5. @Test
    6. public void testEncodeString() {
    7. HuffmanAlgorithmImpl1 huffmanImpl1 = new HuffmanAlgorithmImpl1();
    8. EncodeResult result = huffmanImpl1.encode("abcdda");
    9. System.out.println(result.getEncode());
    10. }
    11. @Test
    12. public void testDecode() {
    13. HuffmanAlgorithmImpl1 huffmanImpl1 = new HuffmanAlgorithmImpl1();
    14. EncodeResult result = huffmanImpl1.encode("abcdda");
    15. String decode = huffmanImpl1.decode(result);
    16. System.out.println(decode);
    17. }
    18. }

    原文地址：http://blog.csdn.net/l294265421/article/details/44778989

    上一篇：Spring EL method invocation example


    下一篇：animation-timing-function中的cubic-bezier(n,n,n,n)