Huffman二进制编码以及文本的压缩与解压

news/2024/10/24 22:33:55/

目录

  • Huffman树转化成二进制编码
  • 文本压缩
  • 文本解压

Huffman树转化成二进制编码

   在上一篇博客的末尾，将Huffman树转化成了01 构成的字符串，显然在实际应用中不是这种操作。我们实际想要的是01构成的一串bits；举个例子：字符"A" 编码：0100 0001（8bit），假设我们重新编码之后字符 "A" 的路径是01，只占2个bit，应该用 01（bit）表示，而不是字符类型的"01"，如果用字符类型的01来重新编码，那经过Huffman编码之后的数据比原本的数据还大。因此需要改进一下。

   如果文本包含很多字符，那么从root节点到根节点的路径可能会很长。如果将二进制路径保存到int型变量中，路径长度超过32位那么一个int变量就不能完整保存路径。因此只能使用数组来保存路径，可以用byte，short，int，long。选择适中的int[]或者知道有很多字符时，可以选择long[]。还是要根据具体情况分析，下面采用long[]类型来保存路径。

在这里插入图片描述

public void bitCode(HMNode root,Map<Character,long[]> huffmanCode,String code){if(root.leaf){System.out.println(root.str+ " -> " + code);huffmanCode.put(root.str,convertBits(code));return;}if(root.left != null){bitCode(root.left,huffmanCode,code+"0");}if(root.right != null){bitCode(root.right,huffmanCode,code+"1");}}//将字符串转化成bitspublic long[] convertBits(String code){int len = code.length() ;int codeLength = len% 64 ==0 ? len/64:len/64+1;int index = 1;int offset = 63;long[] bitCodes = new long[codeLength+1];char[] codes = code.toCharArray();for (int i = 0; i < codes.length; i++) {long bitCode = bitCodes[index];long c = codes[i]-'0';bitCode |= (c<<offset);bitCodes[index]=bitCode;if(offset== 0){offset = 63;index += 1;}else{offset -= 1;}}bitCodes[0]=(long)len;//第一个数字是用来记录编码的长度；return bitCodes;}

测试：

@Testpublic void test(){String text = "aaabbbbbccccccddddee";HMNode root =buildHuffManTree(text);Map<Character,long[]>code = new HashMap<>();bitCode(root,code,"");System.out.println("+++++++++++++++++++++++++++++++++++++++++++++");code.forEach((key,val)->{long codeLen = val[0];System.out.print(key+"编码长度："+codeLen +"\tcode: ");for (int i = 1; i < val.length-1; i++) {System.out.print(" "+val[i]);}System.out.print(" "+(val[val.length-1]>>>(64-codeLen)));System.out.println("\n");});}=========================================res=================================================
d -> 00
c -> 11
b -> 01
e -> 100
a -> 101
+++++++++++++++++++++++++++++++++++++++++++++
d编码长度：2	 code: 0b编码长度：2	 code: 1a编码长度：3	 code: 5c编码长度：2	 code: 3e编码长度：3	 code: 4

