數據壓縮演算法研究

❶ 常用的數據壓縮演算法有哪些

基本的分為兩大類：有損和無損。
有損壓縮：主要是一些量化演算法，比如a率，u率，lloyds最優量化。
無損壓縮：主要是一些編碼演算法，比如子帶編碼，差分編碼，哈夫曼編碼等。
另外時頻變換雖然沒壓縮效果，但是是很好的壓縮工具，比如fft，dct等。
最後就是壓縮感知稀疏重建等。

❷ 多媒體數據壓縮算術研究 論文筆記

多媒體圖像壓縮技術
姓名:Vencent Lee
摘要：多媒體數據壓縮技術是現代網路發展的關鍵性技術之一。由於圖像和聲音信號中存在各種各樣的冗餘，為數據壓縮提供了可能。數據壓縮技術有無損壓和有損壓縮兩大類，這些壓縮技術又各有不同的標准。
一、多媒體數據壓縮技術
仙農(C．E．Shannon)在創立資訊理論時，提出把數據看作是信息和冗餘度的組合。早期的數據壓縮之所以成為資訊理論的一部分是因為它涉及冗餘度問題。而數據之所以能夠被壓縮是因為其中存在各種各樣的冗餘；其中有時間冗餘性、空間冗餘性、信息熵冗餘、先驗知識冗餘、其它冗餘等。時間冗餘是語音和序列圖像中常見的冗餘，運動圖像中前後兩幀間就存在很強的相關性，利用幀間運動補興就可以將圖像數據的速率大大壓縮。語音也是這樣。尤其是濁音段，在相當長的時間內(幾到幾十毫秒)語音信號都表現出很強的周期性，可以利用線性預測的方法得到較高的壓縮比。空間冗餘是用來表示圖像數據中存在的某種空間上的規則性，如大面積的均勻背景中就有很大的空間冗餘性。信息熵冗餘是指在信源的符號表示過程中由於未遵循資訊理論意義下最優編碼而造成的冗餘性，這種冗餘性可以通過熵編碼來進行壓縮，經常使用的如Huff-man編碼。先驗知識冗餘是指數據的理解與先驗知識有相當大的關系，如當收信方知道一個單詞的前幾個字母為administrato時，立刻就可以猜到最後一個字母為r，那麼在這種情況下，最後一個字母就不帶任何信息量了，這就是一種先驗知識冗餘。其它冗餘是指那些主觀無法感受到的信息等帶來的冗餘。
通常數據壓縮技術可分為無損壓縮(又叫冗餘壓縮)和有損壓縮(又叫熵壓縮)兩大類。無損壓縮就是把數據中的冗餘去掉或減少，但這些冗餘量是可以重新插入到數據中的，因而不會產生失真。該方法一般用於文本數據的壓縮，它可以保證完全地恢復原始數據；其缺點是壓縮比小(其壓縮比一般為2：1至5：1)。有損壓縮是對熵進行壓縮，因而存在一定程度的失真；它主要用於對聲音、圖像、動態視頻等數據進行壓縮，壓縮比較高(其壓縮比一般高達20：1以上。最新被稱為「E—igen—ID」的壓縮技術可將基因數據壓縮1．5億倍)。對於多媒體圖像採用的有損壓縮的標准有靜態圖像壓縮標准(JPEG標准，即『JointPhotographicExpertGroup』標准)和動態圖像壓縮標准(MPEG標准，即『MovingPictureExpertGroup』標准)。
JPEG利用了人眼的心理和生理特徵及其局限性來對彩色的、單色的和多灰度連續色調的、靜態圖像的、數字圖像的壓縮，因此它非常適合不太復雜的以及一般來源於真
實景物的圖像。它定義了兩種基本的壓縮演算法：一種是基於有失真的壓縮演算法，另一種是基於空間線性預測技術(DPCM)無失真的壓縮演算法。為了滿足各種需要，它制定了四種工作模式：無失真壓縮、基於DCT的順序工作方式、累進工作方式和分層工作方式。
MPEG用於活動影像的壓縮。MPEG標准具體包三部分內容：(1)MPEG視頻、(2)MPEG音頻、(3)MP系統(視頻和音頻的同步)。MPEG視頻是標準的核心分，它採用了幀內和幀間相結合的壓縮方法，以離散余變換(DCT)和運動補償兩項技術為基礎，在圖像質量基不變的情況下，MPEG可把圖像壓縮至1／100或更MPEG音頻壓縮演算法則是根據人耳屏蔽濾波功能。利用音響心理學的基本原理，即「某些頻率的音響在重放其頻率的音頻時聽不到」這樣一個特性，將那些人耳完全不到或基本上聽到的多餘音頻信號壓縮掉，最後使音頻號的壓縮比達到8：1或更高，音質逼真，與CD唱片可媲美。按照MPEG標准，MPEG數據流包含系統層和壓層數據。系統層含有定時信號，圖像和聲音的同步、多
分配等信息。壓縮層包含經壓縮後的實際的圖像和聲數據，該數據流將視頻、音頻信號復合及同步後，其數據輸率為1．5MB／s。其中壓縮圖像數據傳輸率為1．2M壓縮聲音傳輸率為0．2MB／s。
MPEG標準的發展經歷了MPEG—I,MPEG一2、MPEG一4、MPEG-7、MPEG一21等不同層次。在MPEG的不同標准中，每—個標准都是建立在前面的標准之上的，並與前面的標准向後的兼容。目前在圖像壓縮中，應用得較多的是MPEG一4標准，MPEG-是在MPEG-2基礎上作了很大的擴充，主要目標是多媒體應用。在MPEG一2標准中，我們的觀念是單幅圖像，而且包含了一幅圖像的全部元素。在MPEG一4標准下，我們的觀念變為多圖像元素，其中的每—個多圖像元素都是獨立編碼處理的。該標准包含了為接收器所用的指令，告訴接收器如何構成最終的圖像。

