無前序編碼的動態(tài)規(guī)劃解法.pdf

1、本文主要介紹構(gòu)造無前序編碼中混合度數(shù)編碼,保留長度編碼,以一結(jié)尾編碼這幾個問題的一種最優(yōu)結(jié)構(gòu)構(gòu)造算法。本文介紹的算法的運行時間比歷史上的最好結(jié)果提高了至少一個數(shù)量級的時間復(fù)雜度。
　　前綴碼是一種常見的壓縮編碼方案。它將通信中出現(xiàn)頻率較高的符號映射成較短的字符串,而頻率很低的符號在前綴碼中相應(yīng)的字符串較長。這種每個符號編碼后長度可能不同的編碼,若要保持解碼后對應(yīng)符號的唯一性,需要每個符號的編碼都不是其他符號編碼的前綴。廣為人知的霍

2、夫曼編碼是這類編碼的典型。
　　為了在實際生產(chǎn)生活中更好的運用霍夫曼編碼人們提出了混合度數(shù)編碼,保留長度編碼,以一結(jié)尾編碼等更具實際意味的霍夫曼編碼的變種。本文將逐一介紹其實際運用以及歷史上的最優(yōu)解法,最后提出一種非常類似,系統(tǒng)的方法,來以比歷史最優(yōu)算法快至少一個數(shù)量級的時間解決這些問題。
　　霍夫曼編碼的最優(yōu)結(jié)構(gòu)能用非常簡單明晰的貪婪法求得,但是本文介紹的幾種霍夫曼編碼的變種并不一定存在如此簡便的貪婪算法。我們會在本文中見