简介

昨天刚拿到的需求，要求用二叉树设计一个huffman算法，主要用于压缩数据，就简单的用javascript实现了一个，在实现的过程中，画树进行的很顺利，但在测试编解码的时候出现了一些问题，也是自己对huffman算法的理解错误，好在及时改正。

算法实现

对huffman算法实现原理如果不了解的话最好自己去研究一下在看，否则可能有些地方看不懂，在这不做具体说明。
废话到此为止了，直接上代码，如果认为对自己有用的，请点个赞，谢谢

/**
 * 定义一个节点
 *
 * @param weight 权值
 * @param char 字符
 * */
function node(weight, char) {

    this.left = 0;//左孩子
    this.right = 0;//右孩子
    this.parent = 0;//父节点
    this.weight = weight || 0;//字符的权值
    this.char = char || '';
}

let nodes = [];
let selectStart = 0;

//
function prepareNodes() {

    const arr = [1, 2, 3, 4, 5];
    const arrChar = ['a', 'b', 'c', 'd', 'e'];
    arr.forEach(function (value, index) {
        nodes.push(new node(value, arrChar[index]));
    })
    return nodes;
}

function buildHTree(nodes) {

    selectStart = 0;
    // const nodes = prepareNodes();
    let left,//左孩子索引
        right;//右孩子

    let n = nodes.length;//外部节点数量
    let m = 2 * n - 1;//内部节点+外部节点总数量
    let HT = [];//存储节点的对象

    // console.log('n = ',n,'m = ',m,'nodes = ',nodes);
    for (let i = 0; i < m; i++) {//给所有节点一个默认权值
        HT.push(new node(0, ''));
    }
    //把叶子节点的值赋值给HT[0,n-1];
    for (let i = 0; i < n; i++) {
        HT[i].char = nodes[i].char;
        HT[i].weight = nodes[i].weight;
    }
    // console.log('HT = ',HT);
    //计算内部节点的值
    for (let i = n; i < m; i++) {
        left = selectMinWeightNode(HT, i, 0);//获取HT中权值最小的node下标
        right = selectMinWeightNode(HT, i, 1);
        // console.log('left = ',left,'right = ',right);
        HT[i].left = left || 0;
        HT[i].right = right || 0;
        HT[i].weight = HT[left].weight + HT[right].weight; //计算当前节点权值

        HT[left].parent = i;
        HT[right].parent = i;

        selectStart += 2;
    }
    return HT;
}

/**
 * 返回权值排名为rank的节点在HT中的下标（权值从小到大排列）
 *
 * @param HT 所有节点对象
 * @param rang 处理的节点范围
 * @rank left/right*/
function selectMinWeightNode(HT, rang, rank) {

    let copyNodes = [];

    for (let i = 0; i < rang; i++) {
        copyNodes.push(HT[i])
    }
    //sort  小->大
    copyNodes.sort((a, b) => a.weight - b.weight);
    //从未参与合成的节点中选出最小的值
    const targetNode = copyNodes[rank + selectStart];
    // console.log(targetNode);
    for (let i = 0; i < HT.length; i++) {
        if (targetNode === HT[i]) {
            return i;
        }
    }
    return null;
}


function huffmanCode(char, bit) {
    this.char = char;
    this.bit = bit;
}

/**
 * huffman编码
 *
 * @param HT huffman树
 * @param nodes 待编码数据*/
function encode(HT, nodes) {

    let HC = [];
    let HCStr = '';
    let bit = '';
    for (let i = 0; i < nodes.length; i++) {//遍历叶子节点
        for (let j = 0; j < HT.length; j++) {
            bit = '';
            let char = nodes[i];
            if (HT[j].char === char) {
                let nodeIndex = j;
                while (HT[nodeIndex].parent !== 0) {
                    let parentIndex = HT[nodeIndex].parent;
                    if (HT[parentIndex].left === nodeIndex) {
                        bit = '0' + bit;
                    } else {
                        bit = '1' + bit;
                    }
                    nodeIndex = parentIndex;
                }
                const code = new huffmanCode(HT[j].char, bit);
                HC.push(code);
                HCStr = HCStr+code.bit;
                break;
            }
        }
    }
    console.log(HC);
    return HCStr;
}

/**
 * huffman解码
 *
 * @param HT huffman树
 * @param ecode*/
function decode(HT, ecode) {

    let str = '';
    const bit = ecode;
    let nodeIndex = HT.length - 1;
    //遍历bit 从根节点开始遍历
    for (const c of bit) {
        if (c === '1') {//证明有右节点
            nodeIndex = HT[nodeIndex].right;
        } else {
            nodeIndex = HT[nodeIndex].left;
        }
        if (HT[nodeIndex].left === 0 && HT[nodeIndex].right === 0) {
            str += HT[nodeIndex].char;
            nodeIndex = HT.length - 1;
        }
    }
    return str;
}


function main() {

    const nodes = prepareNodes();//数据准备
    const HT = buildHTree(nodes);//建树
    const a = encode(HT,'abcdeaabcdddddbe');//编码
    // const a = decode(HT, '01001100101101001001100101010011');//解码
    console.log(a);
}

main();

测试结果

01001100101101001001100101010101001111
[ huffmanCode { char: 'a', bit: '010' },
  huffmanCode { char: 'b', bit: '011' },
  huffmanCode { char: 'c', bit: '00' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'e', bit: '11' },
  huffmanCode { char: 'a', bit: '010' },
  huffmanCode { char: 'a', bit: '010' },
  huffmanCode { char: 'b', bit: '011' },
  huffmanCode { char: 'c', bit: '00' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'b', bit: '011' },
  huffmanCode { char: 'e', bit: '11' } ]
➜  service-mqtt-backup git:(master) ✗ node huffman.js
 010 011 00 10 11 010 010 011 00 10 10 10 10 10 011 11
➜  service-mqtt-backup git:(master) ✗ 

收藏

喜欢 0