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

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

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