上圖既表示了MPEG一4解碼器的概念，又比較清楚地描繪了每個部件的用途。這里不是使用單一的視頻或音頻解碼器，而是使用若干個解碼器，其中的每一個解碼器只接收某個特定的圖像(或聲音)元素，並完成解碼操作。每個解碼緩沖器只接收屬於它自己的靈敏據流，並轉送給解碼器。復合存儲器完成圖像元素的存儲，並將它們送到顯示器的恰當位置。音頻的情況也是這樣，但顯然不同點是要求同時提供所有的元素。數據上的時間標記保證這些元素在時間上能正確同步。MPEG一4標准對自然元素(實物圖像)和合成元素進行區分和規定，計算機生成的動畫是合成元素的一個例子。比如，一幅完整的圖像可以包含一幅實際的背景圖，並在前面有一幅動畫或者有另外一幅自然圖像。這樣的每一幅圖像都可以作最佳壓縮，並互相獨立地傳送到接收器，接收器知道如何把這些元素組合在一起。在MPEG一2標准中，圖像被看作一個整體來壓縮；而在MPEG一4標准下，對圖像中的每一個元素進行優化壓縮。靜止的背景不必壓縮到以後的I幀之中去，否則會使帶寬的使用變得很緊張。而如果這個背景圖像靜止10秒鍾，就只要傳送一次(假設我們不必擔心有人在該時間內切人此頻道)，需要不斷傳送的僅是前台的比較小的圖像元素。對有些節目類型，這樣做會節省大量的帶寬。MPEG一4標准對音頻的處理也是相同的。例如，有一位獨唱演員，伴隨有電子合成器，在MPEG一2標准下，我們必須先把獨唱和合成器作混合，然後再對合成的音頻信號進行壓縮與傳送。在MPEG一4標准下，我們可以對獨唱作單獨壓縮，然後再傳送樂器數字介面的聲軌信號，就可以使接收器重建伴音。當然，接收器必須能支持MIDI放音。與傳送合成的信號相比，分別傳送獨唱信號和MIDI數據要節省大量的帶寬。其它的節目類型同樣可以作類似的規定。MPEG一7標准又叫多媒體內容描述介面標准。圖像可以用色彩、紋理、形狀、運動等參數來描述，MPEG一7標準是依靠眾多的參數對圖像與聲音實現分類，並對它們的資料庫實現查詢。
二、多媒體數據壓縮技術的實現方法
目前多媒體壓縮技術的實現方法已有近百種，其中基於信源理論編碼的壓縮方法、離散餘弦變換(DCT)和小波分解技術壓縮演算法的研究更具有代表性。小波技術突破了傳統壓縮方法的局限性，引入了局部和全局相關去冗餘的新思想，具有較大的潛力，因此近幾年來吸引了眾多的研究者。在小波壓縮技術中，一幅圖像可以被分解為若干個叫做「小片」的區域；在每個小片中，圖像經濾波後被分解成若干個低頻與高頻分量。低頻分量可以用不同的解析度進行量化，即圖像的低頻部分需要許多的二進制位，以改善圖像重構時的信噪比。低頻元素採用精細量化，高頻分量可以量化得比較粗糙，因為你不太容易看到變化區域的雜訊與誤差。此外，碎片技術已經作為一種壓縮方法被提出，這種技術依靠實際圖形的重復特性。用碎片技術壓縮圖像時需要佔用大量的計算機資源，但可以獲得很好的結果。藉助於從DNA序列研究中發展出來的模式識別技術，能減少通過WAN鏈路的流量，最多時的壓縮比率能達到90％，從而為網路傳送圖像和聲音提供更大的壓縮比，減輕風絡負荷，更好地實現網路信息傳播。
三、壓縮原理
由於圖像數據之間存在著一定的冗餘，所以使得數據的壓縮成為可能。資訊理論的創始人Shannon提出把數據看作是信息和冗餘度（rendancy）的組合。所謂冗餘度，是由於一副圖像的各像素之間存在著很大的相關性，可利用一些編碼的方法刪去它們，從而達到減少冗餘壓縮數據的目的。為了去掉數據中的冗餘，常常要考慮信號源的統計特性，或建立信號源的統計模型。圖像的冗餘包括以下幾種：
(1) 空間冗餘：像素點之間的相關性。
(2) 時間冗餘：活動圖像的兩個連續幀之間的冗餘。
(3) 信息熵冗餘：單位信息量大於其熵。
(4) 結構冗餘：圖像的區域上存在非常強的紋理結構。
(5) 知識冗餘：有固定的結構，如人的頭像。
(6) 視覺冗餘：某些圖像的失真是人眼不易覺察的。
對數字圖像進行壓縮通常利用兩個基本原理：
(1) 數字圖像的相關性。在圖像的同一行相鄰像素之間、活動圖像的相鄰幀的對應像素之間往往存在很強的相關性，去除或減少這些相關性，也就去除或減少圖像信息中的冗餘度，即實現了對數字圖像的壓縮。
(2) 人的視覺心理特徵。人的視覺對於邊緣急劇變化不敏感(視覺掩蓋效應)，對顏色分辨力弱，利用這些特徵可以在相應部分適當降低編碼精度，而使人從視覺上並不感覺到圖像質量的下降，從而達到對數字圖像壓縮的目的。
編碼壓縮方法有許多種，從不同的角度出發有不同的分類方法，比如從資訊理論角度出發可分 為兩大類：
(1)冗餘度壓縮方法，也稱無損壓縮，信息保持編碼或熵編碼。具體講就是解碼圖像和壓縮 編碼前的圖像嚴格相同，沒有失真，從數學上講是一種可逆運算。
(2)信息量壓縮方法，也稱有損壓縮，失真度編碼或熵壓縮編碼。也就是講解碼圖像和原始圖像是有差別的，允許有一定的失真。
應用在多媒體中的圖像壓縮編碼方法，從壓縮編碼演算法原理上可以分類為：
(1)無損壓縮編碼種類 •哈夫曼編碼 •算術編碼 •行程編碼 •Lempel zev編碼
(2)有損壓縮編碼種類 •預測編碼：DPCM，運動補償 •頻率域方法：正文變換編碼(如DCT)，子帶編碼 •空間域方法：統計分塊編碼 •模型方法：分形編碼，模型基編碼 •基於重要性：濾波，子采樣，比特分配，矢量量化
(3)混合編碼 •JBIG，H261，JPEG，MPEG等技術標准
衡量一個壓縮編碼方法優劣的重要指標
(1)壓縮比要高，有幾倍、幾十倍，也有幾百乃至幾千倍；
(2)壓縮與解壓縮要快，演算法要簡單，硬體實現容易；
(3)解壓縮的圖像質量要好。
四、JPEG圖像壓縮演算法
1．.JPEG壓縮過程

