Huffman編碼是什麼?Huffman 編碼是一種資料壓縮演算法。我們常用的 zip 壓縮,其核心就是 Huffman 編碼,還有在 HTTP/中,Huffman 編碼被用於 HTTP 頭部的壓縮。這篇文章中我將給大家分享php中Huffman編碼與解碼的實作方法。
1. Huffman編碼
字數統計
Huffman編碼的第一步就是要統計文件中每個字元出現的次數,PHP的內建函數count_chars() 就可以做到:
$input = file_get_contents('input.txt'); $stat = count_chars($input, 1);
建構Huffman樹
接下來根據統計結果建構Huffman樹,建構方法在Wikipedia 有詳細的描述。這裡用PHP寫了一個簡易版的:
$huffmanTree = [];foreach ($stat as $char => $count) { $huffmanTree[] = [ 'k' => chr($char), 'v' => $count, 'left' => null, 'right' => null, ]; }// 构造树的层级关系,思想见wiki:https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81$size = count($huffmanTree);for ($i = 0; $i !== $size - 1; $i++) { uasort($huffmanTree, function ($a, $b) { if ($a['v'] === $b['v']) { return 0; } return $a['v'] < $b['v'] ? -1 : 1; }); $a = array_shift($huffmanTree); $b = array_shift($huffmanTree); $huffmanTree[] = [ 'v' => $a['v'] + $b['v'], 'left' => $b, 'right' => $a, ]; } $root = current($huffmanTree);
經過計算之後,$root 就會指向Huffman 樹的根節點
根據Huffman樹產生編碼字典
#有了Huffman 樹,就可以產生用於編碼的字典:
function buildDict($elem, $code = '', &$dict) { if (isset($elem['k'])) { $dict[$elem['k']] = $code; } else { buildDict($elem['left'], $code.'0', $dict); buildDict($elem['right'], $code.'1', $dict); } } $dict = []; buildDict($root, '', $dict);
寫入檔案
#運用字典將檔案內容編碼,並寫入檔案。將Huffman編碼寫入檔案的有幾個注意的地方:
將編碼字典和編碼內容一起寫入檔案後,就沒法區分他們的邊界了,因此需要在檔案開始寫入他們各自佔用的位元組數
PHP提供的fwrite() 函數一次能寫入8-bit(一個位元組)或是8的整數倍個bit。但Huffman編碼中,一個字元可能只用 1-bit 表示,PHP不支援只往檔案中寫入 1-bit 這種操作。所以需要我們自行對編碼進行拼接,每湊齊 8-bit 才會寫入檔案。
每湊齊8-bit才寫入
與第二條類似,最終形成的檔案大小一定是 8-bit 的整數倍。所以如果整個編碼的大小是8001-bit的話,還要在末尾補上7個0
$dictString = serialize($dict);// 写入字典和编码各自占用的字节数 $header = pack('VV', strlen($dictString), strlen($input)); fwrite($outFile, $header);// 写入字典本身 fwrite($outFile, $dictString);// 写入编码的内容$buffer = ''; $i = 0;while (isset($input[$i])) { $buffer .= $dict[$input[$i]]; while (isset($buffer[7])) { $char = bindec(substr($buffer, 0, 8)); fwrite($outFile, chr($char)); $buffer = substr($buffer, 8); } $i++; }// 末尾的内容如果没有凑齐 8-bit,需要自行补齐 if (!empty($buffer)) { $char = bindec(str_pad($buffer, 8, '0')); fwrite($outFile, chr($char)); } fclose($outFile);
2.Huffman編碼的解碼
Huffman編碼的解碼相對簡單:先讀取編碼字典,然後根據字典解碼出原始字元。
解碼過程有個問題要注意:由於我們在編碼過程中,在檔案結尾補齊了幾個0-bit,如果這些0-bit 在字典中剛好是某個字元的編碼時,就會造成錯誤的解碼。
所以解碼過程中,當已解碼的字元數達到文件長度時,就要停止解碼。
<?php $content = file_get_contents('a.out');// 读出字典长度和编码内容长度 $header = unpack('VdictLen/VcontentLen', $content); $dict = unserialize(substr($content, 8, $header['dictLen'])); $dict = array_flip($dict); $bin = substr($content, 8 + $header['dictLen']); $output = ''; $key = ''; $decodedLen = 0; $i = 0; while (isset($bin[$i]) && $decodedLen !== $header['contentLen']) { $bits = decbin(ord($bin[$i])); $bits = str_pad($bits, 8, '0', STR_PAD_LEFT); for ($j = 0; $j !== 8; $j++) { // 每拼接上 1-bit,就去与字典比对是否能解码出字符 $key .= $bits[$j]; if (isset($dict[$key])) { $output .= $dict[$key]; $key = ''; $decodedLen++; if ($decodedLen === $header['contentLen']) { break; } } } $i++; }echo $output;
3.試驗
我們將Huffman編碼Wiki頁的HTML代碼儲存到本地,進行Huffman編碼測試,試驗結果:
#編碼前: 418,504 位元組
編碼後: 280,127 位元組
空間節省了33%,如果原文的重複內容較多,Huffman編碼節省的空間可以達到50% 以上.
除了文字內容,我們再嘗試將一個二進位檔案進行Huffman編碼,例如f.lux的安裝程序,試驗結果如下:
編碼前: 770,384 位元組
編碼後: 773,076 位元組
編碼後反而佔用了更大的空間,一方面是由於我們儲存字典時,並沒有做額外的處理,佔用了不少空間。另一方面,在二進位檔案中,各個字元出現的機率相對比較平均,無法發揮Huffman編碼的優勢。
相關推薦:
以上是Huffman編碼是什麼?php中Huffman編碼與解碼的實作方法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

