• Activity
  • Votes
  • Comments
  • New
  • All activity
  • Showing only topics in ~comp with the tag "compression". Back to normal view / Search all groups
    1. Programming Challenge: Text compression

      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...

      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

      13 votes
    2. Where would a beginner start with data compression? What are some good books for it?

      Mostly the title. I have experience with Python, and I was thinking of learning more about data compression. How should I proceed? And what are some good books I could read, both about specifics...

      Mostly the title. I have experience with Python, and I was thinking of learning more about data compression. How should I proceed? And what are some good books I could read, both about specifics and abstracts of data compression, data management, data in general.

      15 votes