Programming Challenge: Text compression

gpl
2019-05-24T22:43:36Z

In an effort to make these weekly, I present a new programming challenge.

The challenge this week is to compress some text using a prefix code. Prefix codes associate each letter with a given bit string, such that no encoded bitstring is the prefix of any other. These bit strings are then concatenated into one long integer which is separated into bytes for ease of reading. These bytes can be represented as hex values as well. The provided prefix encoding is as follows:

char | value | char | value
' ' | 11 | 'e' | 101
't' | 1001 | 'o' | 10001
'n' | 10000 | 'a' | 011
's' | 0101 | 'i' | 01001
'r' | 01000 | 'h' | 0011
'd' | 00101 | 'l' | 001001
'~' | 001000 | 'u' | 00011
'c' | 000101 | 'f' | 000100
'm' | 000011 | 'p' | 0000101
'g' | 0000100 | 'w' | 0000011
'b' | 0000010 | 'y' | 0000001
'v' | 00000001 | 'j' | 000000001
'k' | 0000000001 | 'x' | 00000000001
'q' | 000000000001 | 'z' | 000000000000

Challenge

Your program should accept a lowercase string (including the ~ character), and should output the formatted compressed bit string in binary and hex. Your final byte should be 0 padded so that it has 8 bits as required. For your convenience, here is the above table in a text file for easy read-in.

Example

Here is an example:

$> tildes ~comp
10010100 10010010 01011010 10111001 00000010 11000100 00110000 10100000
94 92 5A B9 02 C4 30 A0

Bonuses

1. Print the data compression ratio for a given compression, assuming the original input was encoded in 8 bit ASCII (one byte per character).
2. Output the ASCII string corresponding to the encoded byte string in addition to the above outputs.

2. @onyxleopard points out that many bytes won't actually be valid ASCII. Instead, do as they suggested and treat each byte as an ordinal value and print it as if encoded as UTF-8.

3. An input prefixed by 'D' should be interpreted as an already compressed string using this encoding, and should be decompressed (by inverting the above procedure).

Previous Challenges (I am aware of prior existing ones, but it is hard to collect them as they were irregular. Thus I list last week's challenge as 'Week 1')
Week 1

Comments URL: https://tildes.net/~comp/dr0/programming_challenge_text_compression

Votes: 13

Comments: 6