Compress my Malbolge!

Question

Background

Malbolge is truly intriguing language. But programs written in it are also extraordinairly huge (and in some cases, unpostable on PPCG).

Your challenge (shall you accept it) is, to compress and decompress given normalized Malbolge program. Devise your own lossless algorithm. You may compress your data further using an existing algorithm afterwards, but you must cite the algorithm used. You may use dictionaries.

Input

On the input, there will be given (in most cases very long) string, containing only following characters: i</*jpov. Example data:

iooooooooooooooooooooovoooioooipooooo<ooooooooooivojo<<<<<oio*ioooooooooooooooopiooooooooooooooooooo/jpooooooooooo

Example bigger chunk of data, 86 kilobytes big.

Output

Well, not very much to say about it, output depends on the algorithm.

Rules:

• Input taken by your program, compressed, and then decompressed, shall be identical.
• Submissions are scored by the following formula: \$ \frac{Compressed}{Original} \times 100\% \$, applied to the example 86 kilobytes big chunk.
• If a submission abuses the fact that only one example chunk is provided (eg. by hardcoding it), I reserve right to add more example chunks.
• Standard loopholes are forbidden, I/O rules apply.

Note: 7zip with PPMd algorithm manages to compress the code with 2,95% score.

Answer 1

Score with test 1: 38.6%, Score with test 2: 4.9%

Compressor

Jelly, 97 bytes

ṡ2ṢŒɠżQƊ1ị>ɗƇ3NÞḣ8Ṫ€,‘ɼ$€Ẏœṣ;@W}ɗjƭƒ
7©ṛ⁸“i</*jpov”iⱮ’Ç31¡
“i</*jpov”iⱮḅ8b256,ÇĖF€LÞḢL;L};÷/$ʋ,ḷɗ

Try it online!

Decompressor

Jelly, 44 bytes

ḅ256ḃ8
ḣ3s2ṚṣḢ}©¥jƭƒṫ5µṛ®n8Ɗ¿‘
ḢĿị“i</*jpov”

Try it online!

Explanation

Uses two different methods and picks the one with the shortest output.

Method 1: Convert the input from base 8 to base 256 Method 2: Repeatedly finds the 8 most common sublists of length 2 and replaces them with an integer between 8 and 255. The dictionary is stored at the beginning of the output.

The first byte of the output indicates the method used.

Input to compressor is a string of Malbolge. Output is a list of integers between 0 and 255. This could easily be encoded in Jelly’s code page if preferred. Input and output to/from decompressor mirror the compressor.

Answer 2

Retina, 47.25%

I know this is currently uninteresting, but this is still a WIP.

Cheap algorithm to compress Malbolge programs.

ooooooooo
a
oooooooo
b
ooooooo
c
oooooo
d
ooooo
e
oooo
f
ooo
g
j\*
h
jah
k

Decompressor:

a
ooooooooo
b
oooooooo
c
ooooooo
d
oooooo
e
ooooo
f
oooo
g
ooo
h
j\*
k
jah

Explanation

This simply shortens the source by replacing the o's, after noticing that there are too many o's in the Malbolge program. Try compressor online!

Answer 3

This code using standard Python libraries serves as a baseline for other advanced approaches.

Here is the outcomes for common compression algorithms.

Test case 0
Library   Score
gzip      50.000%
bz2       64.912%
lzma      87.719%

Test case 1
Library   Score
gzip      3.908%
bz2       2.968%
lzma      3.826%

PPMd      3.161%

NOTE: The PPMd algorithm score is obtained manually using 7zip to compress Test Case 1 into a zip file using a dictionary size of 16M and word size of 16 on Windows.

Answer 4

///, 0.00116%

Compressor (large test case)

Decompressor (large test case)

Compressor (small test case)

Decompressor (small test case)

Explanation: simple dictionary-based approach. The decompressor performs the same substitions as the compressor, but in reverse order. Note that both these programs take input by concatenating it into the source, as is usual for ///.