哈夫曼树
一、认识
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。
相关名词：
-
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径
-
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1
-
结点的权: 给每一个结点赋予一个新的数值，被称为这个结点的权
-
结点的带权路径长度: 指的是从根结点到该结点之间的路径长度与该结点的权的乘积
-
WPL: 树的带权路径 长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL”
特点：
- 赫夫曼树时带权路径长度最短的树，权值较大的节点离根较近
哈夫曼树
对于 [5,29,7,8,14,23,3,11] 数组，我们把它构造成赫夫曼树:
-
创建节点类，这些值作为节点的权值，存储在集合里
-
将这些节点按照权值的大小进行排序
-
取出权值最小的两个节点，并创建一个新的节点作为这两个节点的父节点，这个父节点的权值为两个子节点的权值之和。将这两个节点分别赋给父节点的左右节点
-
删除这两个节点，将父节点添加进集合里
-
重复第二步到第四步，直到集合中只剩一个元素，结束循环
:::details 点击查看代码
class Node {
data;
left = null;
right = null;
parent = null;
constructor(data) {
this.data = data;
}
}
class HuffmanTree {
root=null;
create(array) {
const nodeList = array.map((item) => new Node(item));
this.sort(nodeList, 0, nodeList.length - 1, "data");
while (nodeList.length > 1) {
const leftNode = nodeList.shift();
const rightNode = nodeList.shift();
const parentNode = new Node(leftNode.data + rightNode.data);
parentNode.left = leftNode;
leftNode.parent = parentNode;
parentNode.right = rightNode;
rightNode.parent = parentNode;
nodeList.push(parentNode);
this.sort(nodeList, 0, nodeList.length - 1, "data");
}
return this.root=nodeList[0];
}
sort(array, start, end, fieldName) {
let list = [[start, end]];
while (list.length > 0) {
let currentRange = list.pop();
if (currentRange[0] >= currentRange[1]) {
continue;
}
let pivot = array[currentRange[0]];
let left = currentRange[0];
let right = currentRange[1];
while (left < right) {
while (
left < right &&
array[right][fieldName] > pivot[fieldName]
) {
right--;
}
while (
left < right &&
array[left][fieldName] <= pivot[fieldName]
) {
left++;
}
[array[left], array[right]] = [array[right], array[left]];
}
[array[currentRange[0]], array[left]] = [
array[left],
array[currentRange[0]],
];
if (currentRange[0] < right) {
list.push([currentRange[0], left - 1]);
}
if (currentRange[1] > left) {
list.push([right + 1, currentRange[1]]);
}
}
}
preOrder(){
const result=[];
const stack=[];
let currentNode=this.root;
while(currentNode||stack.length){
while(currentNode){
result.push(currentNode.data)
stack.push(currentNode);
currentNode=currentNode.left;
}
currentNode=stack.pop();
currentNode=currentNode.right;
}
return result
}
}
const array = [5, 29, 7, 8, 14, 3, 11, 20];
const huffmanTree = new HuffmanTree();
huffmanTree.create(array);
console.log(huffmanTree.preOrder());
:::
哈夫曼编码
- 传送的字符串为 More Worker More Lucky ，进行数据压缩处理
- 记录各个字符出现的次数
- 通过各个字符出现的次数构建哈夫曼树，次数作为权值
- 构建哈夫曼树
- 根据哈夫曼树，给各个字符规定编码（前缀编码），向左的路径为0 ，向右的路径为1
- 通过上述步骤，得出 More Worker More Lucky 的无损编码压缩
:::details 点击查看代码
class Node {
ch;
weight;
left = null;
right = null;
parent = null;
constructor(weight, ch) {
this.weight = weight;
this.ch = ch;
}
}
class HuffmanTree {
str;
root = null;
codeMap = {};
reverseCodeMap = {};
constructor(str) {
this.str = str;
this.getCodeMap(str);
this.getReverseCodeMap();
}
getChFrequency(str) {
const result = [];
const chMap = {};
for (let i = 0; i < str.length; i++) {
if (chMap[str[i]]) {
chMap[str[i]]++;
} else {
chMap[str[i]] = 1;
}
}
Object.keys(chMap).forEach((key) => {
result.push({ ch: key, weight: chMap[key] });
});
return result;
}
create(array) {
const nodeList = array.map((item) => new Node(item.weight, item.ch));
this.sort(nodeList, 0, nodeList.length - 1, "weight");
while (nodeList.length > 1) {
const parentNode = new Node(
nodeList[0].weight + nodeList[1].weight,
""
);
parentNode.left = nodeList.shift();
parentNode.right = nodeList.shift();
parentNode.left.parent = parentNode;
parentNode.right.parent = parentNode;
nodeList.push(parentNode);
this.sort(nodeList, 0, nodeList.length - 1, "weight");
}
this.root = nodeList[0];
}
sort(array, start, end, fieldName) {
let list = [[start, end]];
while (list.length > 0) {
let currentRange = list.pop();
if (currentRange[0] >= currentRange[1]) {
continue;
}
let pivot = array[currentRange[0]];
let left = currentRange[0];
let right = currentRange[1];
while (left < right) {
while (
left < right &&
array[right][fieldName] > pivot[fieldName]
) {
right--;
}
while (
left < right &&
array[left][fieldName] <= pivot[fieldName]
) {
left++;
}
[array[left], array[right]] = [array[right], array[left]];
}
[array[currentRange[0]], array[left]] = [
array[left],
array[currentRange[0]],
];
if (currentRange[0] < right) {
list.push([currentRange[0], left - 1]);
}
if (currentRange[1] > left) {
list.push([right + 1, currentRange[1]]);
}
}
}
getCodeMap(str) {
const codeMap = {};
const array = this.getChFrequency(str);
this.create(array);
const traversal = (node, currentCode) => {
if (!node) return;
if (node.ch) {
codeMap[node.ch] = currentCode;
}
if (node.left) {
traversal(node.left, currentCode + "0");
}
if (node.right) {
traversal(node.right, currentCode + "1");
}
};
traversal(this.root, "");
this.codeMap = codeMap;
}
getReverseCodeMap() {
const result = {};
for (let key in this.codeMap) {
result[this.codeMap[key]] = key;
}
this.reverseCodeMap = result;
}
enCode() {
let result = "";
for (let i = 0; i < this.str.length; i++) {
result += this.codeMap[this.str[i]];
}
return result;
}
deCode(code) {
let i = 0;
let current = "";
let result = "";
let str = code;
while (str) {
current += str[i++];
if (current in this.reverseCodeMap) {
result += this.reverseCodeMap[current];
str = str.replace(new RegExp("^" + current), "");
current = "";
i = 0;
}
}
return result;
}
}
const str = "More Worker More Lucky";
const huffmanTree = new HuffmanTree(str);
const code = huffmanTree.enCode();
console.log(code);
console.log(huffmanTree.deCode(code));
:::