哈夫曼圖片壓縮

Ⅰ Huffman編碼不適合圖像壓縮么，為什麼。有相關的資料么。能給我看看不QQ504278770

下面是我從網上搜索到的資料，希望對你有幫助。

1.哈夫曼圖像壓縮演算法引言

隨著網路與多媒體技術的興起，人們需要存儲和傳輸的數據越來越多，數據量越來越大，以前帶寬有限的傳輸網路和容量有限的存儲介質難以滿足用戶的需求。

特別是聲音、圖像和視頻等媒體在人們的日常生活和工作中的地位日益突出，這個問題越發顯得嚴重和迫切。如今，數據壓縮技術早已是多媒體領域中的關鍵技術之一。

Huffman(哈夫曼)演算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明Huffman演算法在無損壓縮演算法中是最優的。Huffman原理簡單，實現起來也不困難，在現在的主流壓縮軟體得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合，Huffman演算法是非常好的選擇。

2.哈夫曼圖像壓縮演算法原理

Huffman編碼是1952年由Huffman提出的對統計獨立信源能達到最小平均碼長的編碼方法。這一年，他發表了著名論文「A Method for the Construction of Minimum Rendancy Codes」，即最短冗餘碼的構造方法.之後，Huffman編碼及其一些改進方法一直是數據壓縮領域的研究熱點之一。

Huffman碼是一種變長碼，其基本思想是：先統計圖像(已經數字化)中各灰度出現的概率，出現概率較大的賦以較短的碼字，而出現概率較小的則賦以較長的碼字。我們可以用下面的框圖來表示Huffman編碼的過程：

在整個編碼過程中，統計圖像各灰度級出現的概率和編碼這兩步都很簡單，關鍵的是Huffman樹的構造。不但編碼的時候需要用到這顆樹，解碼的時候也必須有這顆樹才能完成解碼工作，因此，Huffman樹還得完整的傳輸到解碼端。

Huffman樹的構造可以按照下面圖2的流程圖來完成。首先對統計出來的概率從小到大進行排序，然後將最小的兩個概率相加;到這兒的時候，先把已經加過的兩個概率作為樹的兩個節點，並把他們從概率隊列中刪除;然後把相加所得的新概率加入到隊列中，對這個新隊列進行排序。

如此反復，直到最後兩個概率相加為1的時候停止。這樣，Huffman樹就建立起來了。

3. 哈夫曼圖像壓縮演算法軟體實現

這兒，我們以Turbo C為例來說明軟體實現Huffman圖像壓縮演算法的一些關鍵技術。

為了敘述方便，我們不妨假設處理的圖像的灰度級變化范圍從0到255，即具有256個灰度級。我們先來統計輸入圖像的概率，實際上是要統計各個灰度級在整幅圖像中出現的次數。為此，我們先定義一個具有256個元素的數組。

然後對輸入圖像信號進行掃描，每出現一個灰度，就把它存入實現定義好的一個數組中的相應元素中(讓這個元素的值自增1)。最後，通過讀取數組中各元素的值就可以求出各個灰度出現的頻數。

接下來就該構造Huffman樹了。為了構造Huffman樹，我們要用到C語言中鏈表的概念。我們必須用一個結構體來表示Huffman樹的節點。對於每個節點而言我們需要這樣幾個信息：本節點的權重(就是灰度的頻數)、指向父節點的指針和分別指向左右子葉節點的指針。於是，我們可以定義這樣一個結構體：

Struct Node{

Floatweight;

Node * father;

Node * left;

Node * right;}Huffman_Node

我們需要先確定權最低的兩個自由結點，這將是最初的left和right節點。然後建立這兩個結點的父結點，並讓它的權等於這兩個結點的權之和。

接著將這個父結點增加到自由結點的序列中，而兩個子結點則從序列中去掉。重復前面的步驟直到只剩下一個自由結點，這個自由結點就是Huffman樹的根。