JPEG壓縮分四個步驟實現：
1.顏色模式轉換及采樣；
2.DCT變換；
3.量化；
4.編碼。
2．1．顏色模式轉換及采樣
RGB色彩系統是我們最常用的表示顏色的方式。JPEG採用的是YCbCr色彩系統。想要用JPEG基本壓縮法處理全彩色圖像，得先把RGB顏色模式圖像數據，轉換為YCbCr顏色模式的數據。Y代表亮度，Cb和Cr則代表色度、飽和度。通過下列計算公式可完成數據轉換。
Y=0.2990R+0.5870G+0.1140B
Cb=-0.1687R-0.3313G+0.5000B+128
Cr=0.5000R-0.4187G-0.0813B＋128
人類的眼晴對低頻的數據比對高頻的數據具有更高的敏感度，事實上，人類
的眼睛對亮度的改變也比對色彩的改變要敏感得多，也就是說Y成份的數據是比較重要的。既然Cb成份和Cr成份的數據比較相對不重要，就可以只取部分數據來處理。以增加壓縮的比例。JPEG通常有兩種采樣方式：YUV411和YUV422，它們所代表的意義是Y、Cb和Cr三個成份的資料取樣比例。
2．2.DCT變換
DCT變換的全稱是離散餘弦變換(Discrete Cosine Transform)，是指將一組光強數據轉換成頻率數據，以便得知強度變化的情形。若對高頻的數據做些修飾，再轉回原來形式的數據時，顯然與原始數據有些差異，但是人類的眼睛卻是不容易辨認出來。
壓縮時，將原始圖像數據分成8*8數據單元矩陣，例如亮度值的第一個矩陣內容如下：

