1
电子说
二进制数据压缩算法二进制是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码来表示的数。它的基数为2,进位规则是“逢二进一”,借位规则是“借一当二”,由18世纪德国数理哲学大师莱布尼兹发现。当前的计算机系统使用的基本上是二进制系统,数据在计算机中主要是以补码的形式存储的。计算机中的二进制则是一个非常微小的开关,用“开”来表示1,“关”来表示0。
20世纪被称作第三次科技革命的重要标志之一的计算机的发明与应用,因为数字计算机只能识别和处理由‘0’。‘1’符号串组成的代码。其运算模式正是二进制。19世纪爱尔兰逻辑学家乔治布尔对逻辑命题的思考过程转化为对符号“0‘’。‘’1‘’的某种代数演算,二进制是逢2进位的进位制。0、1是基本算符。因为它只使用0、1两个数字符号,非常简单方便,易于用电子方式实现。
二进制压缩
在编程时遇到每个数据只有两种状态,且 dfs 或者 bfs 时遍历时间复杂度高时,可以采用二进制压缩数据,尤其是二维数组。
1.二进制压缩一个二位数组
例如:
-+--
----
----
-+--
正常保存数据回使用二位数组,‘+’ -》 1,‘-’ -》 0,即
0100
0000
0000
010012345678910
如果我们采用二进制压缩为一个 int 类型的数据,正好用 16 位来表示。
这里有两种表示方法,其实都一样,一种先从上到下变为从高位到低位,一种是从上到下变为从低位到高位。
从低位到高位
int input = 0;
int[][] data = new int[4][4];
Scanner sc = new Scanner(System.in);
String line = “”;
for (int i = 0; i 《 4; i++) {
line = sc.next();
for (int j = 0; j 《 4; j++) {
data[dataIn++] = line.charAt(j);
}
}
for (int i = 0; i 《 16; i++) {
if (data[i] == ‘+’) {
input |= (1 《《 i);
// System.out.println(Integer.toBinaryString(input));
}
}1234567891011121314151617
从高位到低位
int input = 0;
Scanner sc = new Scanner(System.in);
String line = “”;
for (int i = 0; i 《 4; i++) {
line = sc.next();
for (int j = 0; j 《 4; j++) {
input = input 《《 1;
input = line.charAt(i) == ‘+’ ? input + 1 : input;
}
}
LZFSE
1,zlib和gzip都对deflate进行了封装,比deflate多了数据头和尾
1,苹果开源了新的无损压缩算法 LZFSE ,该算法是去年在iOS 9和OS X 10.10中 引入 的。按照苹果公司的说法,LZFE的压缩增益和ZLib level 5相同,但速度要快2~3倍,能源效率也更高。
LZFSE基于Lempel-Ziv,并使用了 有限状态熵编码,后者基于Jarek Duda在
非对称数字系统(ANS)方面所做的熵编码工作。简单地讲,ANS旨在“终结速度和比率的平衡”,既可以用于精确编码,又可以用于快速编码,并且具有数据加密功能。使用ANS代替更为传统的
Huffman和 算术编码方法的压缩库 越来越多,LZFSE就位列其中。
显然,LZFSE的目标不是成为最好或最快的算法。事实上,苹果公司指出,
LZ4的压缩速度比LZFSE快,而 LZMA提供了更高的压缩率,但代价是比Apple
SDK提供的其他选项要慢一个数量级。当压缩率和速度几乎同等重要,而你又希望降低能源效率时,LZFSE是苹果推荐的选项。
GitHub上提供了LZFSE的参考实现。在MacOS上构建和运行一样简单:
$ xcodebuild install DSTROOT=/tmp/l***se.dst
如果希望针对当前的iOS设备构建LZFSE,可以执行:
xcodebuild -configuration “Release” -arch armv7 install DSTROOT=/tmp/l***se.dst
除了 API文档之外,苹果去年还提供了一个 示例项目,展示如何使用LZFSE 进行块和流压缩,这是一个实用的LZFSE入门资源。
LZFSE是在谷歌 brotli之后发布的,后者在去年开源。与LZFSE相比,brotli 似乎是针对一个不同的应用场景进行了优化,比如压缩静态Web资产和Android APK,在这些情况下,压缩率是最重要的。
全部0条评论
快来发表一下你的评论吧 !