霍夫曼编码约定

Question

是否有为特定字母表生成霍夫曼编码的约定？看起来生成的编码取决于您是将“0”分配给左侧 child 还是右侧 child 以及您如何确定哪个符号将进入左侧树。

Wikipedia 表示：

As a common convention, bit '0' represents following the left child and bit '1' represents following the right child.

所以这是前半部分方差的答案。但是，我找不到下半场的任何惯例。我会假设一些事情，比如让概率较低的节点在左边，但几个在线霍夫曼树示例不会这样做。

例如：

那么左右节点的分配有没有约定俗成的，还是要看实现？

如果这是重复的，我深表歉意，但我找不到答案。

Answer 1

是的，事实上是有的。与其说是互操作性约定，不如说是编码效率约定。称为Canonical Huffman，其中代码按从最短代码到最长代码的数字顺序分配，并且在单个代码长度内，它们在符号上按字典顺序分配。这允许只传输每个符号的代码长度，而不是整个树结构。

一般做的只是用哈夫曼算法树来确定每个符号的比特数。然后树被丢弃。位值永远不会分配给分支。然后使用上面的顺序直接根据长度构建代码。

Answer 2

看看

        class Nodo{
      constructor(v=null,f=null,l=null,r=null){
            this.f=f
            this.v=v
            this.l=l
            this.r=r
          }
      }
        function EnCrypt(text){
            let lista=[]
            for(let i=0;i<text.length;i++){//Create the list with the appearances 
                !lista.find(e => e.v===text[i]) && lista.push(new Nodo(text[i],(text.match(new RegExp(text[i],"g")) || []).length))
            }
            lista=lista.sort((a,b)=>a.f-b.f)//Order from smallest to largest
            //----------------------------------------------------
            function createNew(){//Create the tree
                let nodos=lista.splice(0,2)
                lista.push(new Nodo(null,nodos[0].f+nodos[1].f,nodos[0],nodos[1]))
                if(lista.length==1)return lista
                createNew()
            }createNew()
          ///-----------------------------------------------
            let Arbol=lista[0]
            function Codigo(nodo,c=""){//recursively traverse the tree 
                if(!nodo.l && !nodo.r)return [nodo.v,c]
                return Codigo(nodo.l,c+"0")+";"+Codigo(nodo.r,c+"1")
            }
           //-----------------------------------------------
            const codigo=(Codigo(Arbol)).split(";")
            let finish=""
            text.split("").map(t=>{
                codigo.map(e => {
                    if(e.split(",")[0]==t)finish+=e.split(",")[1]
                })
            })
            return {
                cod:finish,
                dicc:codigo
            }
        }
        function DeCrypt(key,res=""){
            let {cod,dicc}=key
            let temp=""
            for(let i=0;i<=cod.length;i++){
                temp+=cod.substr(i,1)
               dicc.map((d)=>{
                    d=d.split(",")
                    if(temp==d[1]){
                        res+=d[0]
                        temp=""
                        cod=cod.substr(i)
                        i=0
                    }
                })
            }
            return res
        }
        function Huffman(){
                const text=document.querySelector("#newValue").value
                const comp= EnCrypt(text)
                document.querySelector(".res").innerHTML=JSON.stringify(comp,null, 4)
            }
        function HuffmanDecode(){
                const text=JSON.parse(document.querySelector("#huffman").value)
                const comp= DeCrypt(text)
                document.querySelector(".res2").innerHTML=comp
            }

<h1></h1>
<input type="text"
       placeholder="set value (min 2 chars)" id="newValue">
<button onclick="Huffman()">Go</button>
<div class="res" style="white-space: pre-wrap;"></div>

<input type="text" placeholder="paste the result from above" id="huffman"><button onclick="HuffmanDecode()">decode</button>
 <div class="res2" style="white-space: pre-wrap;"></div>

霍夫曼编码约定

Convention for Huffman Coding

huffman-code