Multigram Compression
Efficient compression is more tricky…
Given a simple alphabet of only “A” and “B”.
with the set of multigrams “A”, “B”, “AB” and “BAA”.
Encode the string “ABAA”.
The greedy solution uses 3 bytes “AB”, “A” and “A”.
An optimal solution uses only 2 bytes, “A” and “BAA”.