重启数据结构与算法10

[Ray-56]

重启数据结构与算法10

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

1. 重启数据结构与算法1
2. 重启数据结构与算法2
3. 重启数据结构与算法3
4. 重启数据结构与算法4
5. 重启数据结构与算法5
6. 重启数据结构与算法6
7. 重启数据结构与算法7
8. 重启数据结构与算法8
9. 重启数据结构与算法9
10. 重启数据结构与算法10
11. 重启数据结构与算法11
12. 重启数据结构与算法12

赫夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度(WPL)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

type NodeType = Node | null;
class Node {
    public value: number;
    public left: NodeType = null;
    public right: NodeType = null;
    constructor(value: number) {
        this.value = value;
    }
    public toString(): string {
        return `{value: ${this.value}}`;
    }
    public preOrder() {
        console.log(this.toString());
        this.left?.preOrder();
        this.right?.preOrder();
    }
}

function createHuffmanTree(arr: number[]) {
    // 排序后构建为 Node 数组
    const nodes = arr.map<Node>(i => new Node(i));

    while (nodes.length > 1) {
        // 重新排序
        nodes.sort((a, b) => a.value - b.value);
        // 取最小权
        const left = nodes.shift() as Node;
        // 取第二小权
        const right = nodes.shift() as Node;
        // 构建新树
        const parent = new Node(left!.value + right!.value);
        parent.left = left;
        parent.right = right;
        // 加入 nodes
        nodes.push(parent);
    }
    return nodes[0];
}

window.onload = function main() {
    const arr = [13, 7, 8, 3, 29, 6, 1];
    const root = createHuffmanTree(arr);
    root.preOrder();
    // 前序遍历输出：
    // {value: 67}
    // {value: 29}
    // {value: 38}
    // {value: 15}
    // {value: 7}
    // {value: 8}
    // {value: 23}
    // {value: 10}
    // {value: 4}
    // {value: 1}
    // {value: 3}
    // {value: 6}
    // {value: 13}
}

赫夫曼编码

这里进行了公司的技术分享使用了 Node.js 实现，和老师的有一点区别，Deno 版本的代码也在，只是还有点问题，后面有时间排查解决一下

class Node {
    constructor(value, weight) {
        this.weight = weight;
        // 字符的 Unicode 编码 `'str'.charCodeAt();`
        // 为 null 时表示非叶子节点
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function strToBytes(str) {
    const buffer = Buffer.from(str);

    return [...buffer];
}

function getNodes(bytes) {
    const nodes = [];
    const map = {};

    for (let b of bytes) {
        if (!map[b]) {
            map[b] = 1;
        } else {
            map[b]++;
        }
    }

    for (let [c, weight] of Object.entries(map)) {
        nodes.push(new Node(c, weight));
    }
    return nodes;
}

function createHuffmanTree(nodes) {
    while (nodes.length > 1) {
        nodes.sort((a, b) => a.weight - b.weight);
        const left = nodes.shift();
        const right = nodes.shift();
        const parent = new Node(null, left.weight + right.weight);
        parent.left = left;
        parent.right = right;
        nodes.push(parent);
    }

    return nodes[0];
}

function createHuffmanCodes(root) {
    const huffmanCodes = {};
    function getCodes(node, code = '', path = '') {
        if (!node) return;
        path += code;
        if (node.value === null) {
            getCodes(node.left, '0', path);
            getCodes(node.right, '1', path);
            return;
        }
        huffmanCodes[node.value] = path;
    }
    getCodes(root);
    return huffmanCodes;
}

function encode(bytes, huffmanCodes) {
    let i = 0;
    let ret = '';
    while (bytes[i]) {
        ret += huffmanCodes[bytes[i++]];
    }
    return ret;
}

function huffmanEncode(str) {
    const bytes = strToBytes(str);
    const nodes = getNodes(bytes);
    const huffmanTree = createHuffmanTree(nodes);
    huffmanCodes = createHuffmanCodes(huffmanTree);
    const encodeStr = encode(bytes, huffmanCodes);
    return encodeStr;
}

function reverseMap(o) {
    return Object.keys(o).reduce(
        (r, k) => Object.assign(r, { [o[k]]: k }),
        {}
    );
}

function huffmanDecode(encode, huffmanCodes) {
    // let i = 0;
    // let ret = '';
    // const map = reverseMap(huffmanCodes);
    var i = 0;
    var result = '';
    var data = '';
    var map = reverseMap(huffmanCodes);
    var str = encode;


    while(str) {
        result += str[i++];
        if (result in map) {
            data += String.fromCharCode(map[result]);
            str = str.replace(new RegExp("^"+result),'');
            result = '';
            i = 0;
        }
    }
    console.log('data >>>', data);
}

/************ 分割线 ***************/
let huffmanCodes;
const str = 'hello world alsdjfaljsdfjasdf';
const encodeStr = huffmanEncode(str);
console.log('encode:' + encodeStr);
huffmanDecode(encodeStr, huffmanCodes);

下期预告

• 二叉排序树