使哈夫曼更高效

2016-5-14 4:45:14
收藏：0
阅读：84
评论：1

我目前在 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 位，在读取密钥表时，我可以看到可以轻松缩短或重新排列的代码，同时保持无前缀规则。有没有更好的方法从哈夫曼树中创建比特代码，这将导致编码可解码但更高效？

点赞
用户1847592
用户1847592

这段代码构建了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])
2016-05-14 11:29:50

作者:

用户3788161

用户3788161
推荐文章