数据压缩算法——无损压缩

空间复杂度是指算法在计算机内执行时所需存储空间的度量，如果想要降低算法的空间复杂度，则必须要压缩它所需的存储空间。

在算法执行期间所需要的存储空间中：输入的初始数据所占的存储空间一般来说是最大的（大数据背景下），也是最值得做数据压缩的。

·数据压缩其实就是对数据进行编码的过程，它能够减少存储空间和网络传输时间。

无损压缩：简单的说就是压缩过程中重复数据会被删除，解压的时候会被再添加进来。无损压缩不能忍受任何数据丢失，多数用于法律或医学类文档、计算机程序等重要类文档;

常见的无损压缩方法有RunLengthEncoding、Lempel-Ziv-WelchEncoding（LZW）、HuffmanEncoding。

RunLengthEncoding:行程长度压缩法即根据字符串的连续重复字符进行编码的一种方法。算法原理极其简单（时间复杂度O（n）），对于连续重复的字符压缩效果很好。但是如果没有连续重复字符呢。。。。。。

例子:

Input：AAAAABBB，ABC

Ouput：A5B3，A1B1C1

HuffmanEncoding：霍夫曼编码使用变长编码表对字符进行编码，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，编码之后的字符串的平均长度和期望值都较低。

具体步骤：

1）将信源符号的概率按减小的顺序排队。

2）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率１。

3）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。

4）将每对组合的左边一个指定为0，右边一个指定为1（或相反）。

例子：

Input：BABACAC ADADABB CBABEBE DDABEEEBB

Output：1110111001010010 1001110011101111 010111011001100 01101110110000001111

霍夫曼编码的核心思想就是让出现次数多的元素被较短的编码代替，但是在源符号集的概率分布不是2负n次方的形式，则无法达到熵极限，并且译码复杂，使用时要具体问题具体分析。

关于LZW算法国内有很多论文做了研究，待我整理之后再做介绍。