LZW Compression In Lua [closed]

Question

I would like a function for LZW data compression in the Lua programming language.

Here is the pseudocode -

 pattern = get input character
 while ( not end-of-file ) {
     K = get input character
     if ( <<pattern, K>> is NOT in 
             the string table ){
         output the code for pattern
         add <<pattern, K>> to the string table
         pattern = K
     }
     else { pattern = <<pattern, K>> }
 }
 output the code for pattern
output EOF_CODE

Here is the code I have so far, but it is only printing one character instead of the compressed string.

 function compress(uncompressed)
 local dict_size = 256
 local dictionary = {}
   w = ""
   result = {}
     for i = 1, #uncompressed do
       local c = string.sub(uncompressed, i, i)
       local wc = w .. c
       if dictionary[wc] == true then
           w = wc
       else
           dictionary[w] = ""
           dictionary[wc] = dict_size
           dict_size = dict_size + 1
           w = c
       end
     if w then
       dictionary[w] = ""
     end
     return w
   end
 end

 compressed = compress('TOBEORNOTTOBEORTOBEORNOT')
 print(compressed)

Answer 1

I feel like a teacher...

• Your return statement is inside the for loop, thus the loop only runs once.
• You do not use the dictionary at all, you only generate it. It's like a black hole. Nothing ever comes out. In order to decompress your string, you need the dictionary!
• You have defined a result variable/table but do not use it.
• You test equality to true of wc but it only ever contains a number or string value
• It seems that dict_size is both your current and maximum dictionary size
• You do not actually limit the dictionary size
• The pseudo-code is meant to output the compressed data during the loop, I'm not completely sure what output the code for pattern means exactly, but I assume it's your the value of dictionary[wc]...

I expanded your code below, so you can see that it at least does something when the return statement is put after the loop and the equality is fixed.

function compress(uncompressed)
    local dict_size = 256
    local dictionary = {}
    w = ""
    result = {}
    for i = 1, #uncompressed do
        local c = uncompressed:sub(i, i)
        local wc = w .. c
        if dictionary[wc] then
            w = wc
        else
            dictionary[w] = ""
            dictionary[wc] = dict_size
            dict_size = dict_size + 1
            w = c
        end
        if w then
            dictionary[w] = ""
        end
    end
    return w, dictionary
end

compressed, dict = compress('TOBEORNOTTOBEORTOBEORNOT')
print(compressed)

for k,v in pairs(dict) do
    print(k, v);
end

Answer 2

I'm unfamilar with Lua but have implemented several kinds of LZ data compression. Try using debug functions to display the dictionary. It appears that non-null strings are not being added into the dictionary. Also, your dictionary is initially empty while typically it is initialized with the 256 1-char strings.