Question

浓缩资料

如何简明扼要的记载资料、传述讯息呢？

缩短资料长度，减少交流时间，减少储存空间，好处多多。

Compress / Decompress

“压缩”是浓缩资料，“解压缩”是回复资料。观念类似先前提及的“编码”与“解码”。

compress
Thank you! -------------> 3Q!
           <------------- decompress="" compress="" 200000000 美金="" -------------=""> 两亿镁
              <------------- decompress="" <="" pre="">

文字、声音、图像、动作、感受，通通可以压缩。

资料先压缩、再解压缩，如果还是跟原本资料一模一样，就叫做“无失真压缩 lossless compression”；如果不一样就叫做“失真压缩 lossy compression”。

用电脑处理资料，首重精准无误。以下仅介绍无失真压缩。

二元码压缩

二元码（二进位字串）缩短成另一个二元码。

compress   
001100111100101010100001   ------------->   10110101
                           <------------- decompress="" <="" pre="">

文字压缩

例如 Doctor 缩写成 Dr.、公共汽车简称为公车。

vs.      versus
lol      laugh out loudly
RTFM     read the fucking manual
afaik    as far as I known
¥        Japanese Yen

文字压缩得视作二元码压缩！文字储存于电脑当中，本质上就是 ASCII 或 UTF-8 二元码。

语言压缩

长话短说的压缩，一般认为是文学的范畴。

原文　　　　　　　｜压缩　　　　　｜失真压缩｜言简意赅
如果你没勇气陪我到｜若你畏惧陪我到｜不爱我　｜再见
明天的明天的明天　｜大后天　　　　｜　　　　｜
倒不如就忘了就断了｜不如忘尽　　　｜就忘了我｜
寂寞的昨天的昨天　｜寂寞的前天　　｜　　　　｜

资讯压缩

古代人将压缩和编码视为相同，一般认为是文字学的范畴。

资讯压缩是把抽象的资讯信息变成实际的码。设立一种编码方式，让码的长度越短越好，以三言两语诠释大千世界。

打个比方，白话文是不太理想的压缩、文言文是更理想的压缩；北京话是不太理想的压缩、山东话是更理想的压缩。

北京话　　　　　　｜台湾话　　　　｜闽南话　　　｜四川话　　｜山东话
甲：是谁在楼下啊？｜甲：谁在下面？｜甲：啥咪郎？｜甲：喇国？｜甲：谁？
乙：是我在这儿呗！｜乙：我在这裡！｜乙：喜哇啦！｜乙：使握！｜乙：俺！
甲：你在做什麽咧？｜甲：你在干嘛？｜甲：衝啥悔？｜甲：昨傻？｜甲：啥？
乙：我在这小便呐！｜乙：我在小便！｜乙：棒溜啦！｜乙：潦瞭！｜乙：尿！

除了文字可以当作码，图示、手语、表情也都可以当作码。

Symbol / Code

资料通常很长。大家习惯逐段处理，符合电脑运作特性。

一段资料构成一个“符号”，再进一步变成简短的“码”。常见段落设定成符号，相同的符号对应相同的码，有利于辨认。

制定符号：尚无最佳演算法，仍有研究空间。经典演算法是 Lempel-Ziv Compression。

制定码：已有最佳演算法，让码的总长度达到最小值！经典演算法是 Arithmetic Compression、Huffman Compression。

两者相互配合，产生了各式各样的演算法： DEFLATE 、 gzip 、 bzip2 、 zopfli 、 brotli 。有兴趣的读者请自行学习。

编码与压缩的差别：编码时，符码是公定的，符号长度是一个字元，码长度是整数个 byte；压缩时，符码是自订的，长度不定。

【注：因为逐段处理，所以没有活用到文字先后顺序。】

何谓好的压缩？

预先计算符码，才能顺利压缩。符码资讯，必须连同压缩结果一併储存，才能顺利解压缩。

所谓好的压缩，就是让“压缩后长度”加“符码资讯长度”少于“压缩前长度”。

顺带一提，由于必须额外储存符码资讯，即便使用世上最好的压缩演算法，档案也可能越压越大！比方说，已经压缩过的资料再压缩一遍，很容易产生这种情形。

Dictionary Compression

Dictionary Compression

用于制定符号。

常见单字、常见字根，当作符号。其馀部分则是一种字元当作一种符号。宛如查字典，通常以 Trie 作为字典的资料结构。时间複杂度 O(N)。

