--[dirGames-L] Huffman encoding/decoding source.
--lucas at mach8.nl lucas at mach8.nl
--Sun Mar 3 15:12:31 EST 2002
--
--Previous message: [dirGames-L] A * in director
--Next message: [dirGames-L] Huffman encoding/decoding source.
--Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
--------------------------------------------------------------------------------
--Hi,
--
--For anyone who cares, below is a huffman encoding/decoding script I wrote
--today.. it's totally not optimized, the only thing that it does is
--work..
--
-- Huffman encoder/decoder, written by lucas at mach8.nl
--
-- Usage:
--
-- t=HUFFMAN_ENCODE("dit is een mooiestring")
-- tString=HUFFMAN_DECODE(t)
--
-- tString now contains "dit is een mooie string", and t contains a compact representation of that string.
--
-- This script can easily be adjusted to work on images/integers instead of strings,
-- and its output can also easily be adjusted to ouput into an image, or into whatever you see fir.
on HUFFMAN_ENCODE(tInput)
tTree=MACH8_makeTree(tInput)
data=MACH8_encode(tInput,tTree)
return [data,tTree]
end
on HUFFMAN_DECODE(tInput)
tTree=tInput[2]
tIntegers=tInput[1][1]
tBitCount=tInput[1][2]
tOutput=EMPTY
tCurrentTree=tTree
-- go back to binary representation
tBinary=[]
repeat with I in tIntegers
repeat with ii=1 to 32
if bitAnd(power(2,ii-1),I) then
tBinary.append(1)
else
tBinary.append(0)
end if
end repeat
end repeat
repeat while tBinary.count>tBitCount
tBinary.deleteAt(tBinary.count)
end repeat
repeat while tBinary.count>0
case tBinary[1] of
0:tCurrentTree=tCurrentTree[1]
1:tCurrentTree=tCurrentTree[2]
end case
if ilk(tCurrentTree)=#string then
tOutput=tOutput&tCurrentTree
tCurrentTree=tTree
end if
tBinary.deleteAt(1)
end repeat
return tOutput
end
on MACH8_encode(tInput,tTree)
tOutput=[]
tTemp=[]
repeat with i=1 to tInput.char.count
MACH8_mergeLists(tTemp,MACH8_findCode(tTree,tInput.char[i]))
end repeat
-- padd to multiple of 32
tBitCount=tTemp.count
repeat while tTemp.count mod 32<>0 then
tTemp.append(0)
end repeat
repeat while tTemp.count>=32
t=0
repeat with i=1 to 32
if tTemp[1]=1 then t=bitOr(t, power(2,i-1))
tTemp.deleteAt(1)
end repeat
tOutput.append(t)
end repeat
return [tOutput,tBitCount]
end
on MACH8_findCode(tTree,tChar)
case ilk(tTree) of
#string:
if tTree=tChar then
return list()
else
return -1
end if
#list:
t=MACH8_findCode(tTree[1],tChar)
if t<>-1 then
t.addAt(1,0)
return t
else
t=MACH8_findCode(tTree[2],tChar)
if t<>-1 then
t.addAt(1,1)
return t
else
return -1
end if
end if
end case
end
on MACH8_mergeLists(tList1,tList2)
repeat with I in tList2
tList1.append(I)
end repeat
end
on MACH8_makeTree(tInput)
t=[:]
repeat with i=1 to tInput.char.count
t[tInput.char[i]]=t[tInput.char[i]]+1
end repeat
freqList=[]
repeat with i=1 to t.count
freqList.append([t[i],t.getPropAt(i)])
end repeat
-- make tree
repeat while freqList.count>1
sort(freqList)
t=[freqList[1][1]+freqList[2][1],[freqlist[1][2],freqlist[2][2]]]
freqList.deleteAt(1)
freqList.deleteAt(1)
freqList.addAt(1,t)
end repeat
return freqlist[1][2]
end