The Lempel-Ziv-Welch (LZW) algorithm provides loss-less data compression.

You can read a complete description of it in the   Wikipedia article   on the subject.   It was patented, but it entered the public domain in 2004.




use Collection;
 
class LZW {
  function : Main(args : String[]) ~ Nil {
    compressed := Compress("TOBEORNOTTOBEORTOBEORNOT");
    Show(compressed);
    decompressed := Decompress(compressed);
    decompressed->PrintLine();
  }
 
  function : native : Compress(uncompressed : String) ~ IntVector {
    # Build the dictionary.
    dictSize := 256;
      dictionary := StringMap->New();
      for (i := 0; i < 256; i+=1;) {
        key := "";
        key->Append(i->As(Char));
        dictionary->Insert(key, IntHolder->New(i));
    };
 
    w := "";
    result := IntVector->New();
 
    each (i : uncompressed) {
      c := uncompressed->Get(i);
      wc := String->New(w);
      wc->Append(c);
        if (dictionary->Has(wc)) {
          w := wc;
        }
        else {
          value := dictionary->Find(w)->As(IntHolder);
          result->AddBack(value->Get());
          # Add wc to the dictionary.        
          dictionary->Insert(wc, IntHolder->New(dictSize));
          dictSize+=1;
          w := "";
          w->Append(c);
        };
      };
 
      # Output the code for w.
      if (w->Size() > 0) {
        value := dictionary->Find(w)->As(IntHolder);
        result->AddBack(value->Get());
      };
 
      return result;    
  }
 
  function : Decompress(compressed : IntVector) ~ String {
    # Build the dictionary.
    dictSize := 256;
    dictionary := IntMap->New();
    for (i := 0; i < 256; i+=1;) {
      value := "";
      value->Append(i->As(Char));
      dictionary->Insert(i, value);
    };
 
    w := "";
    found := compressed->Remove(0);
    w->Append(found->As(Char));
 
    result := String->New(w);    
    each (i : compressed) {
      k := compressed->Get(i);
 
      entry : String;
      if (dictionary->Has(k)) {      
        entry := dictionary->Find(k);
      }
      else if (k = dictSize) {
        entry := String->New(w);
        entry->Append(w->Get(0));
      }
      else {
        return "";
      };    
      result->Append(entry);
 
      # Add w+entry[0] to the dictionary.
      value := String->New(w);
      value->Append(entry->Get(0));
      dictionary->Insert(dictSize, value);
      dictSize+=1;
 
      w := entry;      
    };
 
    return result;
  }
 
  function : Show(results : IntVector) ~ Nil {
    "["->Print();
    each(i : results) {
      results->Get(i)->Print(); 
      if(i + 1 < results->Size()) {
        ", "->Print();
      };
    };
    "]"->PrintLine();
  }
}