Solver for LZ77 exercises

lz77.lua

-- lz77.lua
module(..., package.seeall)

-- Length of the common prefix of str1 and str2
function equal_characters(str1, str2)
  -- Shortest length
  local len
  if string.len(str1) < string.len(str2) then
    len = string.len(str1)
  else
    len = string.len(str2)
  end

  -- Loop while equal...
  local i = 1
  while i <= len and string.sub(str1, i, i) == string.sub(str2, i, i) do
    i = i + 1
  end

  -- Return common prefix length
  if i <= len then
    return i - 1
  else
    return len
  end
end

-- LZ77 compression, write to stdout
function lz77(text, sliding_window_length)
  sliding_window_length = sliding_window_length or 6

  local offset = 1
  local reached_eof = false
  while not reached_eof do
    -- Find the sliding window
    local sliding_window_offset = offset - sliding_window_length
    if sliding_window_offset < 1 then sliding_window_offset = 1 end
    local sliding_window =
      string.sub(text, sliding_window_offset, offset - 1)

    -- The part of the text that matters
    local offset_text = string.sub(text, offset)

    -- Find the longest match in the sliding window
    local longest = 0
    local longest_position = 0
    for i = 1, string.len(sliding_window) do
      local n = equal_characters(string.sub(sliding_window, i), offset_text)
      if n > longest then
        longest = n
        longest_position = i
      end
    end

    -- Determine follower
    local follower_position = offset + longest
    local follower 
    if follower_position <= string.len(text) then
      follower = string.sub(text, follower_position, follower_position)
    else
      follower = "EOF"
      reached_eof = true
    end

    -- Output results
    print(string.format("(%d, %d, %s)", longest_position, longest, follower))

    -- Continue
    offset = follower_position + 1
  end
end