Please help

[Joanna]

I think that the idea here is that if someone does not know how to do something he certainly can’t program a computer to do it. 

[q250]

ok 10101011, not 10101001, becouse reasons
just to be sure, that everyone will get it i made N = 8 table
https://en.files.fm/u/p5tmsmtgv7
annswer should be 0101100
lets check it:
10101011
delete from that string from left all zeroes and one one, that one included. in our case none zeroes from left are found, so just delete one one from left: 0101011
N that equal to number of bits of resulting string = size of 0101011 = 7
D10 that equal to that string value in base10, ignoring all zeroes from left = 101011 in decimal = 43
A that equal to 2^N + D10 = 2^7 + 41 = 171
Now add 1 to A, ie A:=A+1 = 172
B that equal to Floor from log(A) base 2 =  Floor(log of (172) base (2) ) = 7
R that equal to R:=A – 2^B = 44
now construct binary text string that equal to R in binary and add as much 0 from left as much it needed to make it overall size equal B.
R in binary = 101100
size of R in binary = 6
how much zeroes needed = B - size of R in binary = 7 - 6 = 1
add them to string R in binary = 0101100
save that resulting answer, ie save 0101100 as binary file

and in reverse:
0101100
N that equal to number of bits of string = 7
D10 that equal to that string value in base10, ignoring all zeroes from left = 101100 in decimal = 44
A that equal to 2^N + D10 = 2^7 + 44 = 172
now subtract 1 from A, ie A:=A-1 = 171
B that equal to Floor from log(A) base 2 = Floor(log of (171) base (2) ) = 7
R that equal to R:=A – 2^B = 171 - 2^7 = 43
now construct binary text string that equal to R in binary and add as much 0 from left as much it needed to make it overall size equal B
R in binary = 101011
size of R in binary = 6
how much zeroes needed = B - size of R in binary = 7 - 1 = 1
add them from left to string R in binary = 0101011
now add to that string one one from left = 10101011
and add even further to left as much zeroes it needed to make overall string size equal to *8* <- that number we save in body of program.
size of that string = size of 10101011 = 8
number of zeroes nedded to be add = 8 - size of that string = 0
add that number of zeroes from left to that string = 10101011
save that resulting answer, ie save 10101011

[gerardus]

I'm lost also. So you start with a 8 bit value and you end up with 7 bits? That would be a 12,5% compression rate?

[Fibonacci]

There is a problem with "bit position" or "output length". It needs to be stored somewhere or the output has to have exactly the same length for every input.

Your table shows that for example 00100100 (8 bits) has output 00111 (5 bits), and you know its 5 bits ON PAPER, but the computer doesnt. Output length varies. If it varies, you need to store the length.


Take 8 bytes (8 bits each) -> compress them -> make them all 7 bits long -> join them all -> split to 7 bytes

So from 8 bytes you make 7. Can you do this?


Eventually an option would be to use very large integer. We need to store "output length", in 1 byte you can store output length for a 256 bit number, in 2 bytes you can store length for a 65536 bit number, so lets use the second option.

Assume you treat the data as a single 65k bits integer, after "compression rountine", how long will be the output? Add 16 bits to it. You still got compression?


To make it easier to understand for you. After you do your compression, convert binary to decimal, and start decompression from decimal number with fixed length of bits. It can be smaller decimal, but with bit length divisible by 8. Also, the output should have always the same length of bits, otherwise add some bits (fixed amount of bits divisible by 8) for storing the length of the output.

You can do the "decompression" becasue you know the compressed bit length.

[q250]

So you start with a 8 bit value and you end up with 7 bits?

in worst case yes, you get string/file at one bit smaller. again its working with ANY arbitrary number of bits, not just 8 bit. but remember, we take file as whole. WHOLE, we dont partition our file, just binary string.

Your table shows that for example 00100100 (8 bits) has output 00111 (5 bits), and you know its 5 bits ON PAPER, but the computer doesnt. Output length varies. If it varies, you need to store the length.

honestly i dont know what is written here. if it about that computer cant store 00101, not 00111, look carefully, ie exatly 5 bit file then wtf? why?
if it about that problem that we need somehow store original size, then i already told that we simply store that number in body of programm. output vares, but input dosent. we put in programm file that exactly equal to some number bits, no more bits, no less, exactly.

You can do the "decompression" becasue you know the compressed bit length.

yes. so?

Take 8 bytes (8 bits each) -> compress them -> make them all 7 bits long -> join them all -> split to 7 bytes
So from 8 bytes you make 7. Can you do this?

no. we dont partion file into bytes, but take it as whole.

[q250]

Take 8 bytes (8 bits each) -> compress them -> make them all 7 bits long -> join them all -> split to 7 bytes

So from 8 bytes you make 7. Can you do this?

i get it what you want to do here. you want to remove one bit from every byte. no, it can not be done in principle. set of all string lenght 8 have size 256, set of all string lenght 7 have size 128, and you want to map
them in one to one correspondence.

