2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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, 2013 at 4:14
  • $\begingroup$ @D.W. I have added the table. $\endgroup$
    – Xara
    Oct 26, 2013 at 4:34

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2013 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, 2013 at 6:13
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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