HackerRank | 2021全台活動資訊網

2020年2月3日—簡單來說就是題目會給定一個字串s，與一個HuffmanTree，我們需要依照給予...這邊先解釋，codeword這邊是指編碼過後呈現的字元。

解個題順便複習 Huffman Tree。

題目描述較長，可以直接到Hacker Rank[1]上看題目說明。

簡單來說就是題目會給定一個字串 s，與一個 Huffman Tree，我們需要依照給予的 Huffman tree內容將字串 s 還原為原本內容。

題目不困難，只是如果在解題前可以充分瞭解Huffman code與 Huffman tree的概念，解起來會輕鬆許多。

這邊做一個簡單的介紹，Huffman code是無失真的資料壓縮演算法，透過『字元出現的頻率』來決定每個字元轉為二元字串時表達方式，意思即依據每個字元出現的頻率，出現次數愈多的字編碼後長度較短，出現頻率愈低的字編碼後長度愈長。

這邊先解釋，codeword 這邊是指編碼過後呈現的字元。

舉例來說，以下列的表來看：

可以看見每個字元出現的頻率，a 出現 45k 次；b出現 13k次，依此類推。

如果現在不以壓縮方式傳輸，每個字都固定以 3 bits (Fixed-length codeword) 來表示，則總共需要

如果改以前面提到的方式壓縮來處理(Variable-length codeword)，則總共需要

比較兩者，同樣的內容，使用 Variable-length codeword 會比 Fixed-length codeword 節省幾乎 25 %的空間，而 Huffman code就是這樣的概念，出現次數愈多，則編碼後二進制字元欲短，反之欲長，

原文定義是：

No codeword is also a prefix of some other codeword, such code are called orefi...