Huffman編碼樹作為一個二叉樹從葉結點逐步向上建立。Huffman樹建立好以後，為了把權、概率等數值轉化碼字，我們還得對整個Huffman樹進行掃描。請注意，在建立Huffman樹的時候，我們是從樹葉開始的，而在對Huffman樹分配碼字的時候卻剛好相反，是從樹根開始，沿著各個樹枝的走向「順藤摸瓜」似的對各個系數進行編碼。

對於一個節點的兩個子節點(left和right)，其中一個節點對應的位為0，而另一個結點則人為地設置成為l。解碼的時候也是完全相同的一顆Huffman樹完成的。下面的循環是實現壓縮的關鍵語句之一[ 1 ]。

for (i = length-1; i >= 0; ――i) {

if ((current_code >> i) & 1)

thebyte |= (char) (1 << curbit);

if (--curbit < 0) {

putc (thebyte, ofile);

thebyte = 0;

curbyte++;

curbit = 7;

}

}

注意：這幾行代碼執行了數據壓縮的功能，但是還沒有生成編碼和解碼所需要的代碼表。

4.哈夫曼圖像壓縮演算法性能評價

我們主要從三方面[ 2 ]來評價Huffman的性能：

(1)壓縮比的大小;

(2)恢復效果的好壞，也就是能否盡可能的恢復原始數據;

(3)演算法的簡單易用性以及編、解碼的速度。

首先分析一下對壓縮比的影響因素(不同的著作中對壓縮比的定義不盡相同，這兒我們採用如下定義：壓縮比等於壓縮之前的以比特計算的數據量比上壓縮之後的數據量)。對於Huffman編碼來說，我們因為要用額外的位保存和傳輸Huffman樹而「浪費」掉一些存儲位，也就是說，為了編、解碼的方便，我們把本已減少的數據量又增加了一些。

如果文件比較大的話，這一點多餘的數據根本算不了什麼，所佔比例很小。但是，如果壓縮的文件本來就很小的話，那麼這筆數據就很可觀了。一般來說，經典的Huffman演算法的壓縮比不是很高，這是無損壓縮的「通病」。

第二點就不用說了，由於它是無損壓縮，能夠完全恢復壓縮之前圖像的本來面貌。

最後，讓我們來分析一下Huffman壓縮方法的速度問題。大家在第三節中已經看到了，在壓縮的過程中，我們進行了兩次掃描，第一次是為了統計各個灰度出現的頻數而掃描整幅圖像，第二次則是為了分配碼字而掃描整個Huffman樹。

這樣一來，對較大的文件進行編碼時，頻繁的磁碟讀寫訪問必然會降低數據編碼的速度，如果用於網路的話，還會因此帶來一些延時，不利於實時壓縮和傳輸。另外，Huffman演算法的編碼和解碼的速度是不對稱的，解碼快於編碼，因為解碼不需要生成Huffman樹的環節。

5.圖像壓縮演算法結束語

Huffman演算法目前已經得到了廣泛的應用，軟體和硬體都已經實現。基於Huffman經典演算法的缺陷，不少人提出了一些自適應演算法。前面的演算法中，Huffman樹是整個圖像全部輸入掃描完成後構造出來的，而自適應演算法(或稱動態演算法)則不必等到全部圖像輸入完成才開始樹的構造，並且可以根據後面輸入的數據動態的對Huffman樹進行調整。實際上，實用的Huffman樹都是經過某種優化後的動態演算法。

網路資源

Ⅱ 基於線性預測和huffman碼的無失真圖像壓縮碼編

哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹—即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用於數據壓縮。 在計算機信息處理中，「哈夫曼編碼」是一種一致性編碼法（又稱"熵編碼法"），用於數據的無損耗壓縮。這一術語是指使用一張特殊的編碼表將源字元（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在於，它是根據每一個源字元出現的估算概率而建立起來的（出現概率高的字元使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之後的字元串的平均期望長度降低，從而達到無損壓縮數據的目的）。這種方法是由David.A.Huffman發展起來的。 例如，在英文中，e的出現概率很高，而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均佔用一個位元組（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較准確的估算，就可以大幅度提高無損壓縮的比例。

