run length encoding


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Run-Length Encoding Compression algorithm  implementation
-- See: https://en.wikipedia.org/wiki/Run-length_encoding

-- Compresses an input string using RLE algorithm
-- @str    :  an input string to be compressed
-- returns : the encoded string
function rle_encode(str)
  local prev = str:sub(1,1)
  local count = 0
  local encoded = ''
  for char in str:gmatch('.') do
    if char == prev then
      count = count + 1
    else
      encoded = encoded .. (count .. prev)
      prev = char
      count = 1
    end
  end
  return encoded .. (count .. prev)
end

-- Decodes a given input
-- @str    : an encoded string
-- returns : the original string
function rle_decode(str)
  local decoded_str = ''
  for count, match in str:gmatch('(%d+)([^%d]+)') do
    decoded_str = decoded_str .. (match:rep(count))
  end
  return decoded_str
end

return {
  encode = rle_encode,
  decode = rle_decode,
}
-- Tests for rle.lua
local rle = require 'rle'

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

run('Encoding string tests', function()
  assert(rle.encode('W')                                                                   == '1W')
  assert(rle.encode('WWWW')                                                                == '4W')
  assert(rle.encode('wwwwwiiiikkkkkkkiiippppppeeeeeddddiia')                               == '5w4i7k3i6p5e4d2i1a')
  assert(rle.encode('BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB') == '12B1N12B3N24B1N14B')
  assert(rle.encode('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW') == '12W1B12W3B24W1B14W')
end)

run('Decoding string tests', function()
  assert(rle.decode(rle.encode('WW'))                                                                  == 'WW')
  assert(rle.decode(rle.encode('WWWW'))                                                                == 'WWWW')
  assert(rle.decode(rle.encode('wwwwwiiiikkkkkkkiiippppppeeeeeddddiia'))                               == 'wwwwwiiiikkkkkkkiiippppppeeeeeddddiia')
  assert(rle.decode(rle.encode('BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB')) == 'BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB')
  assert(rle.decode(rle.encode('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW')) == 'WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW')

end)

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