空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量，如果想要降低算法的空間復(fù)雜度，則必須要壓縮它所需的存儲(chǔ)空間。

在算法執(zhí)行期間所需要的存儲(chǔ)空間中：輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間一般來(lái)說(shuō)是最大的（大數(shù)據(jù)背景下），也是最值得做數(shù)據(jù)壓縮的。

·數(shù)據(jù)壓縮其實(shí)就是對(duì)數(shù)據(jù)進(jìn)行編碼的過(guò)程，它能夠減少存儲(chǔ)空間和網(wǎng)絡(luò)傳輸時(shí)間。

無(wú)損壓縮：簡(jiǎn)單的說(shuō)就是壓縮過(guò)程中重復(fù)數(shù)據(jù)會(huì)被刪除，解壓的時(shí)候會(huì)被再添加進(jìn)來(lái)。無(wú)損壓縮不能忍受任何數(shù)據(jù)丟失，多數(shù)用于法律或醫(yī)學(xué)類文檔、計(jì)算機(jī)程序等重要類文檔;

常見的無(wú)損壓縮方法有RunLengthEncoding、Lempel-Ziv-WelchEncoding（LZW）、HuffmanEncoding。

RunLengthEncoding:行程長(zhǎng)度壓縮法即根據(jù)字符串的連續(xù)重復(fù)字符進(jìn)行編碼的一種方法。算法原理極其簡(jiǎn)單（時(shí)間復(fù)雜度O（n）），對(duì)于連續(xù)重復(fù)的字符壓縮效果很好。但是如果沒有連續(xù)重復(fù)字符呢。。。。。。

例子:

Input：AAAAABBB，ABC

Ouput：A5B3，A1B1C1

HuffmanEncoding：霍夫曼編碼使用變長(zhǎng)編碼表對(duì)字符進(jìn)行編碼，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編碼，編碼之后的字符串的平均長(zhǎng)度和期望值都較低。

具體步驟：

1）將信源符號(hào)的概率按減小的順序排隊(duì)。

2）把兩個(gè)最小的概率相加，并繼續(xù)這一步驟，始終將較高的概率分支放在右邊，直到最后變成概率１。

3）畫出由概率１處到每個(gè)信源符號(hào)的路徑，順序記下沿路徑的０和１，所得就是該符號(hào)的霍夫曼碼字。

4）將每對(duì)組合的左邊一個(gè)指定為0，右邊一個(gè)指定為1（或相反）。

例子：

Input：BABACAC ADADABB CBABEBE DDABEEEBB

Output：1110111001010010 1001110011101111 010111011001100 01101110110000001111

霍夫曼編碼的核心思想就是讓出現(xiàn)次數(shù)多的元素被較短的編碼代替，但是在源符號(hào)集的概率分布不是2負(fù)n次方的形式，則無(wú)法達(dá)到熵極限，并且譯碼復(fù)雜，使用時(shí)要具體問(wèn)題具體分析。

關(guān)于LZW算法國(guó)內(nèi)有很多論文做了研究，待我整理之后再做介紹。