读写二进制数据
基因组数据的压缩
游程编码
位图
霍夫曼压缩
前缀码和单词查找树
构造前缀码的单词查找树
写入和读取单词查找树
使用前缀码压缩
使用前缀码展开
LZW 压缩
LZW 的单词查找树
LZW 的单词查找树
LZW 压缩的展开
对数据进行压缩能够有效节省保存信息所需的空间和传输信息所需的时间. 虽然计算机存储设备的成本在不断降低, 但由于需要存储的数据在飞速膨胀, 压缩算法仍有非常重要的意义, 因为与以往相比, 数据被压缩后节省的空间会更大.
读写二进制数据
现代计算机系统中处理的所有类型的数据最终都是用二进制表示的, 可以将它们都看作一串比特的序列.
数据压缩分为无损压缩和有损压缩, 前者在压缩, 展开后不会丢失任何信息, 但后者不然. 有损压缩常被用于图像, 视频, 音乐的压缩. 对于无损压缩算法, 评价的标准为压缩率, 压缩率 = 压缩后体积 / 原始体积; 对于有损压缩算法, 评价标准除了压缩率外, 还有主观的质量感受等.
接下来只讨论无损压缩算法.
之前的算法设计输入输出时, 使用的都是基于 java 基础方法封装的 StdIn 和 StdOut, 它们处理的是由 Unicode 编码的字符流; 但由于压缩算法会涉及到对比特流的操作, 所以接下来使用 BinaryStdIn 和 BinaryStdOut,BinaryStdIn.readBoolean() 方法会从输入中读取一个比特并返回为布尔值, BinaryStdOut.write(boolean b) 方法则会向输出中写入一个比特.
基因组数据的压缩
接下来从初级的基因组压缩算法开始, 因为表示基因组的字符集只含有 A C T G 四个字符. 这种方法也适用于字符集大小固定且数量有限的场合.
如果将这四个字符直接用 ASCII 编码, 需要 4*8=32 位, 但其实只需要用两个位就可以表示 4 个值 (2^2=4). 这样 4 个字符只需要 2*4=8 位就可以了, 压缩率 = 8/32=25%.
由此可得对基因组数据的压缩方法:
- public static void compress(){
- Alphabet DNA=new Alphabet("ACTG");
- String s=BinaryStdIn.readString();
- int N=s.length();
- BinaryStdOut.write(N);
- for(int i=0;i<N;i++){
- int d=DNA.toIndex(s.charAt(i));
- BinaryStdOut.write(d,DNA.lgR());
- }
- BinaryStdOut.close();
- }
实例化 Alphabet 类时, 指定字符集只有 ACTG 这四个, DNA.lgR() 就等于 2, 每次输出 2 个比特. 比如遇到字符 A, 就用 0 表示, 二进制编码为 00, 字符 B 用 1 表示, 二进制编码为 01 等等.
展开时, 每次读取 2 个比特, 转换为整型数字, 然后根据这个数字去字符集中取得对应的字符.
- public static void expand(){
- Alphabet DNA=new Alphabet("ACTG");
- int w=DNA.lgR();
- int N=BinaryStdIn.readInt();
- for(int i=0;i<N;i++){
- char c=BinaryStdIn.readChar(w);
- StdOut.println("c="+c);
- char e=DNA.toChar(c);
- StdOut.println("e="+e);
- BinaryStdOut.write(DNA.toChar(c));
- }
- BinaryStdOut.close();
- }
游程编码
比特流中最简单的冗余形式就是一长串重复的比特, 游程编码就是利用这种冗余来压缩数据的经典方法, 在对位图的压缩中有很好的效果.
位图
位图经常用于保存图像和扫描文档, 下面是一张最简单的位图, 分辨率为 32*48, 图像为一个 "q" 字符, 用按行排列的比特流来表示位图数据, 所以这张简单的位图是没有颜色信息的, 或者说只有两种颜色.
- 00000000000000000000000000000000
- 00000000000000000000000000000000
- 00000000000000011111110000000000
- 00000000000011111111111111100000
- 00000000001111000011111111100000
- 00000000111100000000011111100000
- 00000001110000000000001111100000
- 00000011110000000000001111100000
- 00000111100000000000001111100000
- 00001111000000000000001111100000
- 00001111000000000000001111100000
- 00011110000000000000001111100000
- 00011110000000000000001111100000
- 00111110000000000000001111100000
- 00111110000000000000001111100000
- 00111110000000000000001111100000
- 00111110000000000000001111100000
- 00111110000000000000001111100000
- 00111110000000000000001111100000
- 00111110000000000000001111100000
- 00111110000000000000001111100000
- 00111111000000000000001111100000
- 00111111000000000000001111100000
- 00011111100000000000001111100000
- 00011111100000000000001111100000
- 00001111110000000000001111100000
- 00001111111000000000001111100000
- 00000111111100000000001111100000
- 00000011111111000000011111100000
- 00000001111111111111111111100000
- 00000000011111111111001111100000
- 00000000000011111000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000001111100000
- 00000000000000000000011111110000
- 00000000000000000011111111111100
- 00000000000000000111111111111110
- 00000000000000000000000000000000
- 00000000000000000000000000000000
取这个位图中的第 5 行来分析
00000000001111000011111111100000
这条长度 32 的字符串中, 含有: 10 个 0 - 4 个 1 - 4 个 0 - 9 个 1 - 5 个 0. 所有的比特字符串都是类似这样, 0 和 1 交替出现, 所以对于这条字符串, 就可以编码为 10,4,4,9,5, 如果用 4 比特表示长度, 并以连续的 0 作为开头, 就可以得到一个 20 位长的字符串 (不包含逗号):1010,0100,0100,1001,0101. 压缩率 = 20/32=62.5%.
4 位编码能表示的值只有 0 到 15, 在实际的应用中是不够的, 所以使用 8 位编码, 可以表示 0-255 之间的游程长度. 如果游程的长度超过 256, 就插入一个长度为 0 的游程, 这样可以确保所有的游程长度都不超过 256.
使用游程编码压缩的代码如下:
- public static void compress() {
- char cnt = 0;
- boolean b, old = false;
- while (!BinaryStdIn.isEmpty()) {
- b = BinaryStdIn.readBoolean();
- if (b != old) {
- BinaryStdOut.write(cnt);
- cnt = 0;
- old = !old;
- } else {
- if (cnt == 255) {
- BinaryStdOut.write(cnt);
- cnt = 0;
- BinaryStdOut.write(cnt);
- }
- }
- cnt++;
- }
- BinaryStdOut.write(cnt);
- BinaryStdOut.close();
- }
算法会逐个读取比特位, 如果它和上一个比特相同, 就把游程计数器 cnt 加 1; 如果计数器已满, 就将其输出为编码, 然后计数器归零, 并输出一个长度为 0 的游程来分割过长的相同编码; 如果它和上一个比特不同, 就将计数器的值输出然后归零.
展开的代码为:
- public static void expand() {
- boolean b = false;
- while (!BinaryStdIn.isEmpty()) {
- char cnt = BinaryStdIn.readChar();
- for (int i = 0; i <cnt; i++)
- BinaryStdOut.write(b);
- b = !b;
- }
- BinaryStdOut.close();
- }
展开时每次读取一个游程的长度 (8 位编码), 先输出比特 0, 按照游程指定的长度输出完毕后, 切换状态, 继续输出.
游程编码被广泛用于位图的压缩, 这种压缩方式还有一项特殊的优势在于, 随着位图分辨率的提高, 它的效果也会大大提高. 如果位图分辨率增加一倍, 它的总比特数将变为原来的 4 倍, 但游程的数量只会变为原来的 2 倍, 因为横向的比特数增加不会影响游程的数量, 只会影响游程的长度, 这样压缩后的比特数量变为约原来的 2 倍, 所以压缩率减半.
但游程编码只在游程较长时效果较好, 如果游程很短, 这种算法可能反而会增加比特数.
霍夫曼压缩
前缀码和单词查找树
虽然游程编码在许多场景非常有效, 但有的时候需要压缩的数据特征并不具有较长的游程, 比如英文文档等自然语言文件, 霍夫曼压缩算法和 LZW 压缩算法对这种特征的数据也能取得很好的效果.
霍夫曼压缩的主要思想是, 放弃文本文件的普通保存方式, 不再使用 7 位或 8 位二进制数表示一个字符, 而是用较少的比特表示出现频率高的字符, 用较多的比特表示出现频率低的字符.
比如对于字符串 A B R A C A D A B R A, 如果使用 7 位的 ASCII 字符编码, 那么只出现了 1 次的 D 和出现了 5 次的 A, 占用的比特数是一样的.
如果能这样编码
- A:0
- B:1
- R:00
- C:01
- D:10
那么这个字符串的编码就是 0 1 00 0 01 0 10 0 1 00 0. 只需要 15 位, 而 ASCII 码需要 77 位. 但这种方法并不完整, 因为它需要空格来区分字符, 如果没有空格, 就会造成歧义, 比如 01, 除了可以解码为 AB, 还可以解码为 C.
如果能够让所有字符编码都不会成为其他字符编码的前缀, 就不需要专门的分隔符了. 含有这种性质的编码规则叫做前缀码.
前缀码的一种简便表示方法就是单词查找树.
如图所示的单词查找树, 就是一种字符的编码方式, 它的左链接表示 0, 右链接表示 1, 每个字符的编码就是从根结点到该结点的路径表示的比特字符串.
不同的单词查找树表示的前缀码的压缩率不相同, 霍夫曼压缩算法构造的单词查找树是最优的.
霍夫曼压缩分为 5 个步骤:
压缩时:
构造前缀码的单词查找树
将树以字节流的形式输出
使用构造的树将字节流编码为比特流
展开时:
读取单词查找树
使用该树将比特流解码
构造前缀码的单词查找树
单词查找树的结点
- public static class Node implements Comparable<Node> {
- private char ch;
- private int freq;
- private final Node left, right;
- Node(char ch, int freq, Node left, Node right) {
- this.ch = ch;
- this.freq = freq;
- this.left = left;
- this.right = right;
- }
- public boolean isLeaf() {
- return left == null && right == null;
- }
- public int compareTo(Node that) {
- return this.freq - that.freq;
- }
- }
这份树结点的实现中, 除了用于表示左右结点的 left,right 和表示叶子节点中字符的 ch, 还增加了一个整型变量 freq, 用于统计字符出现的频率.
构造单词查找树
霍夫曼算法是一个两轮算法, 为了构造单词查找树, 算法会先读取一次整个输入流, 得到每个字符的频率.
构造的第一步是创建一片由许多只有一个结点的树所组成的森林, 每棵树都表示输入流中的一个字符. 然后自底向上根据频率构造单词查找树, 找到两个频率最小的结点, 创建一个包含着两个子结点的新结点, 新结点的频率值为两个子结点的频率值之和, 不断重复这个过程, 直到所有子树都合并为一颗树.
- private static Node buildTrie(int[] freq) {
- MinPQ<Node> pq = new MinPQ<Node>();
- for (char c = 0; c <R; c++)
- if (freq[c]> 0)
- pq.insert(new Node(c, freq[c], null, null));
- while (pq.size()> 1) {
- Node x = pq.delMin();
- Node y = pq.delMin();
- Node parent = new Node('\0', x.freq + y.freq, x, y);
- pq.insert(parent);
- }
- return pq.delMin();
- }
用最小优先队列可以方便快速的找到最小结点.
写入和读取单词查找树
写入
霍夫曼压缩算法需要在压缩时将树写入比特流并在展开时读取它. 写入时, 对单词查找树进行前序遍历, 遇到内部结点时, 写入比特 0, 遇到叶子结点时, 写入比特 1, 紧接着是这个结点中字符的 8 为 ASCII 码.
- private static void writeTrie(Node x) {
- if (x.isLeaf()) {
- BinaryStdOut.write(true);
- BinaryStdOut.write(x.ch);
- return;
- }
- BinaryStdOut.write(false);
- writeTrie(x.left);
- writeTrie(x.right);
- }
读取
在读取比特字符串, 重新构造单词查找树时, 首先读取一个比特以确定当前结点的类型, 如果是叶子结点, 就读取字符并创建一个叶子节点, 如果是内部结点, 就创建一个内部结点并递归地构造它的左右子树.
- private static Node readTrie() {
- if (BinaryStdIn.readBoolean())
- return new Node(BinaryStdIn.readChar(), 0, null, null);
- return new Node('\0', 0, readTrie(), readTrie());
- }
使用前缀码压缩
在压缩时, 首先根据单词查找树定义的前缀码来构造编译表. 为了提升效率, 使用由字符索引的数组 st,st 的大小为字符集的大小. st 中保存了单词查找树中包含的字符对应的比特字符串.
在构造编译表时, 会递归遍历整颗树, 并为每个结点维护了一条从跟结点到它的路径所对应的二进制字符串, 0 表示左链接, 1 表示右链接, 每当到达一个叶子节点时, 就将结点的编码设为它对应的比特字符串.
- private static void buildCode(String[] st, Node x, String s) {
- if (x.isLeaf()) {
- st[x.ch] = s;
- return;
- }
- buildCode(st, x.left, s + '0');
- buildCode(st, x.right, s + '1');
- }
编译表建立后, 压缩的过程, 就成了查找树如字符所对应的编码并写入的过程.
- public static void compress() {
- String s = BinaryStdIn.readString();
- char[] input = s.toCharArray();
- int[] freq = new int[R];
- for (int i = 0; i <input.length; i++)
- freq[input[i]]++;
- Node root = buildTrie(freq);
- String[] st = new String[R];
- buildCode(st, root, "");
- writeTrie(root);
- BinaryStdOut.write(input.length);
- for (int i = 0; i < input.length; i++) {
- String code = st[input[i]];
- for (int j = 0; j < code.length(); j++)
- if (code.charAt(j) == '1')
- BinaryStdOut.write(true);
- else
- BinaryStdOut.write(false);
- }
- BinaryStdOut.close();
- }
使用前缀码展开
在展开时, 首先使用前述方法从比特流中还原单词查找树. 然后根据比特流的输入从跟结点开始向下移动, 如果比特为 0, 就移动到左子结点, 反之就移动到右子结点. 当遇到叶子结点时, 输出这个结点的字符并重新回到根结点.
- public static void expand() {
- Node root = readTrie();
- int N = BinaryStdIn.readInt();
- for (int i = 0; i < N; i++) {
- Node x = root;
- while (!x.isLeaf())
- if (BinaryStdIn.readBoolean())
- x = x.right;
- else
- x = x.left;
- BinaryStdOut.write(x.ch);
- }
- BinaryStdOut.close();
- }
LZW 压缩
LZW 算法的基本思想和霍夫曼压缩的思想正好相反. 霍夫曼压缩是为输入中的定长模式产生了变长的编码编译表; 而 LZW 压缩是为输入中的变长模式生成了一张定长的编码编译表. 而且, LZW 算法不需要在输出中附上这张编译表.
LZW 压缩算法的基础是维护一张字符串键和编码的编译表. 在符号表中, 将 128 个 ASCII 码的值初始化为 8 位编码, 即在每个字符的编码值前面添加 0. 然后用 16 进制数字来表示编码, 那么 A 的编码就是 41,R 的是 52 等等. 将 80 编码保留为文件借宿的标志, 并将 81-FF 的编码值分配给在输入中遇到的各种子字符串.
压缩数据时, 会反复进行如下操作:
找出未处理的输入在符号表中最长的前缀字符串 s;
输出 s 的 8 位编码值;
继续扫描 s 之后的一个字符 c;
在符号表中将 s+c(连接 s 和 c) 的值设为下一个编码值.
比如下图所示为处理输入 A B R A C ... B R A 的过程, 以及对应的三向单词查找树:
对于前 7 个字符, 匹配的最长前缀只有 1 个字符, 因此输出这些字符对应的编码, 并将编码 81 到 87 和产生的 7 个双字符的字符串关联. 然后发现 AB 匹配了输入的前最 81, 并将 ABR 添加到符号表中, 然后是 RA(输出 83 并添加 RAB),BR(输出 82 并添加 BRA) 和 ABR(输出 88 并添加 ABRA), 最后只剩下 A(输出 41).
LZW 的单词查找树
LZW 算法会用到三向单词查找树, 包含两种操作:
找到输入和符号表的所有键的最长前缀匹配;
将匹配的键和前瞻字符相连得到一个新键, 将新键和下一个编码管理并添加到符号表中.
LZW 压缩的展开
在展开时, 会维护一张关联字符串和编码值的符号表, 这张表的逆表示压缩时所用的符号表. 在这张表总加入 00 到 7F 和所有单个 ASCII 字符的字符串的关联条目, 将第一个未关联的编码值设为 81. 在遇到编码 80 前, 不断重复以下操作:
输出当前字符串 val;
从输入中读取一个编码 x;
在符号表中将 s 设为和 x 相关联的值;
在符号表中将下一个未分配的编码值设为 val+c, 其中 c 为 s 的首字母;
将当前字符串 val 设为 s;
最终 LZW 算法的实现如下, 这份用于实际使用的代码, 采用的编码宽度为 12 位.
- public class LZW {
- private static final int R = 256;
- private static final int L = 4096;
- private static final int W = 12;
- public static void compress() {
- String input = BinaryStdIn.readString();
- TST<Integer> st = new TST<Integer>();
- for (int i = 0; i <R; i++)
- st.put("" + (char) i, i);
- int code = R + 1;
- while (input.length()> 0) {
- String s = st.longestPrefixOf(input);
- BinaryStdOut.write(st.get(s), W);
- int t = s.length();
- if (t < input.length() && code < L)
- st.put(input.substring(0, t + 1), code++);
- input = input.substring(t);
- }
- BinaryStdOut.write(R, W);
- BinaryStdOut.close();
- }
- public static void expand() {
- String[] st = new String[L];
- int i;
- for (i = 0; i < R; i++)
- st[i] = "" + (char) i;
- st[i++] = " ";
- int codeword = BinaryStdIn.readInt(W);
- String val = st[codeword];
- while (true) {
- BinaryStdOut.write(val);
- codeword = BinaryStdIn.readInt(W);
- if (codeword == R)
- break;
- String s = st[codeword];
- if (i == codeword)
- s = val + val.charAt(0);
- if (i < L)
- st[i++] = val + s.charAt(0);
- val = s;
- }
- BinaryStdOut.close();
- }
- }
来源: http://www.bubuko.com/infodetail-3394735.html