哈夫曼编码原理

发布网友 发布时间：2022-04-22 09:43

我来回答

共3个回答

懂视网 时间：2022-04-23 07:06

这次给大家带来源生js实现哈夫曼编码步骤详解，源生js实现哈夫曼编码的注意事项有哪些，下面就是实战案例，一起来看一下。

原始版

function cal(str) {
 if (typeof str !== 'string' || str.length < 1) {
 return;
 }
 var map = {};
 var i = 0;
 while(str[i]) {
 map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);
 i++;
 }
 return map;
}
function sort(map) {
 map = map || {};
 var result = [];
 for (key in map) {
 if(map.hasOwnProperty(key)) {
 var obj = {
 key: key,
 val: map[key]
 };
 result.push(new Node(null, null, obj));
 }
 }
 return result.sort(function(x,y){return x.data.val > y.data.val});
}
function Node(left, right, data) {
 this.left = left;
 this.right = right;
 this.data = data;
}
function makeTree(table) {
 var i = 0;
 var len = table.length;
 var node1;
 var node2;
 var parentNode;
 while(table.length > 1) {
 parentNode = new Node(table[i], table[i+1], {key: null, val: table[i]['data'].val + table[i+1]['data'].val});
 table.splice(i,2);
 table.unshift(parentNode);
 table.sort(function(x,y){return x.data.val > y.data.val});
 }
 return table;
}
function encode(str, ret) {
 if (typeof str !== 'string' || str.length < 1) {
 return;
 }
 var i = 0;
 var result = '';
 while(str[i]) {
 result += ret[str[i++]];
 }
 return result
}
function reverseRet(ret) {
 var result = {};
 for (key in ret) {
 if(ret.hasOwnProperty(key)) {
 result[ret[key]] = key;
 }
 }
 return result;
}
function decode(str, ret) {
 var i = 0;
 var result = '';
 var data = '';
 var map = reverseRet(ret);
 while(str) {
 result += str[i++];
 if (result in map) {
 data += map[result];
 str = str.replace(new RegExp("^"+result),'');
 result = '';
 i = 0;
 }
 }
 console.log(data)
}
function traversal(tree, code, ret) {
 if (tree.left !== null) {
 traversal(tree.left, code + '0', ret);
 } else {
 ret[tree.data.key] = code;
 }
 if (tree.right !== null) {
 traversal(tree.right,code + '1', ret);
 } else {
 ret[tree.data.key] = code;
 }
}
var ret = {};
var str = 'ew qew qd ef 24 gf ewr getElementsByTagName';
traversal(makeTree(sort(cal(str)))[0],'', ret)
decode(encode(str, ret), ret)
btoa(encode(str,ret))

修改版

