Herstellung Huffman effizienter

Question

Im Moment habe ich diesen Algorithmus Huffman in 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]) 

die Funktion fSetBits ist dieses

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 

Mein größtes Problem ist, dass Codes schnell größer als 8 Bits werden und beim Lesen der Schlüsseltabelle Ich kann Codes sehen, die leicht gekürzt oder neu angeordnet werden können, während die No-Präfix-Regel beibehalten wird. Gibt es eine bessere Möglichkeit, die Bitcodes aus dem Huffman-Baum zu erstellen, die zu etwas Dekodierbarem führen, aber auch viel effizienter?

Answer 1

Dieser Code erstellt einen Huffman-Baum mit geringer Tiefe.
Es basiert auf Greedy-Algorithmus, ich bin mir also nicht sicher, ob es immer die bestmögliche Tiefe erreicht oder nicht.

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])