1. --[dirGames-L] Huffman encoding/decoding source.
  2. --lucas at mach8.nl lucas at mach8.nl
  3. --Sun Mar 3 15:12:31 EST 2002
  4. --
  5. --Previous message: [dirGames-L] A * in director
  6. --Next message: [dirGames-L] Huffman encoding/decoding source.
  7. --Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
  8. --------------------------------------------------------------------------------
  9. --Hi,
  10. --
  11. --For anyone who cares, below is a huffman encoding/decoding script I wrote
  12. --today.. it's totally not optimized, the only thing that it does is
  13. --work..
  14. --
  15. -- Huffman encoder/decoder,   written by lucas at mach8.nl
  16. --
  17. -- Usage:
  18. --
  19. --   t=HUFFMAN_ENCODE("dit is een mooiestring")
  20. --   tString=HUFFMAN_DECODE(t)
  21. --  
  22. --   tString now contains "dit is een mooie string", and t contains a compact representation of that string.
  23. --
  24. -- This script can easily be adjusted to work on images/integers instead of strings,
  25. -- and its output can also easily be adjusted to ouput into an image, or into whatever you see fir.
  26.  
  27.  
  28. on HUFFMAN_ENCODE(tInput)
  29.   tTree=MACH8_makeTree(tInput)
  30.   data=MACH8_encode(tInput,tTree)
  31.   return [data,tTree]
  32. end
  33.  
  34. on HUFFMAN_DECODE(tInput)
  35.   tTree=tInput[2]    
  36.   tIntegers=tInput[1][1]
  37.   tBitCount=tInput[1][2]
  38.   tOutput=EMPTY
  39.   tCurrentTree=tTree
  40.  
  41.   -- go back to binary representation
  42.   tBinary=[]
  43.   repeat with I in tIntegers
  44.     repeat with ii=1 to 32
  45.       if bitAnd(power(2,ii-1),I) then
  46.         tBinary.append(1)
  47.       else
  48.         tBinary.append(0)
  49.       end if
  50.     end repeat
  51.   end repeat
  52.   repeat while tBinary.count>tBitCount
  53.     tBinary.deleteAt(tBinary.count)
  54.   end repeat
  55.  
  56.  
  57.   repeat while tBinary.count>0
  58.     case tBinary[1] of
  59.       0:tCurrentTree=tCurrentTree[1]
  60.       1:tCurrentTree=tCurrentTree[2]
  61.     end case
  62.     if ilk(tCurrentTree)=#string then    
  63.       tOutput=tOutput&tCurrentTree
  64.       tCurrentTree=tTree
  65.     end if
  66.     tBinary.deleteAt(1)
  67.   end repeat
  68.   return tOutput
  69. end
  70.  
  71. on MACH8_encode(tInput,tTree)
  72.   tOutput=[]
  73.   tTemp=[]
  74.   repeat with i=1 to tInput.char.count
  75.     MACH8_mergeLists(tTemp,MACH8_findCode(tTree,tInput.char[i]))
  76.   end repeat
  77.  
  78.   -- padd to multiple of 32
  79.   tBitCount=tTemp.count
  80.   repeat while tTemp.count mod 32<>0 then
  81.     tTemp.append(0)
  82.   end repeat
  83.  
  84.   repeat while tTemp.count>=32
  85.     t=0
  86.     repeat with i=1 to 32
  87.       if tTemp[1]=1 then t=bitOr(t, power(2,i-1))
  88.       tTemp.deleteAt(1)
  89.     end repeat
  90.    
  91.     tOutput.append(t)
  92.   end repeat
  93.   return [tOutput,tBitCount]
  94. end
  95.  
  96. on MACH8_findCode(tTree,tChar)
  97.   case ilk(tTree) of
  98.     #string:
  99.       if tTree=tChar then
  100.         return list()
  101.       else
  102.         return -1
  103.       end if
  104.     #list:      
  105.       t=MACH8_findCode(tTree[1],tChar)
  106.       if t<>-1 then
  107.         t.addAt(1,0)
  108.         return t
  109.       else
  110.         t=MACH8_findCode(tTree[2],tChar)
  111.         if t<>-1 then
  112.           t.addAt(1,1)
  113.           return t
  114.         else
  115.           return -1
  116.         end if
  117.       end if
  118.   end case
  119. end
  120.  
  121. on MACH8_mergeLists(tList1,tList2)
  122.   repeat with I in tList2
  123.     tList1.append(I)
  124.   end repeat
  125. end
  126.  
  127. on MACH8_makeTree(tInput)
  128.   t=[:]  
  129.   repeat with i=1 to tInput.char.count
  130.     t[tInput.char[i]]=t[tInput.char[i]]+1
  131.   end repeat
  132.   freqList=[]
  133.   repeat with i=1 to t.count
  134.     freqList.append([t[i],t.getPropAt(i)])
  135.   end repeat
  136.  
  137.   -- make tree
  138.   repeat while freqList.count>1
  139.     sort(freqList)    
  140.     t=[freqList[1][1]+freqList[2][1],[freqlist[1][2],freqlist[2][2]]]
  141.     freqList.deleteAt(1)
  142.     freqList.deleteAt(1)
  143.     freqList.addAt(1,t)
  144.   end repeat
  145.   return freqlist[1][2]
  146. end
  147.  
  148.  
[raw code]