读数据压缩入门笔记03_VLC
(相关资料图)
1.概率、熵与码字长度
1.1.数据压缩的目的
1.1.1.给定一个数据集中的符号，将最短的编码分配给最可能出现的符号
1.2
1.2.1.当P(A)=P(B)，也就是两个符号等可能出现时，数据集对应的熵取最大值LOG2（符号的个数），此时数据集很难压缩
1.2.2.其中一个符号出现的可能越大，数据集的熵值就越小，此时数据集也越容易压缩
1.2.3.对只包含两个符号的数据集来说，两个符号互换概率不影响其熵值
1.3.启示
1.3.1.随着数据集的冗余度下降，它的熵在变大，其最大值为数据集中不同符号个数的LOG2值
1.3.2.数据集中一个符号出现的概率越大，整个数据集的熵就越小，数据集也就越容易压缩
1.3.3.码字的长度与符号的出现概率密切相关，而与符号本身没有太大关系
2.VLC算法
2.1.在过去的40多年中，人们创造了数百种VLC算法
2.2.在为数据集选择一种VLC编码方法的考虑因素
2.2.1.数据集的整体大小
2.2.2.数据范围
2.2.3.计算各个符号的出现概率
2.2.4.如果不这样做，得到的结果可能就是，数据集的大小不但没有压缩，有可能反而比原来的数据集还大
2.3.存在的主要问题
2.3.1.它们不按字节 / 字 / 整型对齐
2.3.2.对于大的数值N，为了方便解码，其码字长度的增长速度一般会超过lb(N)个二进制位
2.3.3.解码的速度很慢（每次只能读取一个二进制位）
2.3.4.只能用于表示压缩数据流，没有其他应用
3.设计VLC集的码字原则
3.1.越频繁出现的符号，其对应的码字越短
3.2.码字需满足前缀性质
4.前缀性质
4.1.如果一个码字是另一个码字的前缀，那么用VLC解码二进制流就会很难
4.2.某个码字被分配给一个符号之后，其他的码字就不能用该码字作为前缀
4.2.1.每个符号都能通过其码字前缀唯一地确定
4.3.前缀性质是VLC能正常工作所必须具有的性质
4.3.1.与二进制表示相比，VLC要更长一些
5.唯一可译码
5.1.uniquely decodable codes
6.非奇异码
6.1.nonsingular codes
7.每一种前缀编码都是唯一可译的和非奇异的
8.VLC编码步骤
8.1.遍历数据集中的所有符号并计算每个符号的出现概率
8.1.1.画出数据集中所有符号的直方图
8.2.根据概率为每个符号分配码字，一个符号出现的概率越大，所分配的码字就越短
8.2.1.根据出现的频数对直方图进行排序
8.2.2.给每个符号分配一个VLC，从VLC集中码字最短的开始
8.3.再次遍历数据集，对每一个符号进行编码，并将对应的码字输出到压缩后的数据流中
9.VLC解码步骤
9.1.由于码字的长度并非是固定的，因此解码过程还是稍微有些复杂
9.2.解码的时候，我们会一二进制位一二进制位地读取数据，直到读取的二进制位流与其中的某个码字相匹配
9.3.一旦匹配，就会输出相应的符号，并继续读取下一个码字
10.摩尔斯码
10.1.1836年
10.1.1.画家Samuel F. B. Morse
10.1.2.物理学家Joseph Henry
10.1.3.机械师Alfred Vail
10.1.4.发明了第一套电报系统
10.2.克劳德•香农
10.2.1.摩尔斯码方面的专家
10.3.最简单的编码文本信息的方法
10.3.1.用数字126来编码AZ的英文字母
10.4.发送一次信息所需要的人工操作次数太多
10.4.1.物理硬件（发报机设备）和人工硬件(也就是操作人员的手腕）的磨损比预期的要快，解决方法则是使用统计来减少工作量
10.5.对符号分配变长编码（variable-length codes，VLC）的最初实现之一
10.6.为英语字母表中的每一个字符都分配了或长或短的脉冲，一个字母用得越频繁，其编码也就越短、越简单
10.6.1.目的则在于减少传输信息过程中所需要的总工作量
11.通用编码
11.1.universal codes
11.2.一种将整数转换为VLC的独特方法
11.3.一类特殊的前缀编码
11.4.为正整数赋上一个长度可变的二进制码字
11.5.数值越小，其对应的码字也越短
11.5.1.因为假定小整数比大整数出现得更频繁
12.二进制编码
12.1.不满足前缀性质
12.2.用B(n)来表示整数n的标准二进制表示
12.3.beta编码或二进制编码
12.4.给定0~N的任意整数，都能用1+floor(lb(n))个二进制位来表示
12.4.1.只要提前知道N的值，就能通过固定长度表示法来避开前缀问题
12.4.2.如果不能提前知道数据集中有多少个不同的整数，就不能用固定长度表示法
13.一元码
13.1.满足前缀性质
13.2.任意正整数N，它的一元码表示都是N-1个1后面跟着1个0
13.2.1.4的一元码表示为1110
13.3.整数N的一元码长度也是N个二进制位
13.4.将一元码应用在那些前一个符号的出现概率是后一个符号2倍的数据集上，效果最佳
13.5.如果每个整数N的出现概率P(N)服从指数分布2^(-N)，即1/2、1/4、1/8、1/16、1/32，其他以此类推，就可以使用一元码进行编码
14.Peter Elias
14.1.1923年11月23日生
14.2.1955年，他就引入了卷积码（convolutional codes），作为分组码（block codes）的一种替代方法
14.3.建立了二进制删除信道（binary erasure channel），并提出了用纠错码的列表译码（list decoding of error-correcting codes）来代替唯一可译码（unique decoding）
14.4.Elias gamma编码
14.4.1.用于事先无法确定其上界的整数的编码
14.4.1.1.不知道最大的整数会是多大
14.4.2.对整数n的出现概率P(n)=1/(2n*n)的情形比较适用
14.4.3.最主要的思想是不再对整数直接编码，而是用其数量级作为前缀
14.4.3.1.相应的码字就由两部分组成，即与此整数相当的2的次幂再加上余数
14.4.4.工作原理
14.4.4.1.找出最大的整数N，使其满足2N＜n＜2(N+1)，并且将n表示为n=2^N+L这样的形式
14.4.4.1.1.L=n-2^N
14.4.4.1.2.n=12,23=8,24=16,23＜n＜24,N=3
14.4.4.1.3.L=12-2^3=4
14.4.4.2.用一元码表示N
14.4.4.2.1.N=3,一元码110
14.4.4.3.将L表示为长为N的二进制编码，并加在步骤(2)中得出的一元码之后
14.4.4.3.1.有了这样的对称性，后面才能顺利解码
14.4.4.3.2.L=4，其对应的长度为3的二进制码为100
14.4.4.3.3.将前两个步骤得出的编码连接，就得到了最终的输出110100
14.5.Elias delta编码
14.5.1.对整数N的出现概率P(N)等于1/[2n(lb(2n)*lb(2n))的数据集来说是理想的选择
14.5.2.工作原理
14.5.2.1.将要编码的数N用二进制表示
14.5.2.1.1.将N=12表示为二进制1100
14.5.2.2.数一下N的二进制位数，并将这个位数转化为二进制，作为C
14.5.2.2.1.12的二进制表示共有4位，将4表示为二进制，即C = 100
14.5.2.3.去掉N的二进制表示的最左边一位，这个值肯定是1
14.5.2.3.1.去掉N=12的二进制表示的最左一位，得到100
14.5.2.4.将C的二进制表示加在去掉最左边一位后的N的二进制表示之前
14.5.2.4.1.将C = 100加到上一步骤所得的结果之前，得到100100
14.5.2.5.在上一步骤所得的结果前加上C的二进制位数减1个0作为最终的编码
14.5.2.5.1.将C的二进制位数减1，即3-1 = 2，在上一步骤所得的结果前加上2个0，由此得到12的最终编码为00100100
15.谷歌的Varint算法
15.1.最基本的概念早在1972年就提出
15.2.2010年作为“避免压缩整数”（escaping for compressed integers）而被重新引入
15.3.是一种表示整数的方法，它用一个或多个字节来表示一个整数，数值越小用的字节数越少，数值越大用的字节数越多
15.3.1.结合了VLC的灵活性和现代计算机体系结构的高效率，是一种很好的混合方法
15.3.2.既允许我们表示可变范围内的整数，同时还对自身的数据进行了对齐以提高解码的效率，达到了双赢
15.4.方法
15.4.1.将几个字节连接起来表示整数
15.4.2.并用每个字节的MSB作为布尔标志，来判断当前的字节是否为该整数的最后一个字节
15.4.3.每个字节的低7位则用来存储该数的二进制补码（two"s complement representation）
15.4.4.整数1可以用一个字节表示，因此它的MSB不需要设置，可表示为00000001
15.5.示例
15.5.1.10101100 00000010
15.5.1.1.10101100 00000010 → 0101100 0000010
15.5.1.1.1.删掉每个字节的MSB
15.5.1.1.1.1.它的作用只是判断当前字节是否是最后一个字节
15.5.1.1.1.2.第一个字节的MSB已经设置为1，因为用Varint方法来表示，该数需要多个字节
15.5.1.2.0101100 0000010
15.5.1.2.1.将剩下的两个7二进制位的数据顺序颠倒一下
15.5.1.2.1.1.用Varint方法表示时，低位的字节在前
15.5.1.3.0000010 0101100
15.5.1.3.1.将二进制表示转换为十进制数，就得到了最终的数值300
鹊踏枝冯延巳清明（鹊踏枝冯延巳）
« 上一篇
最新头条
-
出品 36氪未来消费撰文 彭倩头图来源 小红书今年夏天，走进优衣库门店的女孩们可能会发现，无论是T恤、开衫 -
河南仙佑集团了解到，随着人们对于健康关注的日益增加，膏药行业也得到了快速的发展。膏药作为一种传统...
-
在数字化背景下，交通运输的趋势是数字化、网联化和智能化，汽车发展的趋势是电动化、网联化、智能化—... -
今年是我市“优化营商环境攻坚年”“招商引资突破年”。攻坚突破要有勇气和魄力，更要有恒心和毅力。要... -
通讯员余丽艳“比赛场地的变电站责任最大，我年龄大，工作时间长，经验应该也比年轻人丰富，所以我要求... -
成都的大熊猫花花突然之间成了顶流网红，在短视频平台上，花花的视频动辄点赞量破百万。每天，成都大熊猫繁 -
导读1、办理的联通宽带带宽不同，速率也相应不同，如2M宽带下载速率理论值为256KB S，各地的宽带资费和优惠 -
北京时间2023年6月1日，英雄联盟LPL夏季赛常规赛第一周第四日将分别迎来BLG对阵OMG、WBG对阵JDG这两场让人 -
5月31日北向资金增持1 91万股帝科股份。近5个交易日中，获北向资金增持的有2天，累计净增持14 2万股。近20 -
1、转眼又是一年，中秋将至。去年的中秋之夜还历历在目，爸爸的那席话仍在耳畔回响。2、去年八月十五，中国
-
在蔚来的二代车中，真正走量的ET5的销量并没有取得爆款，真说“你买我推荐，我买我不买”那还得是咱小屏爱 -
60寸液晶电视外型尺寸1、LCM的尺寸一般都是指对角线的长度。60INCH等于1524mm2、如果按16：9计算，应该是 -
1、即《朱子家训》又名《朱子治家格言》、《朱柏庐治家格言》，是以家庭道德为主的启蒙教材。2、作者朱用纯 -
蓝绿白2024人选各就各位，各界聚焦蓝、白若不合，恐难赢过绿。民主进步党台北市议员陈贤蔚接受中评社专访分 -
1、南宁南湖：南宁南湖：在广西南宁市东南。2、湖面积1900亩。3、上世纪50年代初在邕江古河床遗址筑堤蓄水 -
北京5月31日电《经济参考报》5月31日刊发文章《多部门联动护航灵活就业举措上新》。文章称，新经济业态催生 -
天空体育消息，凯尔特人主教练波斯特科格鲁是目前热刺换帅的头号候选。本赛季，波斯特科格鲁率领凯尔特人赢 -
今天是5月31日星期三！茸茸给大家带来了今天的坛内新闻聚焦，喜欢的小伙伴们可以点个关注~今天的重点关注内 -
来源：中国新闻网中新网5月31日电据路透社报道，当地时间31日，德国外交部发言人克里斯托弗·伯格宣布，... -
格隆汇5月31日丨新娱科控股(06933 HK)宣布，于有关期间，凭藉我们在金融市场、风险管理及资产管理方面的专 -
你知道吗？有种心灵感应是：你盯着一个人看，心里默念，“快看我！快看我！”，他可能真的会回头看你。... -
近日，在安徽合肥举行的“投资安徽行”系列活动启动大会上，大众集团、中国建材、比亚迪、深创投等700余... -
广州市人民政府办公厅发布关于印发2023年广州金融支持实体经济高质量发展行动方案的通知。行动方案提出，鼓 -
5月27日晚上，2023年清城区“竞争先·致青春”青年音乐会在江滨公园演艺广场顺利举行，唱响了清城区青年... -
在近期的听证会上，动视法律顾问称，英国CMA在为期32周的调查中只花了4周时间在云游戏上。
相关头条
-
环球热资讯！女装集体缩水，优衣库也走起“女团风”
-
仙佑膏药：膏药行业拓展应用领域，满足多样化需求
-
优化营商环境要敢于较真碰硬
-
南京联通宽带网速怎么样（南京联通宽带）
-
帝科股份（300842）：5月31日北向资金增持1.91万股
-
每日视点！月到中秋分外明的作文（月到中秋分外明的作文怎么写）
-
【世界快播报】60英寸电视长宽是多少_60英寸电视长宽是多少
-
陈贤蔚：绿2024没那么乐观赖清德要谨慎
-
世界热议:多部门联动护航 灵活就业举措上新
-
乐享其闻：限时免费领取两款游戏|Epic 第三款神秘游戏可能是《午夜猎魂》 天天快看点
-
新娱科控股(06933.HK)：收购及出售加密货币_全球新资讯
-
投资安徽！中行、大众、比亚迪等加盟安徽招商“合伙人”|天天热点
-
清城区文化艺术月｜青年音乐会，青春正当燃！-全球快播
-
AI热催生PCB强劲需求！多家上市公司官宣应用落地 哪些品类受益？-全球热推荐
-
债市日报：5月31日
广告
X 关闭
神游
- 椰树集团直播带货风格引争议 网友评论一直行走在擦边最前沿
- 人民银行首度下调个人住房公积金贷款利率 满足改善性住房需求还有空间
- 狼能像狗一样“黏人”吗 确实能够像狗一样对人类产生依恋
- 全球首套万吨级绿氢流化床高效炼铁示范项目开工 助力我国钢铁工业绿色低碳创新发展
- 科学家解密地球最大陨石坑 确定数十亿年前的陆地分布
- 具有能量转移作用机制的手性催化人工光酶诞生 突破生产局限性
- 气候变暖引起鳗草南界北移 揭示全球气候变化对海草床生态系统潜在影响
- 多部门联合部署保护修复长江母亲河 考核试点工作已全面启动
- 三峡地区发现植物新物种 中文名命名为“三峡白前”
- 古老颌鱼化石发现3.8亿年历史心脏 迄今最古老心脏
广告
X 关闭