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.




go =>
  S = "TOBEORNOTTOBEORTOBEORNOT",
  println(s=S),
  println(len=S.length),
 
  Compressed = compress(S),
  println(compressed=Compressed),
  println(len=Compressed.length),
 
  Uncompressed = uncompress(Compressed),
  println(uncompressed=Uncompressed),
 
  printf("compressed to %3.3f%%\n", 100*(Compressed.length / S.length)),
 
  if S = Uncompressed then
    println("Same!")
  else
    println("Error: S != Uncompressed!"),
    printf("S.length: %d  Uncompressed.length: %d\n", S.length, Uncompressed.length),
    edit(S,Uncompressed,Distance,Diffs),
    println(distance=Distance),
    println(diffs=Diffs)
  end,
  nl.
 
compress(Uncompressed) = Compressed =>
  DictSize = 256,
  Dict = new_map([C=C : I in 1..DictSize-1, C=chr(I).to_string()]),
  W = "",
  Result = [],
  foreach(C in Uncompressed) 
    C := C.to_string(),
    WC = W ++ C,
    if Dict.has_key(WC) then
      W := WC
    else 
      Result := Result ++ [Dict.get(W)],
      Dict.put(WC, DictSize),
      DictSize := DictSize + 1,
      W := C
    end
  end,
  if W.length > 0 then
     Result := Result ++ [Dict.get(W)]
  end,
  Compressed = Result.
 
uncompress(Compressed) = Uncompressed => 
  DictSize = 256,
  Dict = new_map([ C=C : I in 1..DictSize-1, C=chr(I).to_string()]),
  W = Compressed.first(),
  Compressed := Compressed.tail(),
  Result = W,
 
  Entry = "",
  foreach(K in Compressed) 
    if Dict.has_key(K) then
      Entry := Dict.get(K)
    elseif K == DictSize then
      Entry := W ++ W[1].to_string()
    else
      printf("Bad compressed K: %w\n", K)
    end,
    Result := Result ++ Entry,   
    Dict.put(DictSize,(W ++ Entry[1].to_string())),
    DictSize := DictSize + 1,
    W := Entry
  end,
  Uncompressed = Result.flatten().
 
%
% Computing the minimal editing distance of two given lists
%
table(+,+,min,-)
edit([],[],D,Diffs) => D=0, Diffs=[].
edit([X|Xs],[X|Ys],D,Diffs) =>   % copy
    edit(Xs,Ys,D,Diffs).
edit(Xs,[Y|Ys],D,Diffs) ?=>      % insert
    edit(Xs,Ys,D1,Diffs1),
    D=D1+1,
    Diffs = [insert=Y,xPos=Xs.length,yPos=Ys.length|Diffs1].
edit([X|Xs],Ys,D,Diffs) =>       % delete
    edit(Xs,Ys,D1,Diffs1),
    D=D1+1,
    Diffs = [[delete=X,xPos=Xs.length,yPos=Ys.length]|Diffs1].