123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081 |
- #!/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;
|