JPEG將整個亮度矩陣與色度Cb矩陣，飽和度Cr矩陣，視為一個基本單元稱作MCU。每個MCU所包含的矩陣數量不得超過10個。例如，行和列采樣的比例皆為4:2:2，則每個MCU將包含四個亮度矩陣，一個色度矩陣及一個飽和度矩陣。
當圖像數據分成一個8*8矩陣後，還必須將每個數值減去128，然後一一代入DCT變換公式中，即可達到DCT變換的目的。圖像數據值必須減去128，是因為DCT轉換公式所接受的數字范圍是在-128到+127之間。
DCT變換公式：

x,y代表圖像數據矩陣內某個數值的坐標位置
f(x,y)代表圖像數據矩陣內的數個數值
u,v代表DCT變換後矩陣內某個數值的坐標位置
F(u,v)代表DCT變換後矩陣內的某個數值
u=0 且 v=0 c(u)c(v)=1/1.414
u>0 或 v>0 c(u)c(v)=1
經過DCT變換後的矩陣數據自然數為頻率系數，這些系數以F（0，0）的值最大，稱為DC，其餘的63個頻率系數則多半是一些接近於0的正負浮點數，一概稱之為AC。
3．3、量化
圖像數據轉換為頻率系數後，還得接受一項量化程序，才能進入編碼階段。
量化階段需要兩個8*8矩陣數據，一個是專門處理亮度的頻率系數，另一個則是
針對色度的頻率系數，將頻率系數除以量化矩陣的值，取得與商數最近的整數，
即完成量化。
當頻率系數經過量化後，將頻率系數由浮點數轉變為整數，這才便於執行最
後的編碼。不過，經過量化階段後，所有數據只保留整數近似值，也就再度損失
了一些數據內容，JPEG提供的量化表如下：

2．4、編碼
Huffman編碼無專利權問題，成為JPEG最常用的編碼方式，Huffman編碼通常是以完整的MCU來進行的。
編碼時，每個矩陣數據的DC值與63個AC值，將分別使用不同的Huffman編碼表，而亮度與色度也需要不同的Huffman編碼表，所以一共需要四個編碼表，才能順利地完成JPEG編碼工作。
DC編碼
DC是彩採用差值脈沖編碼調制的差值編碼法，也就是在同一個圖像分量中取得每個DC值與前一個DC值的差值來編碼。DC採用差值脈沖編碼的主要原因是由於在連續色調的圖像中，其差值多半比原值小，對差值進行編碼所需的位數，會比對原值進行編碼所需的位數少許多。例如差值為5，它的二進製表示值為101，如果差值為-5，則先改為正整數5，再將其二進制轉換成1的補碼即可。所謂1的補碼，就是將每個Bit若值為0，便改成1；Bit為1，則變成0。差值5應保留的位數為3，下表即列出差值所應保留的Bit數與差值內容的對照。

在差值前端另外加入一些差值的霍夫曼碼值，例如亮度差值為5（101）的位數為3，則霍夫曼碼值應該是100，兩者連接在一起即為100101。下列兩份表格分別是亮度和色度DC差值的編碼表。根據這兩份表格內容，即可為DC差值加上霍夫曼碼值，完成DC的編碼工作。

