lempel ziv welch


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Lempel-Ziv Welch compression data algorithm implementation
-- See : http://en.wikipedia.org/wiki/LZW

local function lzw_encode(str)
  local w = ''
  local result = {}
  local dict_size = 256

  -- Builds the dictionnary
  local dict = {}
  for i = 0, dict_size-1 do
    dict[string.char(i)] = i
  end

  local i = dict_size

  for char in str:gmatch('.') do
    -- Finds the longest string matching the input
    local wc = w .. char
    if dict[wc] then
      -- Save the current match index
      w = wc
    else
      -- Add the match to the dictionary
      table.insert(result, dict[w])
      dict[wc] = i
      i = i + 1
      w = char
    end
  end
  if w~='' then
    table.insert(result, dict[w])
  end
  return result
end

local function lzw_decode(str)
  local dict_size = 256

  -- Builds the dictionary
  local dict = {}
  for i = 0, dict_size-1 do
    dict[i] = string.char(i)
  end

  local w = string.char(str[1])
  local result = w
  for i = 2, #str do
    local k = str[i]
    local entry = ''
    if dict[k] then
      entry = dict[k]
    elseif k == dict_size then
      entry = w .. w:sub(1,1)
    else
      return nil -- No match found, decoding error
    end
    result = result .. entry
    dict[dict_size] = w .. entry:sub(1,1)
    dict_size = dict_size + 1
    w = entry
  end
  return result
end

return {
  encode = lzw_encode,
  decode = lzw_decode,
}

-- Tests for lzw.lua
local lzw = require 'lzw'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

local function same(t1, t2)
  if #t1 ~= #t2 then return false end
  for k,v in ipairs(t1) do
    if v ~= t2[k] then return false end
  end
  return true
end

run('Encoding string test', function()
  assert(same(lzw.encode('TOBEORNOTTOBEORTOBEORNOT'), {84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263}))
end)

run('Decoding string test', function()
  assert(lzw.decode(lzw.encode('TOBEORNOTTOBEORTOBEORNOT')) == 'TOBEORNOTTOBEORTOBEORNOT')
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))