霍夫曼编码规范

Question

有没有一种生成某个字母表的哈夫曼编码的约定？似乎结果编码取决于您将'0'分配给左子树还是右子树以及如何确定哪个符号将进入左树。

Wikipedia说：

作为一个常见的约定，位'0'表示遵循左孩子，位'1'表示遵循右孩子。

所以这是对第一半差异的回答。然而，我找不到第二半的任何约定。我会假设像使具有较低概率的节点进入左侧之类的事情，但是在线上有几个示例Huffman树不这样做。

例如:

那么，节点分配到左侧和右侧是否有惯例，还是由实现决定？如果这是一个重复的问题，我很抱歉，但我找不到答案。

- andars

---

我认为唯一的“惯例”就是我们选择作为“标准”的算法，例如gzip。 - Jonathon Reinhart

在这种情况下，有关系吗？ 会有一种情况选择其中一种会产生比选择另一种更低效的代码吗？（也许这应该是一个新问题） - andars

Answer 1

实际上是有的，虽然不是为了互操作性而制定的，而是为了编码效率。它被称为规范哈夫曼编码，其中代码按照从最短代码到最长代码的数字顺序分配，并且在单个代码长度内，它们按符号的词典顺序分配。这使得只需传输每个符号的代码长度，而不是整个树结构。

通常所做的是仅使用Huffman算法树确定每个符号的位数。然后丢弃树。永远不会将位值分配给分支。然后直接从长度构建代码，使用上述排序。

- Mark Adler

---

有道理。谢谢。 - andars

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>

- David190

---

感谢在这里分享代码。也许我漏掉了什么，但是这个代码如何解决原帖中关于0和1子节点不同含义的问题呢？ - templatetypedef

节点按照它们的权重从小到大顺序排列在列表中，因此，最小的权重永远是左侧的节点，在树中它将会成为左子节点(0)或右子节点(1)，如果我错了，抱歉。 - David190

我曾将问题理解为“将树分配给左子树或右子树是否重要？”，而不是“如何分配它们？”但也许这是我误读了。 - templatetypedef

以下是关于编程的相关内容的翻译。请仅返回翻译后的文本，而不要简单地复制代码段并解释它如何回答提问者的问题。 - v2v1