決策霍夫曼更有效

Question

我目前在Lua這一霍夫曼算法

for _,v in next, tData do 
    tFreq[v] = tFreq[v] and tFreq[v]+1 or 1 
end 
for k,v in next,tFreq do 
    iCount = iCount + 1 
    fInsert(tTree,{freq=v,contains=k}) 
end 
while #tTree>1 do 
    fSort(tTree, function(a,b) 
     return a.freq<b.freq 
    end) 
    fInsert(tTree,{freq=tTree[1].freq+tTree[2].freq,contains={tTree[1],tTree[2]}}) 
    fRemove(tTree,1) 
    fRemove(tTree,1) 
end 
iMaxSize, tKey = fSetBits(tTree[1]) 

功能fSetBits是這個

local function fSetBits(tData, sCurrBit, sThisBit, bInternal) 
    local iMaxBit, iPossBit, tSet 

    sCurrBit = sCurrBit or "" 
    sThisBit = sThisBit or "0" 

    local tSolution = {} 
    if type(tData.contains)=="table" then 
     iMaxBit,tSet = fSetBits(tData.contains[1],sCurrBit..(bInternal and sThisBit or ""),1,true) 
     for k,v in next,tSet do 
      tSolution[k] = v 
     end 
     iPossMax,tSet = fSetBits(tData.contains[2],sCurrBit..(bInternal and sThisBit or ""),0,true) 
     iMaxBit = iMaxBit>iPossMax and iMaxBit or iPossMax 
     for k,v in next,tSet do 
      tSolution[k] = v 
     end 
    else 
     tSolution[tData.contains]=sCurrBit..sThisBit 
     iMaxBit = #sCurrBit+1 
    end 
    return iMaxBit, tSolution 
end 

我最大的問題是，代碼很快就會大於8位和讀取時關鍵表我可以看到很容易縮短或重新排列的代碼，同時保持沒有前綴規則。有沒有更好的方法來創建霍夫曼樹中的位碼，這將導致可解碼的內容，但效率更高？

Answer 1

此代碼構建Huffman低深度樹。
它基於貪婪算法，所以我不確定它是否總能達到最好的深度。

for _,v in next, tData do 
    tFreq[v] = tFreq[v] and tFreq[v]+1 or 1 
end 
for k,v in next,tFreq do 
    iCount = iCount + 1 
    fInsert(tTree,{freq=v,contains=k,depth=0}) 
end 
while #tTree>1 do 
    fSort(tTree, function(a,b) 
    return a.freq<b.freq or a.freq==b.freq and a.depth<b.depth 
    end) 
    fInsert(tTree,{ 
    freq=tTree[1].freq+tTree[2].freq, 
    contains={tTree[1],tTree[2]}, 
    depth=math.max(tTree[1].depth,tTree[2].depth)+1}) 
    fRemove(tTree,1) 
    fRemove(tTree,1) 
end 
iMaxSize, tKey = fSetBits(tTree[1])