AC編碼
AC編碼方式與DC略有不同，在AC編碼之前，首先得將63個AC值按Zig-zag排序，即按照下圖箭頭所指示的順序串聯起來。

63個AC值排列好的，將AC系數轉換成中間符號，中間符號表示為RRRR/SSSS，RRRR是指第非零的AC之前，其值為0的AC個數，SSSS是指AC值所需的位數，AC系數的范圍與SSSS的對應關系與DC差值Bits數與差值內容對照表相似。
如果連續為0的AC個數大於15，則用15/0來表示連續的16個0，15/0稱為ZRL（Zero Rum Length），而（0/0）稱為EOB（Enel of Block）用來表示其後所
剩餘的AC系數皆等於0，以中間符號值作為索引值，從相應的AC編碼表中找出適當的霍夫曼碼值，再與AC值相連即可。
例如某一組亮度的中間符為5/3，AC值為4，首先以5/3為索引值，從亮度AC的Huffman編碼表中找到1111111110011110霍夫曼碼值，於是加上原來100（4）即是用來取[5，4]的Huffman編碼1111111110011110100，[5，4]表示AC值為4的前面有5個零。
由於亮度AC，色度AC霍夫曼編碼表比較長，在此省略去，有興趣者可參閱相關書籍。
實現上述四個步驟，即完成一幅圖像的JPEG壓縮。

❸ 數據無損壓縮演算法

所謂無損壓縮格式，顧名思義，就是毫無損失地將聲音信號進行壓縮的音頻格式。常見的像MP3、WMA等格式都是有損壓縮格式，相比於作為源的WAV文件，它們都有相當大程度的信號丟失，這也是它們能達到10%的壓縮率的根本原因。而無損壓縮格式，就好比用Zip或RAR這樣的壓縮軟體去壓縮音頻信號，得到的壓縮格式還原成WAV文件，和作為源的WAV文件是一模一樣的！但是如果用Zip或RAR來壓縮WAV文件的話，必須將壓縮包解壓後才能播放。而無損壓縮格式則能直接通過播放軟體實現實時播放，使用起來和MP3等有損格式一模一樣。總而言之，無損壓縮格式就是能在不犧牲任何音頻信號的前提下，減少WAV文件體積的格式。

經常使用的無損壓縮演算法有 Shannon-Fano 編碼，Huffman 編碼，行程（Run-length）編碼，LZW（Lempel-Ziv-Welch）編碼和算術編碼等。

Huffman 編碼
該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼。它是統計獨立信源能達到最小平均碼長的編碼方法。編碼效率高 。

基本原理：

依據信源字元出現的概率大小來構造代碼，對出現概率較大的信源字元，給予較短碼長，而對於出現概率較小的信源字元，給予較長的碼長，最後使得編碼的平均碼字最短。

編碼步驟：

（1）初始化，根據符號概率的大小按由大到小順序對符號進行排序。

（2）把概率最小的兩個符號組成一個節點。

（3）重復步驟2。

（4）從根節點開始到相應於每個符號的「樹葉」，從上到下標上「0」（上枝）或者「1」（下枝）至於哪個為「1」哪個為「0」則無關緊要，最後的結果僅僅是分配的代碼不同，而代碼的平均長度是相同的。

（5）從根節點開始順著樹枝到每個葉子分別寫出每個符號的代碼。

無損壓縮演算法有哪些

Huffman編碼的注意點：

Huffman編碼沒有錯誤保護功能，如果碼中有錯誤，則可能引起接下來的一連串解碼錯誤。

Huffman編碼是可變長編碼，因此很難隨意查找或調用中的文件內容。

Huffman依賴於信源的統計特性。 Huffman編碼的每個碼字都是整數：因此實際上平均碼長很難達到信息熵的大小。

Huffman編碼解碼必須要有碼表，如果消息數目很多，那麼

❹ 壓縮演算法原理

哈夫曼
哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符號，長度由特殊符號出現的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多為來表示。

哈夫曼演算法在改變任何符號二進制編碼引起少量密集表現方面是最佳的。然而，它並不處理符號的順序和重復或序號的序列。

2.1 原理
我不打算探究哈夫曼編碼的所有實際的細節，但基本的原理是為每個符號找到新的二進製表示，從而通常符號使用很少的位，不常見的符號使用較多的位。