本文描述在網上能夠找到的最簡單，最快速的哈夫曼編碼。本方法不使用任何擴展動態庫，比如STL或者組件。只使用簡單的C函數，比如：memset，memmove，qsort，malloc，realloc和memcpy。
因此，大家都會發現，理解甚至修改這個編碼都是很容易的。

背景
哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。
編碼使用
我用簡單的C函數寫這個編碼是為了讓它在任何地方使用都會比較方便。你可以將他們放到類中，或者直接使用這個函數。並且我使用了簡單的格式，僅僅輸入輸出緩沖區，而不象其它文章中那樣，輸入輸出文件。
bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
要點說明
速度
為了讓它(huffman.cpp)快速運行，我花了很長時間。同時，我沒有使用任何動態庫，比如STL或者MFC。它壓縮1M數據少於100ms（P3處理器，主頻1G）。
壓縮
壓縮代碼非常簡單，首先用ASCII值初始化511個哈夫曼節點：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
然後，計算在輸入緩沖區數據中，每個ASCII碼出現的頻率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然後，根據頻率進行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
現在，構造哈夫曼樹，獲取每個ASCII碼對應的位序列：
int nNodeCount = GetHuffmanTree(nodes);
構造哈夫曼樹非常簡單，將所有的節點放到一個隊列中，用一個節點替換兩個頻率最低的節點，新節點的頻率就是這兩個節點的頻率之和。這樣，新節點就是兩個被替換節點的父節點了。如此循環，直到隊列中只剩一個節點（樹根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
這里我用了一個好的訣竅來避免使用任何隊列組件。我先前就直到ASCII碼只有256個，但我分配了511個(CHuffmanNode nodes[511])，前255個記錄ASCII碼，而用後255個記錄哈夫曼樹中的父節點。並且在構造樹的時候只使用一個指針數組(ChuffmanNode *pNodes[256])來指向這些節點。同樣使用兩個變數來操作隊列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接著，壓縮的最後一步是將每個ASCII編碼寫入輸出緩沖區中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位為界限右移後到達右邊位元組的前面
(nDesIndex&7): &7 得到最高位.
注意：在壓縮緩沖區中，我們必須保存哈夫曼樹的節點以及位序列，這樣我們才能在解壓縮時重新構造哈夫曼樹（只需保存ASCII值和對應的位序列）。
解壓縮
解壓縮比構造哈夫曼樹要簡單的多，將輸入緩沖區中的每個編碼用對應的ASCII碼逐個替換就可以了。只要記住，這里的輸入緩沖區是一個包含每個ASCII值的編碼的位流。因此，為了用ASCII值替換編碼，我們必須用位流搜索哈夫曼樹，直到發現一個葉節點，然後將它的ASCII值添加到輸出緩沖區中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}

Ⅲ android黑科技，圖片終極壓縮

一、支持自定義配置、不失真和批量處理

二、圖片上傳為什麼要壓縮
1、圖片伺服器空間限制，磁碟昂貴
2、網路不穩定，大文件需要斷點續傳
3、盡可能避免安卓OOM異常
4、後台約定的規則<200KB
5、需要上傳原圖的應用有醫院臨床項目、金融銀行

三、圖片壓縮流程
1、遞歸每張圖片
2、設置圖片格式 Bitmap.CompressFormat.JPG
png, jpg,webp
3、質量壓縮bitmap.compress(format,quality,baos)
由於png是無損壓縮，所以設置quality無效（不適合作為縮略圖）
采樣率壓縮BitmapFactory.Options.inSampleSize
縮小圖片解析度，減少所佔用磁碟空間和內存大小
縮放壓縮canvas.drawBitmap(bitmap, null,rectF,null)
減少圖片的像素，降低所佔用磁碟空間大小和內存大小，可用於緩存縮略圖
JNI調用JPEG庫
Android的圖片引擎使用的是閹割版的skia引擎，去掉了圖片壓縮中的哈夫曼演算法
4、像素修復
5、返回壓縮
6、完成壓縮

demo： https://github.com/ApeCold/Learn_Compress_Sample

