有没有一种生成某个字母表的哈夫曼编码的约定?似乎结果编码取决于您将'0'分配给左子树还是右子树以及如何确定哪个符号将进入左树。
作为一个常见的约定,位'0'表示遵循左孩子,位'1'表示遵循右孩子。
所以这是对第一半差异的回答。然而,我找不到第二半的任何约定。我会假设像使具有较低概率的节点进入左侧之类的事情,但是在线上有几个示例Huffman树不这样做。
例如:
有没有一种生成某个字母表的哈夫曼编码的约定?似乎结果编码取决于您将'0'分配给左子树还是右子树以及如何确定哪个符号将进入左树。
作为一个常见的约定,位'0'表示遵循左孩子,位'1'表示遵循右孩子。
所以这是对第一半差异的回答。然而,我找不到第二半的任何约定。我会假设像使具有较低概率的节点进入左侧之类的事情,但是在线上有几个示例Huffman树不这样做。
例如:
看一下吧
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>