2 ms·

Whenever there are many ways to encode something, there's wasted room in the encoding space :) Not usually a big deal, but when the goal is compression, I think

Whenever there are many ways to encode something, there's wasted room in the encoding space :) Not usually a big deal, but when the goal is compression, I think it's nice if it can be avoided.

toast0 5y ago
Regardless of how you do your RLE, you're almost certainly going to have many ways to encode something: you can almost certainly encode a run of four as two runs of two (you wouldn't want to, of course, but you could). It's not an encoder you tend to use if you want to use the absolute smallest amount of space, it's good if your data has enough repeats to get compression and your encoding/decoding systems are very resource constrained. It makes a nice interview problem because compression is a real problem, but RLE needs almost zero previous knowledge, has many reasonable answers, doesn't have a gotcha solution, and most people haven't done it before. Lots of typically better compression algorithms out there, but I don't think any are suitable for general interview.
- vintermann 5y ago
  Yeah, in a bijective RLE, one needs to take into account that, say, A2A2 can't mean the same as A4. However, since you also want to be able to represent runs longer than 255 (if you're doing it on byte level), you can solve both problems. If you encounter repeated runs of the same literal, just combine them into a bigger number. So A2A2 should be read as "A times (0b00000010 00000010)" whereas A4 should be read as "A times (0b00000100)." There are some subtleties still to make it a bijective code, related to end handling and how to represent variable length numbers uniquely, but it's perfectly possible, and once you get it right it isn't really larger than "regular" RLE. It's an interesting challenge to write bijective encodings. I feel it's a bit like writing quines, you have to keep in mind a thing you usually don't. For quines, "what this does to the text you need to output", for bijective encodings, "what this does for the inverse function". Not saying you should give it as an interview question, though!

Whenever there are many ways to encode something, there's wasted room in the encoding space :) Not usually a big deal, but when the goal is compression, I think it's nice if it can be avoided.

toast0 5y ago

Regardless of how you do your RLE, you're almost certainly going to have many ways to encode something: you can almost certainly encode a run of four as two runs of two (you wouldn't want to, of course, but you could). It's not an encoder you tend to use if you want to use the absolute smallest amount of space, it's good if your data has enough repeats to get compression and your encoding/decoding systems are very resource constrained. It makes a nice interview problem because compression is a real problem, but RLE needs almost zero previous knowledge, has many reasonable answers, doesn't have a gotcha solution, and most people haven't done it before. Lots of typically better compression algorithms out there, but I don't think any are suitable for general interview.

vintermann 5y ago
Yeah, in a bijective RLE, one needs to take into account that, say, A2A2 can't mean the same as A4. However, since you also want to be able to represent runs longer than 255 (if you're doing it on byte level), you can solve both problems. If you encounter repeated runs of the same literal, just combine them into a bigger number. So A2A2 should be read as "A times (0b00000010 00000010)" whereas A4 should be read as "A times (0b00000100)." There are some subtleties still to make it a bijective code, related to end handling and how to represent variable length numbers uniquely, but it's perfectly possible, and once you get it right it isn't really larger than "regular" RLE. It's an interesting challenge to write bijective encodings. I feel it's a bit like writing quines, you have to keep in mind a thing you usually don't. For quines, "what this does to the text you need to output", for bijective encodings, "what this does for the inverse function". Not saying you should give it as an interview question, though!