Naïve compression

Question

using Prefixed Length Code

We are going to implement a compression of text (string, array/list of characters/bytes) by simple substitution of each character by a binary code, based on the frequency of that character in the text. The characters that occur more frequently will be replaced by shorter codes. The resulting bit array will be split on chunks with length 8.

The code

Prefixed Length Code with length 3 is a code that consist of a prefix - 3 bits indicating the length of the field that follows, and a field. 3 bits are sufficient for 8 (2^3) different prefixes. Each prefix n in turn describes 2^n different fields, enumerated from 0 to 2^n-1.

n = 0; 1 entry (2^0)

000 – field with length 0;

n = 1; 2 entries (2^1)

001|0      (`|` is put for clarity)
001|1    

n = 2; 4 entries (2^2)

010|00
010|01
010|10
010|11

…

n = 7; 128 entries (2^7)

111|0000000
111|0000001
111|0000010
…
111|1111111

Here’s a table of all the codes, enumerated from 0 to 254

┌──┬────────┬─────────┬─────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│  │0       │32       │64       │96        │128       │160       │192       │224       │
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│0 │000     │10100001 │110000001│110100001 │1110000001│1110100001│1111000001│1111100001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│1 │0010    │10100010 │110000010│110100010 │1110000010│1110100010│1111000010│1111100010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│2 │0011    │10100011 │110000011│110100011 │1110000011│1110100011│1111000011│1111100011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│3 │01000   │10100100 │110000100│110100100 │1110000100│1110100100│1111000100│1111100100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│4 │01001   │10100101 │110000101│110100101 │1110000101│1110100101│1111000101│1111100101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│5 │01010   │10100110 │110000110│110100110 │1110000110│1110100110│1111000110│1111100110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│6 │01011   │10100111 │110000111│110100111 │1110000111│1110100111│1111000111│1111100111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│7 │011000  │10101000 │110001000│110101000 │1110001000│1110101000│1111001000│1111101000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│8 │011001  │10101001 │110001001│110101001 │1110001001│1110101001│1111001001│1111101001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│9 │011010  │10101010 │110001010│110101010 │1110001010│1110101010│1111001010│1111101010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│10│011011  │10101011 │110001011│110101011 │1110001011│1110101011│1111001011│1111101011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│11│011100  │10101100 │110001100│110101100 │1110001100│1110101100│1111001100│1111101100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│12│011101  │10101101 │110001101│110101101 │1110001101│1110101101│1111001101│1111101101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│13│011110  │10101110 │110001110│110101110 │1110001110│1110101110│1111001110│1111101110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│14│011111  │10101111 │110001111│110101111 │1110001111│1110101111│1111001111│1111101111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│15│1000000 │10110000 │110010000│110110000 │1110010000│1110110000│1111010000│1111110000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│16│1000001 │10110001 │110010001│110110001 │1110010001│1110110001│1111010001│1111110001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│17│1000010 │10110010 │110010010│110110010 │1110010010│1110110010│1111010010│1111110010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│18│1000011 │10110011 │110010011│110110011 │1110010011│1110110011│1111010011│1111110011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│19│1000100 │10110100 │110010100│110110100 │1110010100│1110110100│1111010100│1111110100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│20│1000101 │10110101 │110010101│110110101 │1110010101│1110110101│1111010101│1111110101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│21│1000110 │10110110 │110010110│110110110 │1110010110│1110110110│1111010110│1111110110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│22│1000111 │10110111 │110010111│110110111 │1110010111│1110110111│1111010111│1111110111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│23│1001000 │10111000 │110011000│110111000 │1110011000│1110111000│1111011000│1111111000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│24│1001001 │10111001 │110011001│110111001 │1110011001│1110111001│1111011001│1111111001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│25│1001010 │10111010 │110011010│110111010 │1110011010│1110111010│1111011010│1111111010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│26│1001011 │10111011 │110011011│110111011 │1110011011│1110111011│1111011011│1111111011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│27│1001100 │10111100 │110011100│110111100 │1110011100│1110111100│1111011100│1111111100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│28│1001101 │10111101 │110011101│110111101 │1110011101│1110111101│1111011101│1111111101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│29│1001110 │10111110 │110011110│110111110 │1110011110│1110111110│1111011110│1111111110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│30│1001111 │10111111 │110011111│110111111 │1110011111│1110111111│1111011111│1111111111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│31│10100000│110000000│110100000│1110000000│1110100000│1111000000│1111100000│          │
└──┴────────┴─────────┴─────────┴──────────┴──────────┴──────────┴──────────┴──────────┘

