I have a table in which some values are repeated often as shown in the figure below. I want to encode that table such that it makes use of less memory. I have heard about run length encoding (RLE) but I would like to know if there are any other such encoding techniques or algorithms which can perform better than RLE or their performance is almost equivalent to RLE.

enter image description here

  • 1
    $\begingroup$ I suggest you edit the question to provide more information about the data in the table. The more information you provide, the more likely that someone can suggest something that's a good fit for your particular situation. $\endgroup$ – D.W. Oct 26 '13 at 4:14
  • $\begingroup$ @D.W. I have added the table. $\endgroup$ – Xara Oct 26 '13 at 4:34

There are many general-purpose compression algorithms, for example Lempel-Ziv and its many variants (used for example by gzip), and Burrows-Wheeler (used for example by bzip2). You can just try them on your input and see how well they perform. If your data has particular structure, then it is possible that a dedicated compression algorithm would perform significantly better, but it's hard to tell without knowing more about the structure.

  • $\begingroup$ Suppose I have a file containing paragraph in which many words are repeated.Now if I compress it with LZ77 (basic one) and Gzip then which will perform better in terms of memory accesses to retrieve the decompressed file? $\endgroup$ – Xara Oct 26 '13 at 3:55
  • $\begingroup$ It depends whether you want random access or not. In the latter case, just try it out. In the former, you could try an altogether different algorithm, in which you compress your one table into two tables, one containing all the unique cells, and the actual table pointing at the cells. You will achieve some compression, and random access will be fast. $\endgroup$ – Yuval Filmus Oct 26 '13 at 6:13

For particular, known, and fixed data, there exist any number of custom encoding schemes (In practice, almost certainly specifically designed by the user for this purpose) to optimally represent those data under the encoding scheme. For instance, any encoding scheme for which

your-table => 1

where 1 is an unambiguous encoding would improve over a standard RLE of your data.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.