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.




F compress(uncompressed)
   V dict_size = 256
   V dictionary = Dict((0 .< dict_size).map(i -> (String(Char(code' i)), i)))
   V w = ‘’
   [Int] result
   L(c) uncompressed
      V wc = w‘’c
      I wc C dictionary
         w = wc
      E
         result.append(dictionary[w])
         dictionary[wc] = dict_size
         dict_size++
         w = c
 
   I !w.empty
      result.append(dictionary[w])
 
   R result
 
F decompress([Int] &compressed)
   V dict_size = 256
   V dictionary = Dict((0 .< dict_size).map(i -> (i, String(Char(code' i)))))
   V result = ‘’
   V w = String(Char(code' compressed.pop(0)))
   result ‘’= w
   L(k) compressed
      V entry = ‘’
      I k C dictionary
         entry = dictionary[k]
      E I k == dict_size
         entry = w‘’w[0]
      E
         exit(‘Bad compressed k: ’k)
      result ‘’= entry
      dictionary[dict_size] = w‘’entry[0]
      dict_size++
      w = entry
 
   R result
 
V compressed = compress(‘TOBEORNOTTOBEORTOBEORNOT’)
print(compressed)
print(decompress(&compressed))