The process

First we need to sort all the unique characters in the text in decreasing order by their frequency. Then we will assign each character a code – the most frequent one will get 000, the next one - 0010 and so on. Now it’s time to traverse the text and replace each character with its corresponding code. At the end we split the resulting binary list to 8-bit chinks and convert them to decimal (or hexadecimal) integers. The last chunk may be shorter than 8 bits, so it should be filled to 8 bits. The fill is unimportant, so you can use whatever values you want – all 0, all 1 or any combination of 1 and 0. In order for the compressed data to be decompressable, we need to keep track of the length of the original message, as well as the sorted list of the characters.

The task

Write two functions (or complete programs):

• Compress, which takes a string as an input and returns the compressed data. The compressed data should include the compressed list/array of decimal or hexadecimal integers, the length of the original input and the sorted list of characters. The three can be in an arbitrary order and can be stored as a list, array, tuple or any other structure, convenient for you. For example my test code in J returns an array of 3 boxed values :

     compress 'Hello World'
  ┌──┬────────┬────────────────┐
  │11│loredWH │90 0 38 20 70 18│
  └──┴────────┴────────────────┘
  

** Note: If you don't need the length of the original input for your decompressor, you don't need to save it/print it in you compressor.

• Decompress, which takes a compressed data and returns the string after decompression.

Scoring and winning criteria

Your score is the sum of the lengths in bytes of your two functions. The lowest score in every language wins.

Test cases

   compress 'Hello World'
┌──┬────────┬────────────────┐
│11│loredWH │90 0 38 20 70 18│
└──┴────────┴────────────────┘
   decompress 11;'loredWH ';90 0 38 20 70 18
Hello World

   compress 'Code Golf Stack Exchange is a site for recreational programming competitions'
┌──┬───────────────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│76│ oieatrncsmgplfxkhdSGEC│142 80 208 34 147 207 136 138 75 48 68 104 12 194 75 14 32 27 65 33 163 82 3 228 176 180 50 180 37 70 76 37 224 234 201 197 165 182 205 135 3 36 219 168 81 168 201 134 128│
└──┴───────────────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
   decompress 76;' oieatrncsmgplfxkhdSGEC'; 142 80 208 34 147 207 136 138 75 48 68 104 12 194 75 14 32 27 65 33 163 82 3 228 176 180 50 180 37 70 76 37 224 234 201 197 165 182 205 135 3 36 219 168 81 168 201 134 128
Code Golf Stack Exchange is a site for recreational programming competitions

   compress 'GFFEEEDDDDCCCCCBBBBBBAAAAAAA'
┌──┬───────┬────────────────────────────────────────────────┐
│28│ABCDEFG│90 148 148 165 8 66 12 204 204 136 136 136 0 0 0│
└──┴───────┴────────────────────────────────────────────────┘
   decompress 28;'ABCDEFG';90 148 148 165 8 66 12 204 204 136 136 136 0 0 0
GFFEEEDDDDCCCCCBBBBBBAAAAAAA

Note

The compressed data might differ between the languages due to the way sorting works on characters with equal frequency. This is not a problem, provided that your decompression code works correctly.

Answer 1

05AB1E, 94 89 71 64 63 61 (29+32) bytes

-25.5 bytes thanks to @ovs.
-2 bytes thanks to @Neil.

Compressor:

ÙΣ¢}R=āεb¦Dgb₄+¦ì}‡¤_9׫8ô¨C,

Try it online or verify all test cases.

Decompressor:

b₁b+€¦J¤Ü[D3£C3+ôć3.$1ìC<Isè?J¤F

First input is integer-list; second input is the string.
Stops the program with an error after it has output the correct result, which is allowed according to the meta.

Try it online or verify all test cases.

Neither of my compressor nor decompressor uses the length.

If the length of the resulting binary-string in the compressor is divisible by 8, it adds a trailing no-op integer to the output-list. (The decompressor obviously still handles both this, and binary-strings that are not divisible by 8, correctly.)

Explanation:

Compressor:

Ù           # Uniquify the characters of the (implicit) input-string
 Σ          # Sort these characters by:
  ¢         #  Their count in the (implicit) input-string
 }R         # After the sort: reverse it so the order is from most to least frequent
   =        # Output this string with trailing newline (without popping the string)
