07. 文字壓縮

因為電腦可以儲存的資訊空間是有限的，所以要盡可能用有效率的方法來呈現資訊，這個概念就叫做「壓縮」。

藉由對資料做編碼，然後要取出資料時再解碼的方式，電腦可以儲存更多資料，或是更快地在網路傳遞資料。

文字壓縮概念的練習

http://bk.chjh.hc.edu.tw/html5/html5_text_compression/text_compression.html

1. 找到重覆出現的單字，在其中選取一個單字(或是一整個句子)，稱為保留標的。

2. 再選取其他重覆出現的單字(或是一整個句子)，稱為壓縮標的。

3. 選取完成之後，按下「開始壓縮」按鈕，將所有重覆的單字(或句子)清除到只剩一個，被壓縮的標的則用數字標示其所在的位置。

4. 一直進行到無法再找到保留或壓縮標的為止，看看總共用了幾個壓縮的步驟、成功壓縮了幾個字元。

問題一、為什麼選取標的時，要被限制在至少選取兩個字元以上？

問題二、尋找壓縮標的時，如果漏掉了其中幾個，對於結果有什麼影響？

問題三、要優先標記一整個句子，還是以較短的單字為優先？

【結論】

電腦的儲存容量正以令人難以置信的速度增長。在過去25年裡，傳統電腦的儲存量已經至少增長了數百萬倍。雖然如此，我們打算存入電腦中的東西也跟著增加很多很多。只要空間足夠，電腦可以儲存整本書，甚至一整個圖書館的資料，當然現在的電腦儲存許多音樂與電影再就不是問題了。

大量的資料在網路網路上是個大問題，因為資料越大就需要更長的時間才能完成下載的動作。此外，我們一直在嘗試將電腦越做越小(像是手機、手錶與許多的穿戴裝置)，但是我們卻希望在上面儲存越多的資訊。

要解決儲存空間或傳輸大量資料的問題，除了買更多如硬碟、快閃磁碟之類的儲存空間，或是加快網路的傳輸速度之外，還有一個解決這個問題的方法，就是我們可以透過壓縮使得資料佔用的空間變少。壓縮和解壓縮的這個過程通常會交給電腦自動完成。我們會注意到的可能只有磁碟因此增加了更多的儲存空間，或是網頁的顯示速度因此變快了。

近年來，有許多壓縮的方法被發明了。在以上的活動中，我們操作的概念是用一個指標指向前面出現過的區塊的做法，被稱為LZ編碼(Ziv-Lempel Coding，或LZ Coding)。這個方法可以方便地用於任何語言，並可以輕易地減少一半的資料量。它有時被稱為在個人電腦上的「拉鍊」(zip)，並且也用在GIF和PNG這兩個圖檔格式。此外，也被用於高速的數據機。數據機利用壓縮減少透過電話線傳送的資料量，所以速度就快得多了。

【作業】

老師將會發下一張全部都是英文字母的文章(開始頭暈了嗎？)，這篇文章透過電腦程式來運算之後，其中至少有1633個字母可以被「壓縮」。

記得，被標記保留或壓縮的標的一定要至少超過兩個字母。請努力嘗試，看看你能壓縮掉幾個字母！

Once upon a time, long, long ago, three little pigs set out to make their fortunes. The first little pig wasn't very clever, and decided to build his house out of straw, because it was cheap. The second little pig wasn't very clever either, and decided to build his house out of sticks, for the "natural" look that was so very much in fashion, even in those days. The third little pig was much smarter than his two brothers, and bought a load of bricks in a nearby town, with which to construct a sturdy but comfortable country home.

Not long after hist housewarming party, the first little pig was curled up in a chair reading a book, when there came a knock at the door. It was the big bad wolf, naturally.

"Little pig, little pig, let me come in!" cried the wolf.

"Not by the hair on my chinny-chin-chin!" squealed the first little pig.

"Then I'll huff, and I'll puff, and I'll blow your house down!" roared the wolf, and he did huff, and he did puff, and the house soon collapsed. The first little pig ran as fast as he could to the house of sticks, and was soon safe inside. But it wasn't long before the wolf came calling again.

"Little pig, little pig, let me come in!" cried the wolf.

"Not by the hair on my chinny-chin-chin!" squealed the second little pig.

"Then I'll huff, and I'll puff, and I'll blow your house down!" roared the wolf, and he did huff, and he did puff, and the house was soon so much firewood. The two terrified little pigs ran all the way to their brother's brick house, but the wolf was hot on their heels, and soon he was on the doorstep.

"Little pig, little pig, let me come in!" cried the wolf.

"Not by the hair on my chinny-chin-chin!" squealed the third little pig.

"Then I'll huff, and I'll puff, and I'll blow your house down!" roared the wolf, and he huffed, and he puffed, and he huffed som more, but of course, the house was built of brick, and the wolf was soon out of breath. Then he had an idea. The chimney! He clambered up a handy oak tree onto the roof, only to find that there was no chimney, because the third little pig, being conscious of the environment, had installed electric heating. In his frestration, the wolf slipped and fell off the roof, breaking his left leg, and severely injuring his pride. As he limped away, the pigs laughed, and remarked how much more sensible it was to live in the city, where the only wolves were in the zoo. And so that is what they did, and of course they all lived happily ever after.