text   | symbol
------ | ------
the    |   0
that   |   1
ing    |   2
is     |   3
ness   |   4
ion    |   5
less   |   6
ed     |   7
a      |   8
b      |   9
c      |   10
:      :   :

text       | symbol       int main() {
---------- | ------           int n = 1 + 1;
int        |   i              return 0;
main()     |   m          }
{          |   {                 ↓
           |   s          ims{
           |   t          tine1p1;
 +         |   p          tr
 =         |   a          }
return 0;  |   r                ↓
}          |   }          ims{⤶tine1p1;⤶tr⤶}
⤶          |   ⤶          
:          :   :

Antidictionary Compression

http://www.stringology.org/DataCompression/dca/index_en.html

Lempel-Ziv Compression

Lempel-Ziv Compression

用于制定符号。有多种变形，共同精神是：

依序读取字元。遇到生字，就加入字典，然后从零开始加长单字；遇到熟字，就继续加长单字。

这个演算法基本上没有什麽道理，但是效果却不错。也许裡面有什麽神奇的数学性质，不过我不清楚。

LZ77 / LZ78 / LZW

http://my.stust.edu.tw/sys/read_attach.php?id=58496

LZMA

http://en.wikipedia.org/wiki/LZMA

LZO

http://en.wikipedia.org/wiki/Lempel–Ziv–Oberhumer

Run-length Compression

Run-length Compression

用于制定符号。

aaaabbcabcbbbaaaa ---> a4b2c1a1b1c1b3a4

连续重複符号，精简成两个符号。时间複杂度 O(N)。

先实施“ Burrows-Wheeler Transform ”让相同符号尽量靠在一起，再实施 Run-length Compression，可以提升压缩效果。

UVa 11541 12547 ICPC 3867

Arithmetic Compression（Under Construction!）

Arithmetic Compression（Range Coding）

用于制定码。

Compress

预先统计符号出现次数，才能顺利地压缩。

依序读取符号，不断切割区间，最后得到一个分数。分数换成二进位表示法，小数部分就是码。

区间宽度设定为 1。浮点数运算，遭遇精确度问题。

区间宽度设定为大数。大数运算，遭遇效率问题，况且我们无法预测数字需要多大。

区间宽度设定成整数。整数运算，没有问题。概念上是从大数取一小段高位数来计算。除不尽就算了，不补零不再除。当位数几乎用罄、无法分辨符号，才替换下一段高位数。

因为计算过程不够精准，所以压缩效果稍微差了一点，不过无伤大雅。时间複杂度 O(N)。

Decompress

码和符号出现次数必须一併储存，才能顺利地解压缩。

依序读码，判断位于哪个区间。时间複杂度 O(N)。

符号长度固定为一个字元的版本。

不输出二元码、而是输出可见符号的版本。

Adaptive Arithmetic Compression

Adaptive Arithmetic Compression

adaptive 是随时视情况调整。dynamic 是随时改变过去输入资料。online 是随时处理当前输入资料。不要混淆囉。

压缩、解压缩的过程当中，不预先计算符号数量，而是即时更新符号数量。因此压缩效果不如原始的 Arithmetic Compression 来得好。使用“ Sequence ”资料结构，时间複杂度 O(NlogN)。

External Memory Algorithm。适合 I/O 速度很慢、资料量很大的情况。例如网路传输，一边等待下载、一边解压缩，争取时效。

Huffman Compression

Huffman Compression

用于制定码。

Code Table

符号与码的对应表，称作“码表”。

symbol  | code  | code length
------- | ----- | -----------
a       | 011   | 3
b       | 0011  | 4
c       | 11111 | 5

考虑 abbacacc
a 出现 3 次、b 出现 2 次、c 出现 3 次
压缩后长度：3*3 + 4*2 + 5*3 = 9 + 8 + 15 = 32
码表长度：3 + 4 + 5 = 12

替每种符号制定独一无二的码，码长皆是整数，资料压缩后可以明确区分符码。

先前码长是分数，此处码长是整数。关係宛如 Fractional Knapsack Problem 和 0/1 Knapsack Problem。因此压缩效果不如 Arithmetic Compression 来得好。

现在要让“压缩后长度”与“码表长度”都尽量短。

Code Tree

码表的所有码，存入 Trie 资料结构，得到“码树”。