function Huffman(str) {
 // 需要编码的字符串
 this.str = str;
 // 键和频率映射表
 this.keyCountMap = null;
 // 编码和键的映射表
 this.codeKeyMap = {};
 // 键和编码的映射表
 this.keyCodeMap = {};
 // 哈夫曼树节点列表
 this.nodeList = null;
 // 哈夫曼树根节点
 this.root = null;
 // 哈夫曼编码后的01序列
 this.code = null;
}
Huffman.prototype.cal = function cal() {
 str = this.str;
 var map = {};
 var i = 0;
 while(str[i]) {
 map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);
 i++;
 }
 this.keyCountMap = map;
}
Huffman.prototype.sort = function sort() {
 map = this.keyCountMap;
 var result = [];
 for (key in map) {
 if(map.hasOwnProperty(key)) {
 var obj = {
 key: key,
 val: map[key]
 };
 result.push(new Node(null, null, obj));
 }
 }
 this.nodeList = result.sort(function(x,y){return x.data.val > y.data.val});
}
function Node(left, right, data) {
 this.left = left;
 this.right = right;
 this.data = data;
}
Huffman.prototype.makeTree = function makeTree() {
 var i = 0;
 var len = this.nodeList.length;
 var node1;
 var node2;
 var parentNode;
 var table = this.nodeList;
 while(table.length > 1) {
 parentNode = new Node(table[i], table[i+1], {key: null, val: table[i]['data'].val + table[i+1]['data'].val});
 table.splice(i,2);
 table.unshift(parentNode);
 table.sort(function(x,y){return x.data.val > y.data.val});
 }
 this.root = table[0] || new Node();
 return this.root;
}
Huffman.prototype.traversal = function traversal(tree, code) {
 if (tree.left !== null) {
 traversal.call(this,tree.left, code + '0');
 } else {
 this.keyCodeMap[tree.data.key] = code;
 }
 if (tree.right !== null) {
 traversal.call(this, tree.right,code + '1');
 } else {
 this.keyCodeMap[tree.data.key] = code;
 }
}
Huffman.prototype.encode = function encode() {
 this.cal();
 this.sort();
 var root = this.makeTree();
 this.traversal(root, '');
 var ret = this.keyCodeMap;
 var i = 0;
 var result = '';
 var str = this.str;
 while(str[i]) {
 result += ret[str[i++]];
 }
 this.code = result;
 console.log('encode:' + result);
 return result
}
Huffman.prototype.reverseMap = function reverseMap() {
 var ret = this.keyCodeMap;
 var result = {};
 for (key in ret) {
 if(ret.hasOwnProperty(key)) {
 result[ret[key]] = key;
 }
 }
 this.codeKeyMap = result;
 return result;
}
Huffman.prototype.decode = function decode() {
 var i = 0;
 var result = '';
 var data = '';
 var map = this.reverseMap();
 var str = this.code;
 while(str) {
 result += str[i++];
 if (result in map) {
 data += map[result];
 str = str.replace(new RegExp("^"+result),'');
 result = '';
 i = 0;
 }
 }
 console.log("decode:" + data)
}
Huffman.prototype.encodeBase64 = function() {
 try {
 var base64 = btoa(this.code);
 return base64;
 } catch(e) {
 return '';
 }
}
var str = 'ew qew qd ef 24 gf ewr getElementsByTagName';
var huffman = new Huffman(str)
huffman.encode(str)
huffman.decode();
huffman.encodeBase64();

相信看了本文案例你已经掌握了方法，更多精彩请关注Gxl网其它相关文章！

推荐阅读：

nodejs读取去重excel步骤详解

js与typescript中class使用详解

热心网友 时间：2022-04-23 04:14

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。

扩展资料

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率
和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相
加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，
将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。

例如a7从左至右，由U至U″″，其码字为1000；

a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…

用赫夫曼编码所得的平均比特率为：Σ码长×出现概率

上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵为2.61bit，二者已经是很接近了。

参考资料来源：百度百科-哈夫曼编码

热心网友 时间：2022-04-23 05:48

霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：
（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
以下这个简单例子说明了这一过程。
1)．字母A,B,C,D,E已被编码，相应的出现概率如下：
p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11
2)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的哈夫曼编码可能由相同的数据产生。
3)．各节点相应的概率如下：
p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13
D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。
如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。
4)．剩下节点的概率如下：
p(AD)=0.29, p(B)=0.51, p(CE)=0.20
AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。
5)．剩下两个节点相应的概率如下：
p(ADCE)=0.49, p(B)=0.51
它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。
6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中：
w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010

图03-02-2 霍夫曼编码例
霍夫曼编码器的编码过程可用例子演示和解释。
下面是另一个霍夫曼编码例子。假定要编码的文本是：
"EXAMPLE OF HUFFMAN CODE"
首先，计算文本中符号出现的概率（表03-02-2）。
表03-02-2 符号在文本中出现的概率
符号
概率

E
2/25

X
1/25

A
2/25

M
2/25

P
1/25

L
1/25

O
2/25

F
2/25

H
1/25

U
1/25

C
1/25

D
1/25

I
1/25

N
2/25

G
1/25

空格
3/25

最后得到图03-02-3所示的编码树。

图03-02-3 霍夫曼编码树
在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive Huffman code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号。
同香农-范诺编码一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是因为这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。
采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error propagation)。计算机对这种错误也*为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。