文本压缩

  EncodeInfo是保存压缩后的文本，设置成了一个二维数组。现在想想其实没必要，因为必定是一边压缩一边保存到磁盘的。不可能把数据完全压缩之后再保存。

  遍历文本将每一个字符的Huffman二进制码数组按顺序保存到压缩文本的二维数组中，这个需要稍微熟悉下位运算。（保存到二位数组纯属折磨自己，搞得比较复杂了，之后再改吧）

   class EncodeInfo{List<List<Long>> encodes = new ArrayList<>();int lastLength = 0;//encodes最后一个list的最后一个long元素中，有效bit个数HMNode root;public EncodeInfo(HMNode root){List<Long> code = new ArrayList<>(ARRAY_SIZE);code.add(0L);encodes.add(code);this.root = root;}}static int ARRAY_SIZE = 1024;static int BIT_CELL_LENGTH = 64;public void encode(String text,EncodeInfo info){Map<Character,long[]>code = new HashMap<>();bitCode(info.root,code,"");for (char c : text.toCharArray()) {addBitCode(info,code.get(c));}}private void addBitCode(EncodeInfo info ,long[] bits){List<List<Long>> encodes = info.encodes;List<Long> codes = encodes.get(encodes.size()-1);//获取到最后一个List;//得到二进制码数组最后一个元素的有效bit数；long last = bits[0]%BIT_CELL_LENGTH == 0 ? BIT_CELL_LENGTH : bits[0] % BIT_CELL_LENGTH;for (int i = 1; i < bits.length-1; i++) {long b = bits[i];int size = codes.size();long val = codes.get(size-1) ;val |= (b >>> info.lastLength);//前半部分codes.set(size-1,val);long after = b << (BIT_CELL_LENGTH-info.lastLength);//后半部分codes = addLast(info,after);info.lastLength = info.lastLength == 0 ? 0: BIT_CELL_LENGTH-info.lastLength;}long lastBits = bits[bits.length-1];long val = codes.get(codes.size()-1);val |= (lastBits >>> info.lastLength);codes.set(codes.size()-1,val);if(last + info.lastLength < BIT_CELL_LENGTH){info.lastLength += last;}else if(last + info.lastLength == BIT_CELL_LENGTH){info.lastLength =0;addLast(info,0L);}else{lastBits<<= (BIT_CELL_LENGTH-info.lastLength);addLast(info,lastBits);info.lastLength +=(last-BIT_CELL_LENGTH);}}private List<Long> addLast(EncodeInfo info,long val){List<List<Long>> encodes = info.encodes;List<Long> codes = encodes.get(encodes.size() - 1);int size = codes.size();if(size == ARRAY_SIZE){codes = new ArrayList<>(ARRAY_SIZE);encodes.add(codes);}codes.add(val);return codes;}
  • 测试
@Testpublic void testEncode(){String text = " sfsdftechfdfhgjhtghrytthnhGGHMBDV打发士大夫SDCYUGERFASDSDW,.*&^%$#[]_+{};;;;;,.XCCCCC地方法规";int beforeEncode = text.getBytes().length;System.out.println("编码前：beforeEncode:"+beforeEncode +";");HMNode root =buildHuffManTree(text);EncodeInfo info =  new EncodeInfo(root);encode(text,info);info.encodes.forEach(x->{for (Long aLong : x) {System.out.println(aLong);}});System.out.println("最后一个long的有效bit个数："+info.lastLength);}
  • 结果
编码前：beforeEncode:103;
* -> 000000
夫 -> 000001
+ -> 000010
地 -> 000011
方 -> 000100
A -> 000101
B -> 000110
规 -> 000111
E -> 001000
F -> 001001
H -> 001010
M -> 001011
发 -> 001100
R -> 001101
打 -> 001110
U -> 001111
法 -> 010000
V -> 010001
W -> 010010
X -> 010011
Y -> 010100
[ -> 010101
] -> 010110
^ -> 010111
_ -> 011000
c -> 011001
e -> 011010
j -> 011011
士 -> 011100
n -> 011101
r -> 011110
y -> 011111
; -> 1000
{ -> 100100
} -> 100101
G -> 10011
C -> 1010
h -> 1011
S -> 11000
D -> 11001
f -> 11010
t -> 11011
, -> 111000
. -> 111001
d -> 111010
g -> 111011
s -> 111100-> 1111010
# -> 1111011
$ -> 1111100
% -> 1111101
& -> 1111110
大 -> 1111111
-727686570736772137
6538905317935103933
-2614557749356706589
2089122890596168205
2620082441562243324
-4620800053492013930
2459590903680641548
4901886719416074240
最后一个long的有效bit个数：16

   数字就是文本经过Huffman编码压缩之后保存的信息；每个long保存8byte信息；可以计算出来被压缩之后的byte数：8 * 7 + 16 = 72；比最原始的103要小一点。因为这段文本基本没有重复的，所以压缩效果不好。

文本解压

  在解压时按顺序读每一个bit位，对照Huffman树，如果是1就走右分支，如果是 0就走左分支。（这个还是要看之前怎么编码的，如果之前在构建Huffman树时，1表示左 ；0表示右那就按对应的方式解析）找到叶子节点就输出字符，然后继续顺序读读取bit知道将所有bit读完为止。

  • 代码
public String decode(EncodeInfo info){List<List<Long>> encodes = info.encodes;HMNode root = info.root;int endListIndex = encodes.size()-1;int endElementIndex = encodes.get(endListIndex).size()-1;HMNode prev = null;for (int i = 0; i < encodes.size(); i++) {List<Long> codes = encodes.get(i);for (int j = 0; j < codes.size(); j++) {if(i == endListIndex && j == endElementIndex){prev = parse(prev,codes.get(j),info.lastLength,info);}else{prev = parse(prev,codes.get(j),BIT_CELL_LENGTH,info);}}}return null;}/*** @param prev* @param bits* @param len long型变量的有效bit长度；* @param info* @return*/public HMNode parse(HMNode prev,long bits,int len,EncodeInfo info){long curBit = 0;while(prev != null && len > 0){curBit = (bits>>>(BIT_CELL_LENGTH-1));if(curBit == 1 ){prev = prev.right;}else{prev = prev.left;}bits<<=1;len--;if(prev.leaf){System.out.print(prev.str);if(len ==0)return null;elsebreak;}}if(len == 0)return prev;return parse(prev=info.root,bits,len,info);}
  • 测试
@Testpublic void testDecode(){String text = "急急急uu  ,.;/.'*&^%$广东福建的好的的德国费尔法的的发夫算法发生过和323434234123吧vDVD产生的";int beforeEncode = text.getBytes().length;System.out.println("编码前：beforeEncode:"+beforeEncode +";");HMNode root =buildHuffManTree(text);EncodeInfo info =  new EncodeInfo(root);encode(text,info);decode(info);System.out.println("\n+++++++++++++++");System.out.println(text);}
  • 结果

编码前：beforeEncode:121;
的 -> 000
2 -> 0010
4 -> 0011
广 -> 01000
D -> 01001
发 -> 01010
法 -> 01011
生 -> 01100-> 01101
. -> 01110
u -> 01111
过 -> 100000
和 -> 100001
福 -> 100010
尔 -> 100011
V -> 100100
算 -> 100101
东 -> 100110
^ -> 100111
$ -> 101000
% -> 101001
& -> 101010
' -> 101011
吧 -> 101100
产 -> 101101
* -> 101110
夫 -> 101111
, -> 110000
/ -> 110001
1 -> 110010
v -> 110011
德 -> 110100
费 -> 110101
建 -> 110110
; -> 110111
3 -> 1110
好 -> 111100
国 -> 111101
急 -> 11111
急急急uu  ,.;/.'*&^%$广东福建的好的的德国费尔法的的发夫算法发生过和323434234123吧vDVD产生的
+++++++++++++++
急急急uu  ,.;/.'*&^%$广东福建的好的的德国费尔法的的发夫算法发生过和323434234123吧vDVD产生的

http://www.ppmy.cn/news/5813.html

相关文章

Spring Cloud Alibaba Sentinel - - ＞流控规则初体验

Spring Cloud Alibaba Sentinel - - ＞流控规则初体验

源码地址&#xff1a;https://github.com/alibaba/Sentinel 新手指南&#xff1a;https://github.com/alibaba/Sentinel/wiki/新手指南#公网-demo 官方文档&#xff1a;https://sentinelguard.io/zh-cn/docs/introduction.html 注解支持文档&#xff1a;https://github.com/ali…
阅读更多...
Android---Banner轮播图

Android---Banner轮播图

轮播图是一种很常见的UI。Banner框架能够帮助我们快速开发&#xff0c;完成首页轮播图效果的需求。 1、导入Banner依赖 implementation io.github.youth5201314:banner:2.2.2 2、activity_main.xml布局。 banner_loop_time: 设置轮播间隔时间&#xff0c;默认3000&#xff…
阅读更多...
基于注解方式Spring Security忽略拦截

基于注解方式Spring Security忽略拦截

文章目录1.Spring Security忽略拦截配置2.基于配置文件注入2.1.添加配置2.2.修改Spring Security配置类2.3. 测试3.基于注解的方式过滤接口3.1.添加注解3.2.获取所有使用了IgnoreWebSecurity注解的接口访问路径3.3.测试1.Spring Security忽略拦截配置 关于Spring Securite的使…
阅读更多...
Flarum部署：从源码到docker到放弃

Flarum部署：从源码到docker到放弃

警告&#xff1a; 此篇文章前半段记录了我用代码部署flarum遇到的一些问题和解决办法&#xff0c;但是可能是由于我是在不熟悉php的框架结构&#xff0c;最终我还是选择了使用docker进行部署&#xff0c;请斟酌是否继续阅读本文。 Hello&#xff0c;大家好&#xff0c;我是内网…
阅读更多...
IU酒店释放轻中端投资活力，开启曲靖酒店新篇章

IU酒店释放轻中端投资活力，开启曲靖酒店新篇章

曲靖位于云南省东北部&#xff0c;是云南连接内地的重要陆路通道&#xff0c;素有“滇黔锁钥”、“入滇门户”、“云南咽喉”之称&#xff0c;是仅次于昆明的云南第二大城市。曾入选“中国十佳宜居城市”榜单10次的城市&#xff0c;拥有3000多年的文明史&#xff0c;早在三国魏…
阅读更多...
通过脚手架vue-cli创建一个vue项目

通过脚手架vue-cli创建一个vue项目

我需要在vue-demo文件下新建vue项目 步骤一 ①在该文件夹下打开集成终端 输入创建命令 命令 vue create 项目名称 &#xff0c;注意不要使用驼峰命名法 如果是第一次配置&#xff0c;有面的提示&#xff0c;这里说你这样速度会很慢的&#xff0c;用不用镜像啊&#xff0c;这…
阅读更多...
基于HOG、LBP完成特征工程，基于SVM/RF/XGBOOST/GBDT/CNN/DNN完成人脸识别+表情识别

基于HOG、LBP完成特征工程，基于SVM/RF/XGBOOST/GBDT/CNN/DNN完成人脸识别+表情识别

在我之前的文章中写过很多关于人脸识别和表情识别的文章&#xff0c;今天有一个项目的需求就是需要做两种或者是多种任务&#xff0c;我在开发完对应的模型之后就突然想到了之前做过的人脸识别和表情识别的项目&#xff0c;就想着是否可以基于机器学习/深度学习等方式来同时实现…
阅读更多...
打造飞一样的前端：vue3应用打包优化

打造飞一样的前端：vue3应用打包优化

目录前言优化vue3构建的几点措施采用CDN压缩JS按需加载按需加载vxe-table按需加载element-plus总结前言 vue3应用上线后&#xff0c;一直受困于加载过慢&#xff0c;昨天终于坐下来做些优化。本想切换到webpack打包&#xff0c;但还是坚持了vite。 优化vue3构建的几点措施 采…
阅读更多...
最新文章

Copyright @ 2022~2023