I'm not quite sure how easy it is to fetch the binary composition of a file, but suppose we have some file with this representation:


We could make 2 arrays.

One which stores the position of the 0s: ['x', '', 'x', 'x', '', '']

And another which stores the position of the 1s (which is simply the opposite of the previous array): ['', 'x', '', '', 'x', 'x']

Then we can persist these two arrays into a file, and voila?

I don't know, is there something i'm not realizing?

I'm not an expert in compression, was just wondering if this would work.

  • 2
    How much space would it take up to store the position of each of the 0's and 1's? – Robert Harvey Jul 21 '14 at 4:51
  • Yeah it depends on the language i guess, for instance a boolean in an array takes one byte in some langauges. I suppose the idea could work if instead of marking each location we entered the starting and ending locations for a particular set of repeating 0s and 1s. I Don't know i guess it was a bad idea hehe – zeroRooter Jul 21 '14 at 4:57
  • 1
    @zeroRooter see Huffman Encoding. – metacubed Jul 21 '14 at 5:15
  • 2
    See also BWT, MTF and then RLE. Also, why would it be difficult to "get a file's binary form"? – Elliott Frisch Jul 21 '14 at 6:35
  • 2
    Also read Pigeonhole principle, which is a tool that can help find loopholes in one's arguments about a compression scheme. – rwong Jul 21 '14 at 11:27

The most compact possible representation of your arrays would be 1 bit per entry. You have two arrays, each of length 6. I.e. your compressed file is 6+6 bits long, while your original file is 6 bits long. This is an increase of 100%.

Also, as @jk pointed out in his comment: your second array is identical to your input data. The first array is identical to the inverse of your input data.

       010011  # original
101100 010011  # 'compressed'

So, not only is your compressed data twice as long, it also contains an exact copy of the original data.

  • additionally one of the arrays is the original file while the other is the complement of the original file – jk. Jul 21 '14 at 11:41

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.