ā           # Push a list in the range [1,string-length] (without popping the string)
 ε          # Map each integer to:
  b         #  Convert it to a binary-string
   ¦        #  Remove its first digit
  Dg        #  Create a copy, and pop and push its length
    b       #  Convert this length to binary
            #  Pad it to length 3 with leading 0s by:
     ₄+     #   Adding 1000
       ¦    #   And then removing the first digit
        ì   #  Prepend this in front of the binary-string we've duplicated
}‡          # After the map: transliterate all sorted unique characters with these
            # strings in the (implicit) input-string
¤           # Push its last digit (without popping the string)
 _          # Invert the boolean (1 becomes 0; 0 becomes 1)
  9×        # Repeat that 9 times as string
    «       # And append it to the big string
     8ô     # Then split it into parts of size 8
       ¨    # Remove the trailing part
        C   # Convert each part from binary to an integer
         ,  # And pop and output it as well

Decompressor:

b           # Convert each integer in the (implicit) input-list to a binary-string
            # Pad each to length 8 with leading 0s by:
 ₁b         #  Pushing 256, and converting it to binary as well: 100000000
   +        #  Adding it to each binary string
    €¦      #  And then removing the first digit of each string
      J     # Join all binary-strings together to a single string
       ¤    # Push its last digit (without popping the string)
        Ü   # And right-strip all those trailing digits