簡短的說，這個問題的解決方案是為了查找每個符號的通用程度，我們建立一個未壓縮數據的柱狀圖；通過遞歸拆分這個柱狀圖為兩部分來創建一個二叉樹，每個遞歸的一半應該和另一半具有同樣的權（權是 ∑ N K =1 符號數 k , N 是分之中符號的數量，符號數 k 是符號 k出現的次數 ）

這棵樹有兩個目的：

1． 編碼器使用這棵樹來找到每個符號最優的表示方法

2． 解碼器使用這棵樹唯一的標識在壓縮流中每個編碼的開始和結束，其通過在讀壓縮數據位的時候自頂向底的遍歷樹，選擇基於數據流中的每個獨立位的分支，一旦一個到達葉子節點，解碼器知道一個完整的編碼已經讀出來了。

壓縮後的數據流是 24 位（三個位元組），原來是 80 位（ 10 個位元組）。當然，我應該存儲哈夫曼樹，這樣解碼器就能夠解碼出對應的壓縮流了，這就使得該例子中的真正數據流比輸入的流數據量大。這是相對較短的數據上的副作用。對於大數據量來說，上面的哈夫曼樹就不佔太多比例了。

解碼的時候，從上到下遍歷樹，為壓縮的流選擇從左 / 右分支，每次碰到一個葉子節點的時候，就可以將對應的位元組寫到解壓輸出流中，然後再從根開始遍歷。

2.2 實現
哈夫曼編碼器可以在基本壓縮庫中找到，其是非常直接的實現。

這個實現的基本缺陷是：

1． 慢位流實現

2． 相當慢的解碼（比編碼慢）

3． 最大的樹深度是 32 （編碼器在任何超過 32 位大小的時候退出）。如果我不是搞錯的話，這是不可能的，除非輸出的數據大於 2 32位元組。

另一方面，這個實現有幾個優點：

1． 哈夫曼樹以一個緊密的形式每個符號要求 12 位（對於 8 位的符號）的方式存儲，這意味著最大的頭為 384 。

2． 編碼相當容易理解

哈夫曼編碼在數據有噪音的情況（不是有規律的，例如 RLE ）下非常好，這中情況下大多數基於字典方式的編碼器都有問題。

❺ 想了解一下數據壓縮演算法的意義和應用領域

平常用的軟體rar就是用的數據壓縮的技術。

再就是多媒體技術，電影文件的音頻，視頻文件也是採用的數據壓縮，不過他的壓縮技術跟文件的壓縮演算法不一樣。mp4是當前比較流行的音視頻壓縮編碼標准。

壓縮以後，可以大大減小信號傳輸的帶寬，減小文件存儲的空間。

要想詳細了解的話，建議在網上搜一下下面的詞彙，會有所了解的：

有損壓縮
無損壓縮
字典壓縮
mpeg1，mpeg2，mpeg4，
h263，h264
mp3，aac，ac3，amr等

補充：
多媒體壓縮的作用都是
在視頻方面，提高清晰度的同時，減少數據量。
在音頻方面，能高保真回放音頻，同時減少數據量。
降低碼率，減小傳輸的信號帶寬，減小文件存儲時的數據量。

有幾百倍的壓縮率。

你昨天提過類似的問題吧，我回答了一下，因為涉及到當前ic行業的內幕，tiezibeishanle。

❻ 基於Huffman編碼的數據壓縮演算法的研究與實現

這是我們上學期做的一個上機題：

上機題：設電文字元集D及各字元出現的概率F如下：
D={a，b，c，d，e，f，g，h}（字元數n=8）
F={5，29，7，8，14，23，3，11}(%)
編寫完成下列功能的程序：
①構造關於F的Huffman樹；
②求出並列印D總各字元的Huffman編碼。
程序結構： 類型說明；
構造Huffman樹的函數：Huffman_tree(H[m+1])；
求Huffman編碼的函數：Huffman_code(code[n+1])；
main()
{ 變數說明；
輸入字元集D及頻率F；
調用Huffman_tree(H)；
調用Huffman_code(code)；
列印編碼；Y繼續，N退出}

運行後，輸入8個字元（中間不能有空格，否則將空格視為字元處理），然後輸入概率（整數，空格或回車分隔。如果要支持浮點數，要改程序）然後Enter，出現構造的霍夫曼節點和編碼，程序如下：（因為這只是一個上機題目，所以程序不復雜，也沒有論文，希望對你有幫助）
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 8
#define M 2*N-1
#define MAX 32767
typedef char datatype;
typedef struct
{
int wi;
char data;
int Parent,Lchild,Rchild;
}huffm;
typedef struct
{
char bits[N+1];
int start;
char ch;
}ctype;