參考：
Luban框架 https://github.com/Curzibn/Luban
缺點
1、當沒有設定壓縮路徑時，拋異常無閃退
2、源碼中，壓縮比率固定值60，無法修改
3、壓縮配置，參數不太適應真實項目需求
4、不能指定壓縮大小，比如100KB以內
https://github.com/zettsu/Compressor

Ⅳ 圖片壓縮的原理

首先說明 jpeg圖片：
JPEG是joint Photographic Experts Group(聯合圖像專家組)的縮寫，文件後輟名為"．jpg"或"．jpeg"，是最常用的圖像文件格式，由一個軟體開發聯合會組織制定，是一種有損壓縮格式，能夠將圖像壓縮在很小的儲存空間，圖像中重復或不重要的資料會被丟失，因此容易造成圖像數據的損傷。尤其是使用過高的壓縮比例，將使最終解壓縮後恢復的圖像質量明顯降低，如果追求高品質圖像，不宜採用過高壓縮比例。但是JPEG壓縮技術十分先進，它用有損壓縮方式去除冗餘的圖像數據，在獲得極高的壓縮率的同時能展現十分豐富生動的圖像，換句話說，就是可以用最少的磁碟空間得到較好的圖像品質。而且 JPEG是一種很靈活的格式，具有調節圖像質量的功能，允許用不同的壓縮比例對文件進行壓縮，支持多種壓縮級別，壓縮比率通常在10：1到40：1之間，壓縮比越大，品質就越低；相反地，壓縮比越小，品質就越好。比如可以把1．37Mb的BMP點陣圖文件壓縮至20．3KB。當然也可以在圖像質量和文件尺寸之間找到平衡點。JPEG格式壓縮的主要是高頻信息，對色彩的信息保留較好，適合應用於互聯網，可減少圖像的傳輸時間，可以支持24bit真彩色，也普遍應用於需要連續色調的圖像。
JPEG格式是目前網路上最流行的圖像格式，是可以把文件壓縮到最小的格式，在 Photoshop軟體中以JPEG格式儲存時，提供11級壓縮級別，以0—10級表示。其中0級壓縮比最高，圖像品質最差。即使採用細節幾乎無損的10 級質量保存時，壓縮比也可達 5：1。以BMP格式保存時得到4．28MB圖像文件，在採用JPG格式保存時，其文件僅為178KB，壓縮比達到24：1。經過多次比較，採用第8級壓縮為存儲空間與圖像質量兼得的最佳比例。
JPEG格式的應用非常廣泛，特別是在網路和光碟讀物上，都能找到它的身影。目前各類瀏覽器均支持JPEG這種圖像格式，因為JPEG格式的文件尺寸較小，下載速度快。
JPEG2000作為JPEG的升級版，其壓縮率比JPEG高約30％左右，同時支持有損和無損壓縮。JPEG2000格式有一個極其重要的特徵在於它能實現漸進傳輸，即先傳輸圖像的輪廓，然後逐步傳輸數據，不斷提高圖像質量，讓圖像由朦朧到清晰顯示。此外，JPEG2000還支持所謂的"感興趣區域" 特性，可以任意指定影像上感興趣區域的壓縮質量，還可以選擇指定的部分先解壓縮。
JPEG2000和JPEG相比優勢明顯，且向下兼容，因此可取代傳統的JPEG格式。JPEG2000即可應用於傳統的JPEG市場，如掃描儀、數碼相機等，又可應用於新興領域，如網路傳輸、無線通訊等等。
優點：
攝影作品或寫實作品支持高級壓縮。
利用可變的壓縮比可以控制文件大小。
支持交錯（對於漸近式 JPEG 文件）。
JPEG 廣泛支持 Internet 標准。
缺點：
有損耗壓縮會使原始圖片數據質量下降。
當您編輯和重新保存 JPEG 文件時，JPEG 會混合原始圖片數據的質量下降。這種下降是累積性的。
JPEG 不適用於所含顏色很少、具有大塊顏色相近的區域或亮度差異十分明顯的較簡單的圖片。
你看不出改變 不等於沒有改變，人的視力范圍里有些色彩的區別是無法分辨的，而把這些圖片信息去掉，你看起來沒區別，但圖片大小已經被壓縮了