二元码的情况下，码树是二元树：左树枝是 0、右树枝是 1。符号位于节点上；从树根往符号的路线是其二元码。

在二元树上面安排各个符号的位置，就能产生一组二元码，并且保证每个码都相异。

一个码千万不能是另一个码的开头，以免解压缩产生歧义。放到 Code Tree 上面来看就是：一个节点千万不能是另一个节点的祖先。想解决这个问题，只要让符号全部集中于树叶！

Code Tree 的树叶深度总和，就是“码表长度”。

码长即树叶深度。减少码长即减少树叶深度。码长不断减少，符号不断挪往树根，又要避免成为其他符号的祖先，最后符号都在树叶，Code Tree 形成满二元树。

调整满二元树的形状，可以改变码表长度。Code Tree 长得越像完美二元树，码表长度就越短。

满二元树（full binary tree）：
每个节点只有零个或两个小孩的二元树。

完美二元树（perfect binary tree）：
每片树叶深度都一致的二元树。亦是满二元树。

UVa 283 644

Code Tree 的权重，刻意定义为“压缩后长度”。

符号出现次数填入树叶，做为权重。树叶深度乘上权重，然后加总，定义为 Code Tree 的权重。

计算 Code Tree 的权重（Incremental Method）

深度相同的树叶，可以一併累计权重，再一併乘上深度。逐层累计权重，就得到整棵树的权重。

计算 Code Tree 的权重（Recursive Method）

满二元树每个内部节点都有两个小孩。满二元树的最深的树叶，一定有两片树叶互为兄弟。

删除最深、互为兄弟的两片树叶，递迴缩小问题。两片树叶权重相加，作为新树叶的权重，进一步得到递迴公式：

递迴式：
原树权重 = 新树权重 + 左树叶权重 + 右树叶权重

化作一般式：
原树权重 = 第一次删除的左树叶权重 + 第一次删除的右树叶权重 +
　　　　   第二次删除的左树叶权重 + 第二次删除的右树叶权重 +
　　　　　　　　　　　　　　　　　⋮
　　　　   第 N-1 次删除的左树叶权重 + 第 N-1 次删除的右树叶权重

Optimal Code Tree：降低压缩后长度

Code Tree 是哪一种形状，权重才会最小呢？

根据方才的公式，Code Tree 的权重取决于每次删除的那两片树叶。每次删除的那两片树叶权重越小，Code Tree 权重就越小。

换句话说，优先聚合权重最小的两个节点，最小的相加之后还是最小的，如此递推下去，Code Tree 权重就达到最小值，得到 Optimal Code Tree。

以 Priority Queue 存放节点，就能迅速找出权重最小的两个节点。总共 2N-1 个 push，2N-2 个 pop，时间複杂度 O(NlogN)。N 是一开始的树叶数目，也就是符号数目。

Adaptive Huffman Compression

Adaptive Huffman Compression

不预先建立 Optimal Code Tree。即时调整 Code Tree 的形状，维持是 Optimal Code Tree。

读入一个符号，符号出现次数加一，Optimal Code Tree 对应的树叶权重加一，该树叶的祖先们权重也都要跟著加一。

当有需要重新调整 Optimal Code Tree 的形状，也就是指其中有一个节点权重加一之后，权重刚好超越了另一个节点的权重（换句话说，这些节点本来权重相同），导致另一个节点必须先聚合，权重加一的节点必须晚一点才能聚合，改变了 Optimal Code Tree 的形状。

Code Tree 排序所有树叶

深度相同的树叶互相对调，Code Tree 权重不变。

权重小、位置浅的树叶，权重大、位置深的树叶，两者对调，可让 Code Tree 权重变小。

换句话说，权重小的树叶儘量挪往深处，权重大的树叶儘量挪往浅处，可让 Code Tree 权重变小。

进一步来说，所有树叶依照权重由小到大排序之后，依序由深到浅安排位置、同一层则随意安排位置（或者是刻意由左到右安排位置），可让 Code Tree 权重达到区域极小值。

Optimal Code Tree 排序所有节点

Optimal Code Tree 则是全部节点都能如此排序。建立 Optimal Code Tree 时，每次都是聚合权重最小的两个节点，因而造就了排序的性质。

节点依照权重排序之后，就很容易搜寻了，能够快速找到权重相同的节点们。

调整 Optimal Code Tree

http://www.stringology.org/DataCompression/fgk/index_en.html

