InTesting

Huffman Compression

Apr 19th, 2021
513
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. local a = 'wow potato'
  2.  
  3.  
  4.  
  5. local function TableClone(t)
  6.     local nt = {}
  7.     for i,v in next,t do
  8.         nt[i] = v
  9.     end
  10.     return nt
  11. end
  12.  
  13. local function GetIdFromLetterInHeiarchy(hi,let)
  14.     local res
  15.    
  16.     for i,a in next,hi do
  17.         local cres
  18.        
  19.         if type(a.Char)=='table'then
  20.             cres = GetIdFromLetterInHeiarchy(a.Char,let)
  21.             if cres then
  22.             end
  23.         elseif a.Char==let then
  24.             cres = ''
  25.         end
  26.        
  27.         if not cres then continue end
  28.         res = tostring(i - 1) ..  cres
  29.         break
  30.     end
  31.    
  32.     return res
  33. end
  34.  
  35.  
  36.  
  37. local function HuffmanCompress(str)
  38.     local res_dict = {}
  39.     local res_str = ''
  40.    
  41.     local char_freq = {}
  42.     local LeastArray = {}
  43.     for p = 1,#str do
  44.         local char = str:sub(p,p)
  45.        
  46.         if not char_freq[char]then
  47.             char_freq[char] = 0
  48.         end
  49.         char_freq[char] += 1
  50.     end
  51.    
  52.     for char,freq in next,char_freq do
  53.         table.insert(LeastArray,{Char = char,Frequency = freq})
  54.     end
  55.     while #LeastArray>1 do
  56.         if workspace:FindFirstChild('Stop')then break end
  57.        
  58.         table.sort(LeastArray,function(a,b)
  59.             return a.Frequency<b.Frequency
  60.         end)
  61.        
  62.         local set1 = LeastArray[1]
  63.         local set2 = LeastArray[2]
  64.        
  65.         table.remove(LeastArray,2)
  66.        
  67.         local newset = {}
  68.         newset.Char = {set1,set2}
  69.         newset.Frequency = set1.Frequency + set2.Frequency
  70.         LeastArray[1] = newset
  71.     end
  72.    
  73.     local res_dict = {}
  74.    
  75.     for p = 1,#str do
  76.         local let = str:sub(p,p)
  77.         local id = res_dict[let]
  78.         if not id then
  79.             res_dict[let] = GetIdFromLetterInHeiarchy(LeastArray,let):sub(2)
  80.             id = res_dict[let]
  81.         end
  82.         res_str ..= id
  83.     end
  84.    
  85.     local inv_dict = {}
  86.     for i,v in next,res_dict do
  87.         inv_dict[v] = i
  88.     end
  89.    
  90.     res_dict = inv_dict
  91.    
  92.     return res_dict,res_str
  93. end
  94.  
  95. local function HuffmanDecompress(tab,str)
  96.     local res = ''
  97.    
  98.     local curr_index = 1
  99.     for p = 1,#str do
  100.         local section = str:sub(curr_index,p)
  101.         local let = tab[section]
  102.         if not let then continue end
  103.         res ..= let
  104.         curr_index = p + 1
  105.     end
  106.  
  107.     return res
  108. end
  109.  
  110. local tab,str = HuffmanCompress(a)
  111.  
  112. print(tab,str)
  113. print(HuffmanDecompress(tab,str))
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×