Ⅳ 演算法解析：哈夫曼（huffman）壓縮演算法

本篇將介紹 哈夫曼壓縮演算法（Huffman compression）

眾所周知，計算機存儲數據時，實際上存儲的是一堆0和1（二進制）。

如果我們存儲一段字元：ABRACADABRA!

那麼計算機會把它們逐一翻譯成二進制，如A：01000001；B: 01000010; !: 00001010.

每個字元佔8個bits, 這一整段字元則至少佔12*8=96 bits。

但如果我們用一些特殊的值來代表這些字元，如：

圖中，0代表A; 1111代表B；等等。此時，存儲這段字元只需30bits，比96bits小多了，達到了壓縮的目的。

我們需要這么一個表格來把原數據翻譯成特別的、占空間較少的數據。同時，我們也可以用這個表格，把特別的數據還原成原數據。

首先，為了避免翻譯歧義，這個表格需滿足一個條件： 任何一個字元用的值都不能是其它字元的前綴 。

我們舉個反例：A: 0; B: 01;這里，A的值是B的值的前綴。如果壓縮後的數據為01xxxxxx,x為0或者1，那麼這個數據應該翻譯成A1xxxxxx, 還是Bxxxxxxx?這樣就會造成歧義。

然後，不同的表格會有不同的壓縮效果，如：

這個表格的壓縮效果更好。

那麼我們如何找到 最好的表格 呢？這個我們稍後再講。

為了方便閱讀，這個表格是可以寫成一棵樹的：

這棵樹的節點左邊是0，右邊是1。任何含有字元的節點都沒有非空子節點。（即上文提及的前綴問題。）

這棵樹是在壓縮的過程中建成的，這個表格是在樹形成後建成的。用這個表格，我們可以很簡單地把一段字元變成壓縮後的數據，如：

原數據：ABRACADABRA!

表格如上圖。

令壓縮後的數據為S；

第一個字元是A，根據表格，A：11，故S=11;

第二個字元是B，根據表格，B：00，故S=1100;

第三個字元是R，根據表格，R：011，故S=1100011;

如此類推，讀完所有字元為止。

壓縮搞定了，那解壓呢？很簡單，跟著這棵樹讀就行了：

壓縮後的數據S=11000111101011100110001111101

記住，讀到1時，往右走，讀到0時，往左走。

令解壓後的字元串為D；

從根節點出發，第一個數是1，往右走：

第二個數是1，往右走：

讀到有字元的節點，返回此字元，加到字元串D里。D:A;

返回根節點，繼續讀。

第三個數是0，往左走：

第四個數是0，往左走：

讀到有字元的節點，返回此字元，加到字元串D里。D:AB;

返回根節點，繼續讀。

第五個數是0，往左走：

第六個數是1，往右走：

第七個數是1，往右走：

讀到有字元的節點，返回此字元，加到字元串D里。D:ABR;

返回根節點，繼續讀。

如此類推，直到讀完所有壓縮後的數據S為止。

壓縮與解壓都搞定了之後 我們需要先把原數據讀一遍，並把每個字元出現的次數記錄下來。如：

ABRACADABRA!中，A出現了5次;B出現了2次;C出現了1次;D出現了1次;R出現了2次;!出現了1次。

理論上，出現頻率越高的字元，我們給它一個佔用空間越小的值，這樣，我們就可以有最佳的壓縮率

由於哈夫曼壓縮演算法這塊涉及內容較多 ，文章篇幅很長；全文全方面講解了Compose布局的各方面知識。更多Android前言技術進階，我自薦一套《 完整的Android的資料，以及一些視頻課講解 》 現在私信發送「進階」或者「筆記」即可免費獲取

最後我想說：

對於程序員來說，要學習的知識內容、技術有太多太多，要想不被環境淘汰就只有不斷提升自己，從來都是我們去適應環境，而不是環境來適應我們