void Huffman_tree(huffm H[M+1])
{
int i,j,p1,p2;
int w,s1,s2;
for(i=1;i<=M;i++)
{
H[i].wi=MAX;
H[i].Parent=0;
H[i].Lchild=H[i].Rchild=0;
}
printf("please enter the weight:\n");
for(i=1;i<=N;i++)
{
scanf("%d",&H[i].wi);
}

for(i=N+1;i<=M;i++)
{
p1=p2=0;
s1=s2=MAX;
for(j=1;j<=M;j++)
if(H[j].Parent==0)
if(H[j].wi<s1)
{
s2=s1;
s1=H[j].wi;
p2=p1; p1=j;
}
else if(H[j].wi<s2) {s2=H[j].wi; p2=j;}
H[p1].Parent=H[p2].Parent=i;
H[i].Lchild=p1;
H[i].Rchild=p2;
H[i].wi=H[p1].wi+H[p2].wi;
}
printf("Number\tParent\tLchild\tRchild\n");
for(i=1;i<=M;i++)
printf("%d\t%d\t%d\t%d\n",i,H[i].Parent,H[i].Lchild,H[i].Rchild);

}
void Huffman_code(ctype code[N+1])
{
int i,j,p,s;
char c[N];
huffm H[M+1];
ctype md;
printf("please enter char:\n");
/* for(i=1;i<=N;i++)
{
scanf("%c",&c);
H[i].data=code[i].ch=c;
}
*/
scanf("%s",c);
for(i=1;i<=N;i++)H[i].data=code[i].ch=c[i-1];
Huffman_tree(H);

for(i=1;i<=N;i++)
{
md.ch=code[i].ch;
md.start=N+1;
s=i;
p=H[i].Parent;
while(p!=0)
{
md.start--;
if(H[p].Lchild==s)
md.bits[md.start]='1';
else
md.bits[md.start]='0';
s=p;
p=H[p].Parent;
}
code[i]=md;
}
printf("print the code:\n");
for(i=1;i<=N;i++)
printf("%c\t",code[i].ch);
printf("\n");
for(i=1;i<=N;i++)
{
for(j=code[i].start;j<=N;j++)
printf("%c",code[i].bits[j]);
printf("\t");
}
printf("\n");
}
int Continue()
{ char c;
getchar();
printf("continue? y/n\n");
c=getchar();
if(c=='y') return 1;
else return 0;
}
main()
{
do{
/* huffm H[M+1]; */
ctype code[N+1];
Huffman_code(code);

}while(Continue());

}

❼ 數據壓縮的流行演算法

Lempel-Ziv（LZ）壓縮方法是最流行的無損存儲演算法之一。DEFLATE是 LZ 的一個變體，它針對解壓速度與壓縮率進行了優化，雖然它的壓縮速度可能非常緩慢，PKZIP、gzip 以及 PNG 都在使用 DEFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的專利，直到2003年6月專利到期限，這種方法用於 GIF 圖像。另外值得一提的是 LZR (LZ-Renau) 方法，它是 Zip 方法的基礎。LZ 方法使用基於表格的壓縮模型，其中表格中的條目用重復的數據串替換。對於大多數的 LZ 方法來說，這個表格是從最初的輸入數據動態生成的。這個表格經常採用霍夫曼編碼維護（例如，SHRI、LZX）。 一個性能良好基於 LZ 的編碼機制是 LZX，它用於微軟公司的 CAB 格式。

❽ 數據壓縮演算法可分無損壓縮和（ ）壓縮兩種

有損壓縮。無損壓縮是指對原數據毫無損害完全保留，有損是指犧牲一部分數據真實性且對原數據影響不大的情況下，換取更小的壓縮後存儲空間。

❾ 有沒有32可用的數據壓縮演算法

7Zip極限壓縮，效果最好，數據文件實測壓縮率可達15%，已壓縮文件可達80%！唯一缺點是解壓和壓縮同時極慢！想要速度可以用Zip！但Zip效果可能最差！
-

❿ 是關於數據壓縮演算法的問題

這個也。。。。。。查看度娘有沒有類似的源代碼去吧！！！