[Fibonacci]

Smallest unit to save in a file is 8 bits. So you wont know the exact compressed data size, it must be divisible by 8.

If you compress some large number and the output will not be divisible by 8, then what? Add "dummy bits" at the end and.. save the compressed data size. So the question remains. If you compress a number of 65k bits, add padding (to be divisible by 8), and add 16 bits to store actual compressed bits amount (or 8 bits to store amount of padding bits added), will it be smaller than original data?

If you are lucky and there is padding+16 (or padding+8) "0" bits on the "left" then yes, otherwise not. What are the chances?


Just prove it somehow. Compress 32 bits number multiple times to get 24 bits, 3 bytes can be saved to a file. Then decompress multiple times to get 32 bits from 24 bits.

1 round
           

Code: Pascal  [Select][+][-]

1.             d = 150
2.         input = 10010110
3.    compressed =  0010111
4.  decompressed = 10010110
5.             d = 150

           
2 rounds

Code: Pascal  [Select][+][-]

1.            d = 150
2.         input = 10010110
3.    compressed =  0010111
4.    compressed =     1000
5.  decompressed =    10111
6.  decompressed =   110110
7.             d = 54

Can you make a table for 1 to 8 bits?


Edit: actually dont make this table, no need to. It just cant work.

Look, your words:

delete from that string from left all zeroes and one one, that one included = 100001011000100110001101100100

Now open any file in a hex editor, look at first 8 bits. How many 0s are there? Your compression is "all 0s until 1, including that 1" bits length. You can only save bytes in a file, so you must add padding, so you need to know how many bits were added to make full byte. You cut just few bits and need to add at least 1 byte to a file. In some rare cases you will compress maybe 1 byte.

[q250]

Smallest unit to save in a file is 8 bits. So you wont know the exact compressed data size, it must be divisible by 8.

i check internet, and i think you right. ok, got problem, but we can solve it. for string compression:
find size sring mod 8. if it = 0 then just add 00000000 at end. if not then just do reverse operation on that remainder, ie map all of these strings to string size 8, ie remainder 0 would become 00000001, remainder 1111111 would become 11111110, even get 1 spare value.
for string decompression: do reverse. if we find 00000000 at end then just delete it. if anything else then do on last 8 bits compression, and then decompress whole string. downside compession start only if you manage cutoff more than 9 bits, but if computer in reality works only on bytes, not bits, then it best solution.

[KodeZwerg]

To be honest, from what I do see up to here, this is not a compression, this is just shuffling bits. The actual size never shrink when dealing with byte(s).

[gerardus]

There is no way you can encode every random N-bit value in N-1 or less bits just by shuffling bits.

[q250]

To be honest, from what I do see up to here, this is not a compression, this is just shuffling bits. The actual size never shrink when dealing with byte(s).

it will shrink, but in chuncks. if you manage cutoff 1-8 bit on paper, remember 1 bit garanted, then on practice yes no compression. but if you manage cutoff 9-16 bit on paper, then on practice - 8 bit, for 17-24 is 16 bit reduction and so on.

There is no way you can encode every random N-bit value in N-1 or less bits just by shuffling bits.

for every random N-bit value, it is indeed impossible. but for every, exept two, random N-bit value turns out it is possible. main equation that govern that transormation :
2^N - 2 = summ of 2^N, N:=1 to N-1

[KodeZwerg]

I understand that you can do amazing things on a paper.
On paper I could be a Picasso but this will not make me automagical a computer artist for graphics.
So count in on paper what is given by computer technique, a byte, and there your efford (compression) goes poof into nirvana.
You can try read and write as a continious stream but then you need a mechanism that control how much is possible to "shuffle" your bits, without padding your "shuffle back" wont work so you save, if at all, really not much.
Anyway, I am a fan for compression and like your idea, so when you figured out that there is no way to just store 5 bits (exemplary), I jump back on the train.

[q250]

i did explain how to overcome this problem. take example:
lets say we get 800 bits = 100 bytes long string and want to compress it with these technic. lets say we manage to cutoff 37 bits. so, on paper our file now 763 bits. but as we can save on disc only bytes we need to rewrite this file so his lenght would be number that divisible by 8. so, that what we do. find 763 mod 8 = 3. now take look at that 3 last bits. for example let them be 101. now we rewrite that bits using our decompession and 101 become 00001100. now just save these bits at end of our string instead of 101 and save whole file, now we can do it, becouse overall size of compresed string now is 768 bits = 96 bytes.

[Fibonacci]

lets say we manage to cutoff 37 bits

Again, open any file in a hex editor and check if you can cut 37 bits, you cant. And minimum for this to work is 16 bits. 16 bits cut = 0% compression, after 24 bits cut you saved 1 byte. Chances for first round are ultra low (you will never be able to compress regular text). Chances for another round are 0, so you have ultra low chances to compress something by 1 byte.

[TRon]

There exist lossless bit compression algorithms such as huffman. See also here.

Better read up (a bit more) to catch on