技術是無止境的，你需要對自己提交的每一行代碼、使用的每一個工具負責，不斷挖掘其底層原理，才能使自己的技術升華到更高的層面

Android 架構師之路還很漫長，與君共勉

Ⅵ 如何用哈夫曼編碼對圖像進行壓縮

% 演示圖象的哈夫曼編解碼過程
% chenyong 2009.04.20

clear all;
close all;
clc;
Dimens = 256; % 矩陣維數，假設矩陣為方陣即256*256
src_size = Dimens^2; % 矩陣元素的個數
gray_level = 9; % 灰度級

src = randn(Dimens); %產生模擬圖像矩陣，滿足正態分布，零均值，方差為1
%src = randint(Dimens,Dimens,gray_level); % 產生隨機圖像矩陣，灰度值為0~63，滿足均勻分布
src_one = reshape(src,1,src_size);
src_max = max(src_one);
src_min = min(src_one);
quan = linspace(src_min,src_max,gray_level); % 產生均勻量化區間
src_d = []; % 數字矩陣
for row = 1:Dimens % 逐點量化
for vol = 1:Dimens
diff = abs(src(row,vol)-quan);
[min_diff,min_index] = min(diff);
quan_gray = min_index -1;
src_d(row,vol) = quan_gray;
end
end

%將數字圖像矩陣還原成模擬矩陣
src_a = [];
quan_space = quan(2)-quan(1);
for row = 1:Dimens
for vol = 1:Dimens
src_a(row,vol) = src_d(row,vol) * quan_space + src_min;
end
end

% prob數組保存圖像中各灰度出現的概率
prob = [];
for src_value=0:(gray_level-1)
index = find(src_d==src_value);
i = src_value + 1;
prob(i) = length(index)/src_size;
end

% 畫出直方圖
% stem(0:gray_level-1,prob);
% xlabel('灰度值');
% ylabel('概率');
% title('灰度直方圖');

% huffman編碼
p = prob;
n=length(p);
q=p;
m=zeros(n-1,n);
for i=1:n-1
[q,l]=sort(q);
m(i,:)=[l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
end
bre=zeros(n-1,n);
bre(n-1,1)=0+j; %虛部表示當前的二進制數的位數，以下類似
bre(n-1,2)=1+j;
for time=1:n-2
loc_1 = find(real(m(n-time,:))==1);
prebit = bre(n-time,loc_1);
bre(n-time-1,1) = (real(prebit)*2 + 0) + j*(imag(prebit)+1);
bre(n-time-1,2) = (real(prebit)*2 + 1) + j*(imag(prebit)+1);

loc_not1 = find(real(m(n-time,:))>1);
bre(n-time-1,3:3+time-1) = bre(n-time,loc_not1);
end
[m1,index] = sort(m(1,:));
code = bre(1,index);
code_data = real(code);
code_bits = imag(code);
disp(['gray level',' ', 'huffman code']);
for i = 1:length(code)
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i)))]);
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i),code_bits(i)))]);
end
code_binary = dec2bin(code_data);

%逐點編碼
out = [];
for row = 1:Dimens
for vol = 1:Dimens
now_gray = src_d(row,vol);
now_code = code_binary(now_gray+1,:);
now_bits = code_bits(now_gray+1);
now_code = now_code(end-now_bits+1:end);
out = [out, now_code];
end
end

%計算壓縮比
real_bitnum = length(out);
bitnum_no_huffman = src_size*nextpow2(gray_level);
comp_ratio =bitnum_no_huffman/real_bitnum;
Lavg = real_bitnum/src_size;
Hshannon = (-1)*prob*(log2(prob))';
disp(['Lavg = ',num2str(Lavg)]);
disp(['normal bit num = ',num2str(nextpow2(gray_level))]);
disp(['comp_ratio = ',num2str(comp_ratio)]);
disp(['Hshannon = ',num2str(Hshannon)]);

Ⅶ libjpeg-turbo 圖片壓縮

