Re:Lossless Text Compression [pdf]
by compressedgas on Friday April 09, 2021 @03:00AM
(#26747475)
That's what Re-Pair does. It repeatedly replaces the most frequent substring with a symbol until the input has no repeating substrings.
Re:Lossless Text Compression [pdf]
by kwhitefoot on Friday April 09, 2021 @04:47AM
(#26748156)
I had to do this by hand in the 1980s when I ran out of space in the ROM of the embedded controller I was working on for messages to be printed. There was no way to increase the size of ROM (2716 EPROM) at that stage in the development. The text was all 7 bit ASCII so I used the MSB as a flag to say that the remaining bits were a pointer into a table of frequently used fragments. This saved enough space to include the decompressor; it was recursive too so the fragments could also be compressed.
This is how LZW and Huffman compression work. LZW finds repeated symbol groups and encodes them as new symbols, and Huffman compression codes frequent symbols with fewer bits and infrequent symbols with more bits.
I've been too way too busy (cough.. lazy) to test this idea