基于静态huffman编码的压缩
名词解释:哈夫曼编码(HuffmanCoding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。该方法依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码。 实现过程: 1.计算每个字符在字符串中出现的频率作为构建h
名词解释:哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。该方法依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码。
实现过程:
1.计算每个字符在字符串中出现的频率作为构建huffman树的权重
2.构建huffman树
3.建立每个字符对应的编码表
4.重建字符串编码,既压缩字符串
5.解压时根据先前的huffman树和字符位长度还原字符串
<?php /** 基于静态huffman编码的压缩[PHP语言实现] author: lajabs email: aGl0dHlvQGdtYWlsLmNvbQ== 本文以PHP作为描述语言较详细讲解huffman树原理及应用 因保证程序可读性,故不做优化. */ class huffman { /** * 压缩入口 * $str:待压缩的字符串 */ public function encode($str) { $len=strlen($str); //计算每个字符权重值(出现的频度)<这边可以做成概率表> for($i=0;$i<$len;$i++) $array[ord($str{$i})]++; $HuffmanArray=array(); asort($array); /** * 构造huffman树,时间复杂度O(nlogn) * 选择两个使用频率较小<字符在字符串中出现的次数>的结点合并生成出一个树 */ while ($item1 = each($array)) { $item2 = each($array); //构建huffman树 $this->creat_tree($item1,$item2,$array,$HuffmanArray); //反复排序<优化这步可在构造树时用插入排序算法完成> asort($array); } $HuffmanArray=array_shift($HuffmanArray); //构建编码表<这步可优化为构建树时一同生成> $tab=null; $code_tab=$this->creat_tab($HuffmanArray,$tab); //压缩&转换整个字符串为二进制表达式 $binary=null; for($i=0;$i<$len;$i++) $binary.=$tab[ord($str{$i})]; //转化为压缩后的字符串 $code=$this->encode_bin($binary); //静态huffman编码算法压缩后需保留huffman树 return array('tree'=>$HuffmanArray,'len'=>strlen($binary),'code'=>$code); } /** * 解压缩入口 * $huffman:解压所使用的huffman树 * $str:被压缩的字符 * $blen:压缩前的位长度 */ public function decode($huffman,$str,$blen) { $len=strlen($str); $binary=null; //将编码解为二进制表达式 for($i=0;$i<$len;$i++) $binary.=str_pad(base_convert(ord($str{$i}),10,2),8,'0',STR_PAD_LEFT); //去除补码 $binary=substr($binary,0,$blen); //从hufman树中配比相应的编码 return $this->decode_tree($binary,$huffman,$huffman); } /** * 将压缩后的二进制表达式再转为字符串 * $binary:二进制表达式字串 */ private function encode_bin($binary) { $len=strlen($binary); //二进制转字符需要整8位,不足8位补0 $blen=$len+8-$len%8; $binary=str_pad($binary,$blen,'0'); $encode=null; //每8位转为一个字符 for($i=7;$i<$blen;$i+=8) { $frag=substr($binary,$i-7,8); $encode.=chr(base_convert($frag,2,10)); } return $encode; } /** * 构造huffman树,使用贪婪算法选择最小的两个元素作为树的子节点 * $item1:权重最小的元素1 * $item2:权重次小的元素2 * $array:所有字符出现次数表<权重表> * $HuffmanArray:保存生成的huffman树结构 */ private function creat_tree($item1,$item2,&$array,&$HuffmanArray) { list($k,$v)=$item1; list($k2,$v2)=$item2; //假设当前树的左右节点为空节点 $c1=$k; $c2=$k2; //判断两个元素若为树则直接作为节点并入主树 if(isset($HuffmanArray[$k2])) { $c2=$HuffmanArray[$k2]; unset($HuffmanArray[$k2]); } if(isset($HuffmanArray[$k])) { $c1=$HuffmanArray[$k]; unset($HuffmanArray[$k]); } //设置树结点权值 $array[$k2]=$v+$v2; //合并节点后删除元素 unset($array[$k]); //合并到huffman树中 $HuffmanArray[$k2]=array(0=>$c1,1=>$c2); } /** * 广度优先遍历树,得到所有原字符对应的二进制表达式<01010...> * $tree:已经构建好的huffman树 * $tab:编码表,保存所有字符对应的编码 * $a0:左遍历树的路径<11010...> * $a1:右遍历树的路径 */ private function creat_tab($tree,&$tab,$a0=null,$a1=null) { if($tree==null) return; //遍历左右子树 foreach($tree as $node=>$ctree) { if(is_array($ctree)) { //判断未到达叶子节点时再向下遍历 $this->creat_tab($ctree,$tab,$a0.$node,$a1.$node); } else { //遍历到叶子节点<原字符ascii码>时的所有路径,既二进制表达式,下同 $tab[$ctree]=${'a'.$node}.$node; } } } /** * 使用进制表达式深度优先遍历树,0为左子树,1为右子树,而到根节点,即为二进制表达式所指向的原字符 * $binary:二进制表达式字串 * $huffman:huffman树 * $tree:当前所遍历的子树 * $i:指向二进制表达式字串的<指针> * $code:解码后的字符串 */ private function decode_tree($binary,$huffman,$tree,$i=0,$code=null) { $lr=$binary{$i}; //遍历完成 if($lr==null) return $code; //判断是否到根节点,根节点既为二进制表达式对应的原字符ascii码 if(is_array($tree[$lr])) { //继续向下遍历子树 return $this->decode_tree($binary,$huffman,$tree[$lr],$i+1,$code); } else { //将二进制表达式解码为原字符 $code.=chr($tree[$lr]); return $this->decode_tree($binary,$huffman,$huffman,$i+1,$code); } } } ?>
$str=' In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes". '; $huffman=new huffman(); $obj=$huffman->encode($str); echo '压缩前的编码长度:',strlen($str),"\n"; echo '压缩后的编码:',"\n"; var_dump($obj['code']); echo '解压后的字符:',$huffman->decode($obj['tree'],$obj['code'],$obj['len']);
压缩前的编码长度:587压缩后的编码:string(330) "sp閉h颚?6鵞+王d挓吷s霒zk洚磗脎|t?*?;娳9蹴??>楏4O3 5 F凣rRuJ解压后的字符:In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Dengan pemampatan memori pada Windows 11, peranti anda akan tercekik walaupun dengan jumlah RAM yang terhad. Dalam artikel ini, kami akan menunjukkan kepada anda cara mendayakan atau melumpuhkan pemampatan memori pada Windows 11. Apakah pemampatan memori? Pemampatan memori ialah ciri yang memampatkan data sebelum menulisnya ke RAM, sekali gus menyediakan lebih banyak ruang storan padanya. Sudah tentu, lebih banyak data yang disimpan dalam memori fizikal diterjemahkan kepada operasi sistem yang lebih pantas dan prestasi keseluruhan yang lebih baik. Ciri ini didayakan secara lalai dalam Windows 11, tetapi jika ia tidak aktif entah bagaimana, anda boleh melumpuhkan atau mendayakannya semula. Bagaimana untuk membolehkan pemampatan memori dalam Windows 11? Klik bar carian, taip powershell dan klik

Saya mendapati bahawa pakej termampat yang dimuat turun dari laman web muat turun tertentu akan lebih besar daripada pakej termampat asal selepas penyahmampatan Perbezaannya ialah berpuluh-puluh Kb dan berpuluh-puluh Mb jika fail kecil, jika terdapat banyak fail, kos penyimpanan akan meningkat dengan banyak. Saya telah membuat beberapa kajian mengenainya dan boleh belajar daripadanya jika perlu. Tahap mampatan: 9-mampatan melampau Saiz kamus: 256 atau 384, semakin dimampatkan kamus, semakin perlahan perbezaan kadar mampatan lebih besar sebelum 256MB dan tiada perbezaan dalam kadar mampatan selepas 384MB: maksimum 273 Parameter: f=BCJ2, uji dan tambah kadar mampatan parameter akan lebih tinggi

Model bahasa besar (LLM) mempunyai keupayaan untuk menghasilkan teks yang lancar dan koheren, membawa prospek baharu ke bidang seperti perbualan kecerdasan buatan dan penulisan kreatif. Walau bagaimanapun, LLM juga mempunyai beberapa had utama. Pertama, pengetahuan mereka terhad kepada corak yang diiktiraf daripada data latihan, kurang pemahaman sebenar tentang dunia. Kedua, kemahiran menaakul adalah terhad dan tidak boleh membuat inferens logik atau menggabungkan fakta daripada pelbagai sumber data. Apabila berhadapan dengan soalan yang lebih kompleks dan terbuka, jawapan LLM mungkin menjadi tidak masuk akal atau bercanggah, dikenali sebagai "ilusi." Oleh itu, walaupun LLM sangat berguna dalam beberapa aspek, ia masih mempunyai had tertentu apabila berhadapan dengan masalah kompleks dan situasi dunia sebenar. Untuk merapatkan jurang ini, sistem penjanaan dipertingkatkan semula (RAG) telah muncul dalam beberapa tahun kebelakangan ini

Ramai rakan perlu merakam skrin untuk kerja pejabat atau memindahkan fail, tetapi kadangkala masalah fail yang terlalu besar menyebabkan banyak masalah berikut adalah penyelesaian kepada masalah fail yang terlalu besar, mari kita lihat. Apa yang perlu dilakukan jika fail rakaman skrin win10 terlalu besar: 1. Muat turun perisian Format Factory untuk memampatkan fail. Alamat muat turun >> 2. Masukkan halaman utama dan klik pilihan "Video-MP4". 3. Klik "Tambah Fail" pada halaman format penukaran dan pilih fail MP4 untuk dimampatkan. 4. Klik "Konfigurasi Output" pada halaman untuk memampatkan fail mengikut kualiti output. 5. Pilih "Kualiti dan Saiz Rendah" daripada senarai konfigurasi juntai bawah dan klik "OK". 6. Klik "OK" untuk melengkapkan import fail video. 7. Klik "Mula" untuk memulakan penukaran. 8. Selepas selesai, anda boleh

Kaedah pengekodan biasa termasuk pengekodan ASCII, pengekodan Unikod, pengekodan UTF-8, pengekodan UTF-16, pengekodan GBK, dsb. Pengenalan terperinci: 1. Pengekodan ASCII ialah standard pengekodan aksara yang paling awal, menggunakan nombor perduaan 7-bit untuk mewakili 128 aksara, termasuk huruf Inggeris, nombor, tanda baca, aksara kawalan, dsb. 2. Pengekodan Unikod ialah kaedah yang digunakan untuk mewakili semua aksara di dunia Kaedah pengekodan standard aksara, yang memberikan titik kod digital yang unik kepada setiap aksara 3. Pengekodan UTF-8, dsb.

Analisis mendalam tentang peranan dan penggunaan kata kunci statik dalam bahasa C Dalam bahasa C, statik ialah kata kunci yang sangat penting, yang boleh digunakan dalam definisi fungsi, pembolehubah dan jenis data. Menggunakan kata kunci statik boleh menukar atribut pautan, skop dan kitaran hayat objek Mari analisa peranan dan penggunaan kata kunci statik dalam bahasa C secara terperinci. Pembolehubah statik dan fungsi: Pembolehubah yang ditakrifkan menggunakan kata kunci statik di dalam fungsi dipanggil pembolehubah statik, yang mempunyai kitaran hayat global

Pekerja pejabat menggunakan perisian wps dengan kerap di tempat kerja Kadangkala mereka memasukkan berbilang fail setiap hari dan kemudian menghantarnya kepada ketua atau ke lokasi yang ditetapkan Jadi bagaimana perisian wps memampatkan folder dan membungkusnya untuk dihantar? Langkah operasi ini. Mula-mula, susun fail dan folder yang ingin anda hantar ke dalam folder yang sama. Jika anda mempunyai banyak fail, adalah idea yang baik untuk menamakan setiap fail supaya lebih mudah untuk dikenal pasti semasa menghantar. Langkah kedua, kali ini klik pada folder besar ini dan kemudian klik kanan. Pilih "Tambah ke arkib". Langkah 3: Pada masa ini, perisian akan membantu kami membungkus fail kami secara automatik Pilih "Mampatkan ke XX.zip ini ialah format pembungkusan, dan kemudian klik Mampatkan Sekarang". ,

Pembungkusan dan pemampatan adalah operasi yang biasa digunakan di Linux, tetapi ramai pengguna cenderung untuk mengelirukan kedua-dua konsep. Artikel ini akan membincangkan perbezaan antara pembungkusan dan pemampatan dalam sistem Linux secara terperinci, dan menggunakan contoh kod khusus untuk membantu pembaca memahami dengan lebih baik. Pertama, kita perlu menjelaskan perbezaan antara pembungkusan dan pemampatan. Pembungkusan ialah gabungan berbilang fail atau direktori ke dalam satu fail, selalunya digunakan untuk menyusun, mengarkibkan atau memindahkan fail. Mampatan adalah untuk memampatkan satu atau lebih fail melalui algoritma untuk mengurangkan saiz fail, menjimatkan ruang storan atau mempercepatkan penghantaran.