android7.0之前，Bitmap.compress不支持哈夫曼壓縮演算法，壓縮效率不高，因此引入libTurboJpeg庫來改善壓縮效率。
安卓底層使用Skia作為它的圖片處理引擎，通過對libjpeg進行封裝，來進行壓縮圖片。然而在libjpeg進行壓縮圖片時，有一個參數，叫optimize_coding，默認為FALSE。關於這個參數，官方的解釋是，如果設置為TRUE，在壓縮過程中，會計算哈夫曼表，這會顯著消耗空間和時間。

然而這是對於十幾年前的設備而言的，現在的設備來做這個計算完全沒有壓力。因此，只有在安卓7.0之後，才支持了哈夫曼演算法。

開發時，把Java層的Bitmap傳遞到native層，然後使用 AndroidBitmap API 取出圖像所有的argb數據，接著可以舍棄a通道信息，只保留rgb信息到一個新的uint_8數組中，將這個數組作為參數傳入jpeg-turbo庫中，開啟哈夫曼編碼，就可以保存到一個新的路徑中。
參考鏈接： https://www.jianshu.com/p/32ff62bc33d5?from=timeline

我們來看看2，6，8，9，3權值節點構成哈夫曼樹的過程。

初始時候各個節點獨立，先將其排序(這里使用優先隊列)，然後選兩個最小節點(拋出)生成一個新的節點，再將其加入優先隊列中，此次操作完成後優先隊列中有5，6，8，9節點

重復上面操作，這次結束 隊列中有11，8，9節點(排序後8，9，11)

如果隊列為空，那麼返回節點，並且這個節點為整個哈夫曼樹根節點root。

否則繼續加入隊列進行排序。重復上述操作，直到隊列為空。

先統計字元出現的次數，然後將這個次數當成權值按照上面介紹的方法構造一棵哈夫曼樹，然後樹的根不存，往左為0往右為1每個葉子節點得到的二進制數字就是它的編碼，這樣頻率高的字元在上面更短在整個二進制存儲中也更節省空間。

Ⅷ 利用哈夫曼編碼進行壓縮壓縮率一般達到多少

哈夫曼編碼進行壓縮的壓縮率是根據平均碼長來計算的，壓縮率比較低。

例如：用三位二進行數進行的等長編碼平均長度為3，而根據哈夫曼樹編碼的平均碼長為：

4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

2.61/3=0.87=87%

其平均碼長是等長碼的87%，所以平均壓縮率為13%。

哈夫曼編碼，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。

Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。

壓縮率，描述壓縮文件的效果名，是文件壓縮後的大小與壓縮前的大小之比，例如：把100m的文件壓縮後是90m，壓縮率為90/100*100%=90%，壓縮率一般是越小越好，但是壓得越小，解壓時間越長。

(8)哈夫曼圖片壓縮擴展閱讀

哈夫曼編碼的具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率 和剩餘的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最後變成1。

每次相 加時都將「0」和「1」賦與相加的兩個概率，讀出時由該符號開始一直走到最後的「1」， 將路線上所遇到的「0」和「1」按最低位到最高位的順序排好，就是該符號的哈夫曼編碼。

Ⅸ 如何寫壓縮軟體，運用哈夫曼演算法實現

到文件壓縮大家很容易想到的就是rar,zip等我們常見的壓縮格式。然而，還有一種就是大家在學習數據結構最常見到的哈夫曼樹的數據結構，以前還不知道他又什麼用，其實他最大的用途就是用來做壓縮，也是一些rar,zip壓縮的祖先，稱為哈弗曼壓縮（什麼你不知道誰是哈弗曼，也不知道哈弗曼壓縮，不急等下介紹）。

隨著網路與多媒體技術的興起，人們需要存儲和傳輸的數據越來越多，數據量越來越大，以前帶寬有限的傳輸網路和容量有限的存儲介質難以滿足用戶的需求。

特別是聲音、圖像和視頻等媒體在人們的日常生活和工作中的地位日益突出，這個問題越發顯得嚴重和迫切。如今，數據壓縮技術早已是多媒體領域中的關鍵技術之一。

一、什麼是哈弗曼壓縮