http://www.stringology.org/DataCompression/ahv/index_en.html

节点权重要加一之前，就先与权重相同的节点交换位置，尽量换到最上层、最右端的位置，也就是尽量换到最靠近次大权重值的位置；这个交换不会影响 Optimal Code Tree 的权重、仍是 Optimal Code Tree。如此一来，权重加一之后，不需要改变 Code Tree 的形状，仍是 Optimal Code Tree；而且所有节点依然是排序好的。

别忘记该树叶的祖先们，权重也都要加一。採用递增法，一步一步处理：树叶权重加一之后，再处理父亲权重加一的问题。

我不清楚如何得到码表长度最短的 Optimal Code Tree。

Hu-Tucker Compression

Alphabetic Code Tree

符号必须由小到大、从左往右排列。

特色是：符号的大小顺序，就是码的大小顺序。符号比大小，就是码比大小──可以直接使用压缩之后的资料比大小。

有一好就有一坏，压缩效果比起 Huffman Compression 就逊色了一点。

Alphabetic Code Tree 的权重

与 Code Tree 的权重定义相同。

计算 Code Tree 的权重（更玄的 Recursive Method）

先前计算 Code Tree 的权重，是删除深度相同、互为兄弟的两片树叶；关注节点之间的高度关係、父子关係。

其实还有另外一种计算方式，是改为删除深度相同、但是不一定要互为兄弟的两片树叶；改为关注高度关係、无视父子关係。最后得到类似的递迴公式：

递迴式：
原节点集合 = 新节点集合 + 一片树叶权重 + 另一片树叶权重

化作一般式：
原树权重 = 第一次删除的树叶权重 + 第一次删除的另一片树叶权重 +
　　　　   第二次删除的树叶权重 + 第二次删除的另一片树叶权重 +
　　　　　　　　　　　　　　　　　⋮
　　　　   第 N-1 次删除的树叶权重 + 第 N-1 次删除的另一片树叶权重

Optimal Alphabetic Code Tree

http://www.cs.rit.edu/~std3246/thesis/node10.html

http://cseweb.ucsd.edu/classes/wi06/cse202/notes-feb09.pdf

优先聚合权重最小的两个节点，Alphabetic Code Tree 的权重就会达到最小值，就和 Optimal Code Tree 一样。

但是 Alphabetic Code Tree 限定了树叶的左右顺序，所以每次聚合的两个节点，如果刚好都是树叶的话，就只能是相邻的树叶──如此才能维持符号的左右顺序。

只有树叶必须担心符号顺序问题；树叶一旦经过聚合之后，就不必再担心顺序问题，也不再隔开其他树叶。

一、统计各个符号的出现次数。
二、一开始有 N 个树叶（节点），权重设定成符号出现次数。
　　现在以 bottom-up 方式建立 Optimal Alphabetic Code Tree：
　甲、两个权重最小的节点（不能是被隔离的两片树叶），相加得到新节点的权重。
　　　此时确立了这两个节点的深度相同（不见得互为兄弟），
　　　同时确立了新节点深度比它们浅一层（不见得是它们的父亲）。
　乙、聚合 N-1 次就得到树根了，不过只能确立所有节点的高度关係。
　　　得到 Optimal Alphabetic Code Tree 的权重。
　丙、以 top-down 方式，按照高度关係，确立所有节点的父子关係。
　　　即形成 Optimal Alphabetic Code Tree。

时间複杂度为 O(NlogN)。不过实作比较複杂。

【待补程式码】

相似的树

这三棵树非常相似，都是“深度”乘上“符号出现次数”，令总和最小。

Optimal Binary Search Tree
所有节点都有符号出现次数，节点的位置必须按照大小排列顺序。O(N^2)。

Optimal Alphabetic Binary Code Tree
只有树叶拥有符号出现次数，树叶的位置必须按照大小排列顺序。O(NlogN)。

Optimal Binary Code Tree
只有树叶拥有符号出现次数，树叶的位置顺序随意。O(NlogN)。

实务上，符号种类数目通常很少，亦可运用 OBST 的 O(N^2) 演算法，求得 OABT；程式码结构简单，执行时间也比较短。

UVa 12057 PKU 1738

延伸阅读：Garcia-Wachs Algorithm

http://www.math.tau.ac.il/~haimk/seminar00/dana-MCBT.ppt

演算法简单很多，但是证明也複杂很多。