LZW на Lua

Опубликовано в QLua

Алгоритм Лемпеля — Зива — Уэлча (Lempel-Ziv-Welch, LZW)  : сжатие данных без потерь. Реализация на  Lua

 

local function compress(uncompressed) -- string
  local dictionary, result, dictSize, w, c = {}, {}, 255, ""
    for i = 0, 255 do
      dictionary[string.char(i)] = i
    end
    for i = 1, #uncompressed do
        c = string.sub(uncompressed, i, i)
        if dictionary[w .. c] then
            w = w .. c
        else
            table.insert(result, dictionary[w])
           dictSize = dictSize + 1
           dictionary[w .. c] = dictSize
           w = c
        end
    end
    if w ~= "" then
        table.insert(result, dictionary[w])
    end
    return result
end

local function decompress(compressed) -- table
   local dictionary, dictSize, entry, w, k = {}, 256, "", string.char(compressed[1])
   local result = {w}
   for i = 0, 255 do
      dictionary[i] = string.char(i)
   end
   for i = 2, #compressed do
      k = compressed[i]
      if dictionary[k] then
         entry = dictionary[k]
      elseif k == dictSize then
         entry = w .. string.sub(w, 1, 1)
      else
         return nil, i
      end
      table.insert(result, entry)
      dictionary[dictSize] = w .. string.sub(entry, 1, 1)
      dictSize = dictSize + 1
      w = entry
   end
   return table.concat(result)
end
 

Использование:

 

local example = "TOBEORNOTTOBEORTOBEORNOT"
local com = compress(example)
local dec = decompress(com)
print(table.concat(com, ", "))
print(dec)

 

Комментарии   
0 # Андрей К 04.06.2022 20:48
круто! я себе утащу ?
0 # admin 05.06.2022 00:05
Непременно )

Недостаточно прав для комментирования

Архив QLua