让霍夫曼更有效率

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 位，并且在读取密钥时 table 我可以看到代码可以很容易地缩短或重新排列，同时保持无前缀规则。有没有更好的方法从霍夫曼树创建比特码，从而产生可解码但效率更高的东西？

Answer 1

此代码构建哈夫曼低深度树。
它是基于贪心算法的，所以我不确定它是否总能达到最佳深度。

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

让霍夫曼更有效率

making huffman more efficient

lua

scripting

compression

huffman-code