lzw_compression.sf

#!/usr/bin/ruby

# Implementation of the LZW compression algorithm.

# See also:
#   https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch

# Compress a string to a list of output symbols.
func compress(String uncompressed) -> Array {

    # Build the dictionary.
    var dict_size = 256;
    var dictionary = Hash.new;

    0 .. dict_size-1 -> each { |i|
        dictionary{i.chr} = i.chr;
    };

    var w = '';
    var result = [];
    uncompressed.each { |c|
        var wc = w+c;
        if (dictionary.has_key(wc)) {
            w = wc;
        } else {
            result.append(dictionary{w});
            # Add wc to the dictionary.
            dictionary{wc} = dict_size;
            dict_size++;
            w = c;
        }
    };

    # Output the code for w.
    if (w != '') {
        result.append(dictionary{w});
    };

    return result;
};

# Decompress a list of output ks to a string.
func decompress(Array compressed) -> String {

    # Build the dictionary.
    var dict_size = 256;
    var dictionary = Hash.new;

    0 .. dict_size-1 -> each { |i|
        dictionary{i.chr} = i.chr;
    };

    var w = compressed.shift;
    var result = w;
    compressed.each { |k|
        var entry;
        if (dictionary.has_key(k)) {
            entry = dictionary{k};
        } elsif (k == dict_size) {
            entry = w+w.substr(0,1);
        } else {
            die "Bad compressed k: #{k}";
        };
        result += entry;

        # Add w+entry[0] to the dictionary.
        dictionary{dict_size} = w+entry.substr(0,1);
        dict_size++;

        w = entry;
    };

    return result;
};

# How to use:
var compressed = compress('TOBEORNOTTOBEORTOBEORNOT');
say compressed.join(' ');
var decompressed = decompress(compressed);
say decompressed;