ハフマンの木のjsが実現しました.

前言
ハフマンツリーはデータ圧縮符号化アルゴリズムの基礎であり、本論文ではJavaScript言語を用いてこのアルゴリズムを実現した.アルゴリズムの流れ:符号化される文字列を入力して、アルゴリズムでハフマンツリーを構成し、文字列のバイナリ圧縮符号化を実現します.
ハフマン理論の勉強には、他の文章を参照してください.本明細書は、実装されたコードおよび注釈のみを含む.コメントが豊富で、理解しにくいと信じています.
アルゴリズム
ツリーノード
ツリーデータ構造である以上、ツリーノードが必要です.以下はツリーノード定義です.

class Node {  
    constructor(value, char, left, right) {  
        this.val = value; //         
        this.char = char; //        
        this.left = left;  
        this.right = right;  
    }  
}

一般的には、ノードはval、left、rightだけが必要です.ここにcharフィールドを追加して、ノードは符号化される文字列の中のどの文字を表していますか?
コアコード
構造関数

class huffmanTree{ 
    constructor(str){  
        //    ，          
        let hash = {};  
        for(let i = 0; i < str.length; i++){  
            hash[str[i]] = ~~hash[str[i]] + 1;  
        }  
        this.hash = hash;  
  
        //    ，        
        this.huffmanTree = this.getHuffmanTree();  
  
        //    ，      ，     
        let map = this.getHuffmanCode(this.huffmanTree);  
        //      ，                
        console.log(map);  
  
        //    ，       ，            
        this.binaryStr = this.getBinaryStr(map, str);  
    } 
}

次に私達は一つずつ見てみます.(1)ハフマンの木を作る過程、(2)ハフマンの木を遍歴して符号表を取得する過程、および(3)最終二進法の串を返す過程です.
構造ハフマンの木

    //         
    getHuffmanTree(){  
        //           node.val,       
        let forest = []  
        for(let char in this.hash){  
            let node = new Node(this.hash[char], char); 
            forest.push(node);  
        }  
  
        let allNodes = []; //         ，                 ，  .left .right         
        //            ，        ，     
        while(forest.length !== 1){  
            //             ，     
            forest.sort((a, b) => {  
                return a.val - b.val;  
            });  
  
            let node = new Node(forest[0].val + forest[1].val, '');  
            allNodes.push(forest[0]);  
            allNodes.push(forest[1]);  
            node.left = allNodes[allNodes.length - 2]; //            
            node.right = allNodes[allNodes.length - 1]; //            
  
            //           
            forest = forest.slice(2);  
            //         
            forest.push(node);  
        }  
  
        //        ，      ，        
        return forest[0];  
    } 

ハフマンを経て、コード表に戻ります.

    //       ，                        
    getHuffmanCode(tree){  
        let hash = {};  //    
        let traversal = (node, curPath) => {  
            if (!node.length && !node.right) return;  
            if (node.left && !node.left.left && !node.left.right){  
                hash[node.left.char] = curPath + '0';  
            }  
            if (node.right && !node.right.left && !node.right.right){  
                hash[node.right.char] = curPath + '1';  
            }  
            //     ，   0  
            if(node.left){  
                traversal(node.left, curPath + '0');  
            }  
            //     ，   1  
            if(node.right){  
                traversal(node.right, curPath + '1');  
            }  
        };  
        traversal(tree, '');  
        return hash;  
    }  

符号列を返します

    //                
    getBinaryStr(map, originStr){  
        let result = '';  
        for(let i = 0; i < originStr.length; i++){  
            result += map[originStr[i]];  
        }  
        return result;  
    }  

コードのまとめ

//                                
class huffmanTree{  
    constructor(str){  
        //    ，          
        let hash = {};  
        for(let i = 0; i < str.length; i++){  
            hash[str[i]] = ~~hash[str[i]] + 1;  
        }  
        this.hash = hash;  
  
        //         
        this.huffmanTree = this.getHuffmanTree();  
  
        let map = this.getHuffmanCode(this.huffmanTree);  
        //      ，                
        console.log(map);  
  
        //           
        this.binaryStr = this.getBinaryStr(map, str);  
    }  
  
    //         
    getHuffmanTree(){  
        //           node.val,       
        let forest = []  
        for(let char in this.hash){  
            let node = new Node(this.hash[char], char); 
            forest.push(node);  
        }  
  
        //            ，        ，       
        let allNodes = []; //         ，                 ，  .left .right         
        while(forest.length !== 1){  
            //             ，     
            forest.sort((a, b) => {  
                return a.val - b.val;  
            });  
  
            let node = new Node(forest[0].val + forest[1].val, '');  
            allNodes.push(forest[0]);  
            allNodes.push(forest[1]);  
            node.left = allNodes[allNodes.length - 2]; //            
            node.right = allNodes[allNodes.length - 1]; //            
  
            //           
            forest = forest.slice(2);  
            //         
            forest.push(node);  
        }  
  
        //          
        return forest[0];  
    }  
  
    //       ，                        
    getHuffmanCode(tree){  
        let hash = {};  //    
        let traversal = (node, curPath) => {  
            if (!node.length && !node.right) return;  
            if (node.left && !node.left.left && !node.left.right){  
                hash[node.left.char] = curPath + '0';  
            }  
            if (node.right && !node.right.left && !node.right.right){  
                hash[node.right.char] = curPath + '1';  
            }  
            //     ，   0  
            if(node.left){  
                traversal(node.left, curPath + '0');  
            }  
            //     ，   1  
            if(node.right){  
                traversal(node.right, curPath + '1');  
            }  
        };  
        traversal(tree, '');  
        return hash;  
    }  
  
    //                
    getBinaryStr(map, originStr){  
        let result = '';  
        for(let i = 0; i < originStr.length; i++){  
            result += map[originStr[i]];  
        }  
        return result;  
    }  
}

テストコード

let tree = new huffmanTree('ABBCCCDDDDEEEEE')  
console.log(tree)

エンコーディング対照表:{C:'00',A:'010',B:'011',D:'10',E:'11''の最終エンコーディング結果:01010101010101100000 101111111
おわりに
フロントエンドのアルゴリズムライブラリ:https://github.com/cunzaizhuy...ここでは、私が書いた500近いLeetCodeの問題を記録しています.前端の同行者に仕事の面接をしたり、アルゴリズムの内功を修練したりするのに役立ちます.