PHP在現代編程中仍然是一個強大且廣泛使用的工具,尤其在web開發領域。 1)PHP易用且與數據庫集成無縫,是許多開發者的首選。 2)它支持動態內容生成和麵向對象編程,適合快速創建和維護網站。 3)PHP的性能可以通過緩存和優化數據庫查詢來提升,其廣泛的社區和豐富生態系統使其在當今技術棧中仍具重要地位。

在PHP中,弱引用是通過WeakReference類實現的,不會阻止垃圾回收器回收對象。弱引用適用於緩存系統和事件監聽器等場景,需注意其不能保證對象存活,且垃圾回收可能延遲。

\_\_invoke方法允許對象像函數一樣被調用。 1.定義\_\_invoke方法使對象可被調用。 2.使用$obj(...)語法時,PHP會執行\_\_invoke方法。 3.適用於日誌記錄和計算器等場景,提高代碼靈活性和可讀性。

Fibers在PHP8.1中引入,提升了並發處理能力。 1)Fibers是一種輕量級的並發模型,類似於協程。 2)它們允許開發者手動控制任務的執行流,適合處理I/O密集型任務。 3)使用Fibers可以編寫更高效、響應性更強的代碼。

PHP社區提供了豐富的資源和支持,幫助開發者成長。 1)資源包括官方文檔、教程、博客和開源項目如Laravel和Symfony。 2)支持可以通過StackOverflow、Reddit和Slack頻道獲得。 3)開發動態可以通過關注RFC了解。 4)融入社區可以通過積極參與、貢獻代碼和學習分享來實現。

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

PHP不是在消亡,而是在不斷適應和進化。 1)PHP從1994年起經歷多次版本迭代,適應新技術趨勢。 2)目前廣泛應用於電子商務、內容管理系統等領域。 3)PHP8引入JIT編譯器等功能,提升性能和現代化。 4)使用OPcache和遵循PSR-12標準可優化性能和代碼質量。

PHP的未來將通過適應新技術趨勢和引入創新特性來實現:1)適應云計算、容器化和微服務架構,支持Docker和Kubernetes;2)引入JIT編譯器和枚舉類型,提升性能和數據處理效率;3)持續優化性能和推廣最佳實踐。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

SAP NetWeaver Server Adapter for Eclipse
將Eclipse與SAP NetWeaver應用伺服器整合。

記事本++7.3.1
好用且免費的程式碼編輯器

Dreamweaver Mac版
視覺化網頁開發工具

SublimeText3 Linux新版
SublimeText3 Linux最新版