[           # Loop indefinitely:
 D          #  Duplicate the binary-string
  3£        #  Pop the copy, and push its first 3 digits
    C       #  Convert that from binary to an integer
     3+     #  Add 3
       ô    #  Split the binary-string into parts of that size
  ć         #  Extract head; pop the remainder-list and first item separately
   3.$      #  Remove the first 3 digits of this first item
      1ì    #  Prepend a 1
        C   #  Convert it from binary to an integer as well
         <  #  And decrease it by 1
   I        #  Then push the second input-string
    s       #  Swap so the integer is at the top of the stack
     è      #  (0-based) index it into the input-string
      ?     #  Pop and output this character (without trailing newline)
   J        #  And join the remainder-list back to a string
    ¤       #  Push its first character (without popping the string),
            #  which will be either 0, 1, or an empty string
     F      #  Loop that many times, which will error for the empty string to exit the
            #  program

Answer 2

K (ngn/k), 56 + 80 = 136 bytes

Try it online!

compress:{|(2/'8#'0N 8#,/(,/c[3],/:'c:{+!x#2}'!8)e?x;e:>#'=x;#x)}

• {|(...;...;...)} return a (reversed) three item list containing (compressed data; sorted list of characters; length of input)
  • (...;...;#x) get the length of the input string
  • (...;e:>#'=x;...) returns the characters in x sorted by their frequency (descending), storing in e
  • (2/'8#'0N 8#,/(,/c[3],/:'c:{+!x#2}'!8)e?x;...;...) compress the input
    • (,/c[3],/:'c:{+!x#2}'!8) generate all valid (compressed) bit patterns, i.e. (0 0 0;0 0 1 0;0 0 1 1;0 1 0 0 0;...). this code is also used in decompress.
    • (...)e?x index into the bit patterns using the indices in e of each character in x (this ensures the most frequent characters in the input get the shortest compressed codes)
    • 8#'0N 8#,/ convert the compressed input into a list of 8-length chunks, with 8#' ensuring each chunk contains a full 8 values
    • 2/' converts each chunk of 8 bits into a decimal number

decompress:{*x{((*y),x(,/c[3],/:'c:{+!x#2}'!8)?d#t;(d:3+/2/3#t)_t:*|y)}[y]/("";,/+(8#2)\z)}

• x{...}[y]/("";,/+(8#2)\z set up a seeded-do-fold, run for x iterations (the number of characters), fixing y (the sorted list of characters), seeded with a two item list containing (decompressed output;remaining compressed data). each iteration peels off one compressed character. confusingly, within the function, the fixed y becomes x, and the ("";...) becomes y

  • {(...;...)} return a two item list, containing the updated (decompressed output;remaining compressed data)

• to calculate the remaining compressed data:

  • t:*|y store the remaining compressed data in t
  • (d:3+/2/3#t) determine how many bits the next character in the (compressed) input uses, storing in d
  • (...)_t drop this many "bits" from the compressed data

• to calculate the decompressed output:

  • (...)?d#t get the next compressed character, looking up its index in the...
  • (,/c[3],/:'c:{+!x#2}'!8) list of all valid compressed codes
  • (*y),x(...) retrieve the uncompressed character from x, and append it to *y, i.e. the decompressed output

• {*...} return just the first item, i.e. the decompressed string

Answer 3

Charcoal, 71 64 + 32 = 96 bytes

Compressor, 64 bytes:

≔Ｅθ⟦№θιι⟧ηＷ⁻ηυ⊞υ⌈ιＵＭυ⊟ι⭆¹⟦Ｌθ⪫υωＥ⪪⭆Ｅθ⍘⊕⌕υλ !⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ⁸⍘◨λ⁸ !

Try it online! Link is to verbose version of code. Explanation:

≔Ｅθ⟦№θιι⟧η

Pair all of the input characters with their frequency.

Ｗ⁻ηυ

Repeat until all of the pairs have been sorted and deduplicated.

⊞υ⌈ι

Push the highest (i.e. most frequent) remaining pair to the predefined empty list.

ＵＭυ⊟ι

Drop the frequencies from the sorted, deduplicated list.

⭆¹⟦

Stringify the list of...

Ｌθ

... the length of the input, ...

⪫υω

... the concatenation of the characters in descending order of frequency, and:

Ｅθ⍘⊕⌕υλ !

For each character in the input string, find its (1-indexed, so I have to increment) popularity index, and convert it to base 2 using custom digits.

⭆...⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ

For each converted character, add 7 to its length, convert that to base 2 using custom digits, and create a list of that and the converted string. Behead all of the strings and concatenate the bodies.

Ｅ⪪...⁸⍘◨λ⁸ !

Chop the string into substrings of length 8, right-pad the last one, and decode each substring as base 2 using the custom base characters (in particular, right-padding uses spaces, so this has to be the custom base character for 0).

Note that this version of the compressor resolves ties by taking the character with the highest ordinal, rather than the character with the first appearance that the previous version chose. I've updated the input to the decompressor link accordingly.

Decompressor, 32 bytes:

Ｆ⮌ζＦ⁸⊞υ﹪÷ιＸ²κ²⭆θ§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²

Try it online! Link is to verbose version of code.

Ｆ⮌ζ

Loop over the bytes in reverse.

Ｆ⁸

Loop over each bit in reverse.

⊞υ﹪÷ιＸ²κ²

Push the bit to the predefined empty list.

⭆θ

Map over each index, join and implicitly print:

§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²

Pop 3 bits from the list, decode as base 2, pop that many bits from the list, prefix 1, decode as base 2, index into the string (0-indexed, so I have to decrement). (I could have used BaseString and StringMap twice.)

Answer 4

JavaScript (Node.js), 223 + 126 = 349 bytes

Compressor, 223 bytes

s=>[s.length,a=[...new Set(s)].sort(g=(a,b)=>a?1/s.split(a).length-g(b):0),([...s].reduce((q,c)=>q<<3n+(x=(B=BigInt)(31-Math.clz32(i=a.indexOf(c)+1)))|x<<x|B(i)^1n<<x,1n)<<7n).toString(2).match(/\B.{8}/g).map(x=>+('0b'+x))]

Try it online!

How?

Generating the sorted list a[] of unique characters:

a = [...new Set(s)]       // get the array of unique characters
.sort(g = (a, b) =>       // for each pair (a, b) of characters to be sorted:
  a ?                     //   if a is defined:
    1 / s.split(a).length //     compute 1 / (N + 1),
                          //     where N is the number of occurrences of a in s
    - g(b)                //     subtract the result of a recursive call
                          //     with a = b and b undefined
  :                       //   else:
    0                     //     stop the recursion
)                         // end of sort()

Generating the byte stream as a single BigInt:

[...s].reduce((q, c) =>      // for each character c in s, using q as the accumulator:
  q <<                       // left-shift q by:
    3n +                     //   3 + x positions,
    (x = (B = BigInt)(       //   where x is the number of bits required to write ...
      31 - Math.clz32(       //
        i = a.indexOf(c) + 1 //   ... the 1-indexed position i of c in a[]
      )                      //
    ))                       //
  |                          //   bitwise OR with:
  x << x                     //     x, left-shifted by x positions
  |                          //   bitwise OR with:
  B(i) ^ 1n << x,            //     i without the most significant bit
  1n                         //   start with q = 1 to preserve leading 0's
)                            // end of reduce()

Splitting the BigInt into a list of bytes:

(... << 7n)            // left-shift the final result to add 7 trailing 0's
.toString(2)           // convert to binary
.match(/\B.{8}/g)      // split by groups of 8 binary digits, ignoring the 1st one
.map(x => +('0b' + x)) // convert each group back to decimal

Decompressor, 126 bytes

19 bytes saved by @Neil!

(n,a,b)=>(g=s=>n--?a['0b1'+s[S](3,x=2-~('0b'+s[S](0,3)))-1]+g(s[S](x)):'')(b.map(v=>(256+v).toString(2)[S='slice'](1)).join``)

Try it online!

How?

Turning the byte stream into a binary string:

b.map(v =>         // for each byte v in b[]:
  (256 + v)        //  force a leading '1'
  .toString(2)     //  convert to binary
  [S = 'slice'](1) //  remove the leading '1'
).join``           // end of map(); join all strings together

Generating the output:

g = s =>                    // s = binary string
  n-- ?                     // decrement n; if it was not equal to 0:
    a[                      //   pick the next character from a[]:
      '0b1' +               //     the index of the character is 2 ** x + V - 1
      s[S](                 //     where V is defined
        3,                  //     as the x-bit value
        x = 2 -~(           //     whose length x (+3)
          '0b' + s[S](0, 3) //     is stored in the 3 leading bits
        )                   //
      ) - 1                 //
    ] +                     //   end of character lookup
    g(s[S](x))              //   recursive call with all processed bits removed
  :                         // else:
    ''                      //   stop the recursion

Answer 5

Python 3, 190 + 128 = 318 bytes

Saved a whopping 28 41 55 57 82 bytes (and got below 400!) thanks to ovs!!!
Saved 10 bytes thanks to Neil!!!

Compressor

Python 3, 190 bytes

def c(r):j=''.join;s=j(sorted({*r},key=r.count))[::-1];i=s.index;g=j(f'{len(bin(i(c)+1)[3:]):03b}'+bin(i(c)+1)[3:]for c in r)+8*'0';return[int(g[a:a+8],2)for a in range(0,len(g),8)],len(r),s

Try it online!

Decompressor

Python 3, 128 bytes

def d(a,l,s):
 d=''.join(f'{d:08b}'for d in a);r=''
 while len(r)<l:b=3+int(d[:3],2);r+=s[~-int('1'+d[3:b],2)];d=d[b:]
 return r

Try it online!

Decompression uses the original string's length.

Answer 6

Husk, 119 103 95 (55+40) bytes

Edit: -8 bytes thanks to Neil

Compressor (55 bytes):

,₁¹B256ḋS+ö`R0%8_Lṁ!ṁλm+tḋ+8¹(motḋ→½ŀ`^2→))ŀ8m€₁¹
↔Ö#¹u

Try it online!

Decompressor (40 bytes):

mö!²ḋ:1↓3↑I¡λ§,↓↑+3ḋ↑3¹)Ṡ+ö`R0%8_LḋB256⁰

Try it online!

How does it work?

Compressor:

1. Sort letters by frequency (helper function ₁):

↔Ö#¹u

2. Substitute letters by their rank by frequency:

m€₁

3. Genrate prefix-length-code:

ṁ                      ŀ8       # for each integer x from 0 to 7
 λm+                            # join 
    tḋ+8¹                       # zero-padded binary digits of x to
         (motḋ→½ŀ`^2→))         # zero-padded binary digits of 1..x

4. Look-up each prefix-length-code from each letter rank:

ṁ!

5. Pad end with digits to multiple-of-8:

S+ö`R0%8_L

6. Convert from binary to base-256:

B256ḋ

7. And finally pair with letters sorted by frequency:

,₁¹

Decompressor:

1. Convert first argument from base-256 to binary digits:

ḋB256⁰

2. Pad start with digits up to multiple-of-8:

Ṡ+ö`R0%8_L

3. Sequentially get prefix-length-codes:

  ¡λ          )                 # apply function repeatedly:
         3ḋ↑3¹                  # remove first 3 digits & convert to number
    §,↓↑+                       # split remaining list at this position
                                # (this keeps going forever, so the list ends-up
                                # with a lot of empty elements)
↑I                              # finally, just keep the truthy prefixes

4. Convert to each element to a number:

   ↓3                           # discard the first 3 digits
 :1                             # and add a '1' at the start
                                # (equivalent to converting the 3 digits
                                # to a value from binary and adding it: Thanks Neil! )
ḋ                               # and convert it all to a value from binary

5. Look up the letter from second argument:

mö!²

Answer 7

J, 70 + 95 = 165 bytes

Encoder returns length;table;bytes just as in the description. The fill for the last chunk is the last generated bit.

#;[(];[:#.@($~8,~#>.@%8:)@;(~.(128#3+i.8)<@$"0 1#:i.4^5){~i.~)~.\:#/.

Decoder using the exact same format for the input:

>@{.$>@{~&1({~(~.(128#3+i.8)<@$"0 1#:i.4^5)i.l<@{.])"1[:(}.~l=:3+3#.@{.])^:(<_)128,@}.@#:@,>@{:

Try it online!

How it roughly works

Code table that is used in both:

• #:i.4^5 0…1024 in binary.
• 128#3+i.8 repeat every number in 3…11 for 128 times
• <@$"0 for 0…127 take the first 3 digits, for 128…255 take the first 4 digits, …
• ~. take the unique elements of the result.

Encoder:

• ~.\:#/. sort the unique characters in the input based on occurrences. That is the character table.
• (table){~i.~ map input to character table positions and get the corresponding code.
• ($~8,~#>.@%8:)@; concatenate all the codes together and split them into chunks of 8.
• #;…];#.@ convert back to integers and prepend the character table and the length.

Decoder:

• 128,@}.@#:@,>@{ take bytes and convert them back to bits. Have to prepend 128 temporarily to pad the results to 8 bits.
• [:(}.~l=:3+3#.@{.])^:(<_) parse the first 3 bits n, and remove them and the next n bits from the bit array. Do this until the bit array is empty. Return all intermediate results (so starting positions for the codes).
• (table)i.l<@{.] again, parse the starting bits and look them up in the code table.
• >@{~&1({~ and look the index up in the character table.
• >@{.$ trim the output down to the length of the string.

Answer 8

Perl 5, 354 bytes

@c=map{$c=$_;map{sprintf"%0*b%0*b",$c?3:2,$c,$c,$_}0..2**$c-1}0..7;
sub c{$_=pop;my%f;$f{$_}++for/./g;my%c;@c{@f=sort{$f{$b}<=>$f{$a}}keys%f}=@c;y///c,join('',@f),map oct(substr"0b$_".'0'x7,0,10),join('',@c{/./g})=~/.{1,8}/g}
sub d{($l,$f,@i)=@_;@d{@c}=0..255;join'',map$f=~/^.{$d{$_}}(.)/,(join('',map sprintf('%08b',$_),@i)=~/@{[join'|',@c]}/g)[0..$l-1]}

Try it online!

Run this to compress with function c() and decompress with d().

my @c1 = c('Hello World');
my @c2 = c('Code Golf Stack Exchange is a site for recreational programming competitions');
print join('|',@c1)."\n";
print join('|',@c2)."\n";
print "Bytes in 1st compression: ".(@c1-2)."\n";
print "Bytes in 2nd compression: ".(@c2-2)."\n";
print d(@c1)."|\n";
print d(@c2)."|\n";

Output:

11|loredWH |90|0|38|20|70|18
76| oieatrncsmgplfxkhdSGEC|142|80|208|34|147|207|136|138|75|48|68|104|12|194|75|14|32|27|65|33|163|82|3|228|176|180|50|180|37|70|76|37|224|234|201|197|165|182|205|135|3|36|219|168|81|168|201|134|128
Bytes in 1st compression: 6
Bytes in 2nd compression: 49
Hello World|
Code Golf Stack Exchange is a site for recreational programming competitions|

Answer 9

Julia, 331 bytes

p(s)=Meta.parse("0b"*s)
s(n,p)=last(bitstring(n),p)
b(i,n=0,B=2^n)=2B<=i ? b(i,n+1) : s(n,3)s(i-B,n)
c(s,u=sort(unique(s),by=x->count(==(x),s),rev=0<1))=join(u),p.(i.match for i=eachmatch(r".{8}",join(b.(findlast(==(i),u) for i=s))*'1'^7))
d(u,N,s=join(s.(N,8)),n=p(s[1:3]))=u[n<1||2^n+p(s[4:3+n])]*try d(u,0,s[4+n:end])catch;""end

Try it online!

I don't want to separate compression and decompression because I use the functions p and s for both.

c is for compression, returns the sorted letters and the compressed string (missing bits are filled with 1s)

dis for decompression, doesn't need the length of the original string (it discards the last invalid caracter)