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位和讀取時關鍵表我可以看到很容易縮短或重新排列的代碼,同時保持沒有前綴規則。有沒有更好的方法來創建霍夫曼樹中的位碼,這將導致可解碼的內容,但效率更高?
所有可能的霍夫曼樹在壓縮比方面具有相同的效率。但他們可能有不同的樹深度。爲了減少樹深度,您應該在'fSort(tTree,...)'中選擇兩個可連接的子樹時考慮子樹的深度。不過,你應該可以使用深度> 8的樹來製作真正的霍夫曼編碼器。在使用霍夫曼編碼長度超過8位時,你有什麼困難? –