Huffman(哈夫曼)演算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明Huffman演算法在無損壓縮演算法中是最優的。Huffman原理簡單，實現起來也不困難，在現在的主流壓縮軟體得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合，Huffman演算法是非常好的選擇。

二、怎麼實現哈弗曼壓縮

哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。

故我們得了解幾個概念：

1、二叉樹：在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。2、哈夫曼編碼(Huffman Coding)：是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。uffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。三、哈夫曼編碼生成步驟：

①掃描要壓縮的文件，對字元出現的頻率進行計算。

②把字元按出現的頻率進行排序，組成一個隊列。

③把出現頻率最低（權值）的兩個字元作為葉子節點，它們的權值之和為根節點組成一棵樹。

④把上面葉子節點的兩個字元從隊列中移除，並把它們組成的根節點加入到隊列。

⑤把隊列重新進行排序。重復步驟③④⑤直到隊列中只有一個節點為止。

⑥把這棵樹上的根節點定義為0（可自行定義0或1）左邊為0，右邊為1。這樣就可以得到每個葉子節點的哈夫曼編碼了。

既如 (a)、(b)、(c)、(d)幾個圖，就可以將離散型的數據轉化為樹型的了。

如果假設樹的左邊用0表示右邊用1表示，則每一個數可以用一個01串表示出來。

則可以得到對應的編碼如下：
1-->110
2-->111
3-->10
4-->0
每一個01串，既為每一個數字的哈弗曼編碼。
為什麼能壓縮：
壓縮的時候當我們遇到了文本中的1、2、3、4幾個字元的時候，我們不用原來的存儲，而是轉化為用它們的01串來存儲不久是能減小了空間佔用了嗎。（什麼01串不是比原來的字元還多了嗎？怎麼減少？）大家應該知道的，計算機中我們存儲一個int型數據的時候一般式佔用了2^32-1個01位，因為計算機中所有的數據都是最後轉化為二進制位去存儲的。所以，想想我們的編碼不就是只含有0和1嘛，因此我們就直接將編碼按照計算機的存儲規則用位的方法寫入進去就能實現壓縮了。
比如：
1這個數字，用整數寫進計算機硬碟去存儲，佔用了2^32-1個二進制位
而如果用它的哈弗曼編碼去存儲，只有110三個二進制位。
效果顯而易見。

Ⅹ 哈夫曼壓縮演算法的內容是什麼

注:哈夫曼和lzss演算法不是同一種演算法,先用哈夫曼再用lzss演算法壓縮後會發現經哈夫曼壓縮後再用lzss壓縮文件會變大,具體原因不明
lzss原理:
把編碼位置置於輸入數據流的開始位置。
在前向緩沖器中查找窗口中最長的匹配串
①
pointer
：=匹配串指針。
②
length
：=匹配串長度。
判斷匹配串長度length是否大於等於最小匹配串長度(min_length)
，
如果「是」：輸出指針，然後把編碼位置向前移動length個字元。
如果「否」：輸出前向緩沖存儲器中的第1個字元，然後把編碼位置向前移動一個字元。
如果前向緩沖器不是空的，就返回到步驟2。
例：編碼字元串如表03-05-3所示，編碼過程如表03-05-4所示。現說明如下：
「步驟」欄表示編碼步驟。
「位置」欄表示編碼位置，輸入數據流中的第1個字元為編碼位置1。
「匹配」欄表示窗口中找到的最長的匹配串。
「字元」欄表示匹配之後在前向緩沖存儲器中的第1個字元。
「輸出」欄的輸出為：
①
如果匹配串本身的長度length
>=
min_length，輸出指向匹配串的指針，格式為(back_chars，
chars_length)。該指針告訴解碼器「在這個窗口中向後退back_chars個字元然後拷貝chars_length個字元到輸出」。
②
如果匹配串本身的長度length
>=
min_length，則輸出真實的匹配串。
表:輸入數據流
位置
1234567891011
字元
aabbcbbaabc
表:編碼過程(min_length
=
2)
步驟位置匹配串輸出
11--a
22aa
33--
b
44bb
55--c
66b
b(3,2)
78
a
a
b(7,3)
811cc