If your encoding format is still flexible, I would suggest a 'classic' (and preferable, IMHO) Run Length Encoding approach (Update: as already suggested, I now see, by RichardK here). (Caution: not tested for runs of 256 or more characters.)

>perl -wMstrict -le
"use constant S => 'iiMMMMMMMMMMoooooooooooooooooooooooMMMMMMMMMMiiiii
+iiiiiiiiiiiiiiiiiiiiiiiiiMMMMM
MMMMMMMMooooooooooooooooooooo';
 print q{'}, S, q{'};
 ;;
 (my $rle = S) =~ s{ ((.) \2{0,254}) }{ chr(length $1) . $2 }xmsge;
 print qq{'$rle'};
 ;;
 (my $s = $rle) =~ s{ (.) (.) }{ $2 x ord $1 }xmsge;
 print qq{'$s'};
 ;;
 die 'encode/decocde failed' if $s ne S;
 print 'encode/decode ok!';
"
'iiMMMMMMMMMMoooooooooooooooooooooooMMMMMMMMMMiiiiiiiiiiiiiiiiiiiiiiii
+iiiiiiMMMMMMMMMMMMMooooooooooo
oooooooooo'
'?i
M?o
M§o'
'iiMMMMMMMMMMoooooooooooooooooooooooMMMMMMMMMMiiiiiiiiiiiiiiiiiiiiiiii
+iiiiiiMMMMMMMMMMMMMooooooooooo
oooooooooo'
encode/decode ok!
[download]

(You may be able to do something a bit more efficient using unpack for the decoding step. I think  s/// is about as efficient as you will get for encoding.)