Squares

[coderJeff]

Yes, they say that. Perhaps they are right. Perhaps they are wrong, and there is a way to compress random data, but even if such a way exists , people in this forum obviously are unable to get it to work, otherwise they wouldn't have told you that it's impossible.

Here's an analogy that relates to the way the original problem has been framed (nothing to do with data compression):
- given some whole number
- all even numbers are evenly divisible by 2
- all odd numbers are not evenly divisible by 2 (always remainder 1)

Given a random whole number:
- 50% chance the number is even (evenly divisible by 2)
- 50% chance the number is odd (not evenly divisible by 2)

Now, how to evenly divide all whole numbers by 2? There must be a way... we just haven't discovered it yet. Right?

Or can we safely conclude that dividing a all whole numbers evenly by 2 (no remainder, no fraction) is impossible?

[coderJeff]

@CoderJeff
...
They said it was impossible , to fly like a bird..
...

I think I have been careful to discriminate between impossible and improbable, but maybe not.

Maybe an analogy will help. It's not precise, but it might help get the point across.

Let's compare flight in air to data compression.

Take a sheet of note paper. Compared to all the many many ways that a sheet of note paper can be arranged, only a few arrangements will actually exhibit the characteristics of flight when tossed.

1) Folded in to an airplane like shape and tossed, it will remain in the air long enough to show low drag, high lift, and overcome the force of gravity for a time.

2) Crumpled in to a ball (and many many other arrangements) and tossed, we see high drag, low lift and behaves more like a projectile. I think would be safe to say that it does not well demonstrate the characteristics of flight.

Now, suppose I have a machine that can randomly arrange a sheet of note paper in every possible configuration, and we test the arrangement for flight:
- Do any arrangements fly? Yes. (very low probability)
- Do any arrangements not fly? Yes. (very high probability)
- Does **every** arrangement fly? No. (impossible, because most don't)
- Does **every** arrangement **not** fly? No. (impossible, because a few do)


Let's now relate that to data compression.

For a given compression algorithm, given a random arrangement of bits:
- Do any arrangements compress? Yes. (very low probability)
- Do any arrangements not compress? Yes. (very high probability)
- Does **every** arrangement compress? No. (impossible, because most don't)
- Does **every** arrangement **not** compress? No. (impossible, because a few do)

[angros47]

If you want a proof that compressing EVERY random data set is impossible, I can prove it using reductio ad absurdum, or proof by contradiction.

Let's demonstrate if:

We will define a compression algorithm as an algorithm that takes a dataset A as input, and emits a dataset B that is always:
-shorter than dataset A (compressing it means reducing its size)
-sufficient to reconstruct the dataset A perfectly, with no need of further information, by using the same decompression algorithm (so, compression is lossless)

Now, the question is: is there a compression algorithm that can compress every possible data set?

Let's assume such an algorithm exists: it can take a dataset A, and produce a smaller dataset B. By definition, B is smaller than A.
Since the algorithm can (according to the hypothesis) work with every data set, it can also accept B as input, and produce a dataset C, that is smaller than B (and since B is smaller than A, C must be smaller than A).
Since C allows to reconstruct B, and B allows to reconstruct A, it means that C allows to reconstruct A.

By repeating the compression many times, it is possible to reduce the size of the dataset every time, until we reach the minimum possible size: and the minimum possible size for an information is a single bit. (if the algorithm can compress every dataset to a smaller one, it must be able to compress a dataset of two bits, too, and the only possible dataset smaller than two bits is a single bit).

So, a single bit should be able to represent unambiguously the initial dataset A. Since a bit can have only two possible values, only two datasets can be represented by it, but this is clearly in contradiction with the hypothesis, that assumed every dataset could be compressed. So, the hypothesis must be wrong: if it were true, it would lead to consequences that would contradict it.

[albert]

3 bits in ( 0 to 7 )

if 1 + 1
if 1 + 10
if 1 +11
+ 0

Combos:

0 = 0
1 = 10
2 = 100
3 = 110
4 = 1100
5 = 1110
6 = 10110
7 = 110110

There is no 00 or 01.

So if you run into 0's then you know its all 0's.
If you run into a 01 the you know it's a 10 1.

There's the possibility of a 10 , 0 being mistaken for a 100 ?
There's the possibility of a 11 , 0 being mistaken for a 110 , 0 ?

I'll put it into the test bed , to see what the strings look like..

In my experience with random data all combos are equally likely.. there's a almost even mix of all values..

[angros47]

In my experience with random data all combos are equally likely.. there's a almost even mix of all values..

True. If they weren't, data would not be truly random any more. And that's why they cannot be compressed: all compression algorithms work on the assumption that some combos are more common than others: Huffman compression, for example, uses shorter bit sequences for characters that appear more often in a text, and longer sequences for less used characters: for that reason, it will never work if all characters appear in the text with the same frequency.

[albert]

For 3 bits in:

if 1 + 1
if 1 + 01
if 1 + 11
+ 0

Combos:

0 = 0
1 = 10
2 = 010
3 = 110
4 = 1010
5 = 1110
6 = 01110
7 = 101110

There's no combos that equal others , and it doesn't compress.

Back to the drawing board...

I'll try stepping by 32 bits , and 64 bits.

[angros47]

Albert, why do you keep posting here your efforts, since you are not listening at all at what people replied to you?

[albert]

@angros47

Most of my posts are directed to Richard and Dodicat or both.

Why do other people reply? and complain?
You don't have to click on "Squares"... It's your choice.

Sometimes Richard is a great help , otherwise , he replies with sarcasm. Then i know it's a failure.
Dodicat has been a great help.. If he doesn't like my question , or can't answer it , he just doesn't reply. ( that's what others should do )

[albert]

As far as compression goes:

0
01
10
11

00
01
10
1

Both will compress... So it works... It's a success.. lossless compression accomplished..

But it can't be decompressed...

'Cause i haven't been able to tell where the single 0 or 1 is located in the output string..

So far no one else has any clue as to how to decompress it... It's not a failure... just can't be undone yet..

[albert]

@Dodicat

This compresses:

For 3 bits in : ( Identifying the set bits. )

000 = 3
001 = 0 , bit 1 set
010 = 1 , bit 2 set
011 = 10 , bits 2 and 1 set
100 = 2 , bit 3 set
101 = 20 , bits 3 and 1 set
110 = 21 , bits 3 and 2 set
111 = 210 , bits 3 and 2 and 1 are set

I can't figure out how to end the set. If you use 4 to end each set , it doesn't compress. ( and you have to step the output , by 2 digits , instead of 3 )

The highest value you can have = 3333 , = 12 bits in , and 11 11 11 11 = 8 bits out or another way is ( "&O" + 333 ) stepping by 3 digits.

[dodicat]

Albert.
Getting away from compression for a bit, I have the same problem with fbide on Linux, only graphics code will [quick] run from the ide.
fbedit has exactly the same problem.(all in wine).
To get a console just
wine cmd
You can navigate around the file system (Linux and all).
But Linux files won't run (fbc, gedit . . .)
Wine seems to operate inside it's own cocoon (I think sandbox is computer jargon).
My own little quickrunner does the job OK, but it is no fun coding in notepad after years of fbide and highlighted keywords.
But If I am using Linux I would prefer to use the Linux fb distro anyway, so it all a bit of an experiment in my case.

I was watching a TV program last night, a Sky at Night question time.
There were 4 professors answering questions from a small dedicated audience about the cosmos.
I don't believe a word these boffins say of course, but I was reminded of your compressor journey when they were blabbering on about the death of a star,( they actually gave the impression that they knew all about these things)!.
Seemingly the star goes from the sudden pre death expansion to a red, brown or white dwarf (compression) then further compression to a neutron star and when the neutron can no longer withstand the gravitational force it finally compresses into a black hole.
But this black hole has all the information on it's surface, that is the information to decompress stage by stage back to it's star state at any time.
The black hole surface information is akin the seashell which tells you the story of the ocean (encrypted of course), if you put it to your ear.
I believe in the seashell, not the boffins.

[albert]

@Dodicat

I don't believe you can have a neutron star.. The probability , is just too vast.

I think there's an ether , and it eddies into particles and the elasticity of the ether pulls the particles together to make atoms and then the elasticity pulls the atoms together to make molecules.

Maybe the ether is "GOD" , "YHWH" , and he creates the eddies in himself , that make up the particles and atoms.

So ; God created the universe out of himself. We all reside within the God...

=============================================================================
I was playing around with my "Time Rhyme" program idea.. making little sayings of the numbers..
1 = fun gun bun done
2 = blue blew new knew too do chew jew screw
3 = she free key bee sea ,,, I thought it might make a good radio or tv station name KEBC = "key bee sea"

[albert]

@Dodicat

This one ; doesn't know if it wants to compress or not..

Just keep pressing a key and watch the numbers..

Code: Select all

Declare Function   compress_loop( chrs as string ) as string
Declare Function decompress_loop( chrs as string ) as string


Namespace Zlibrary

#inclib "zlib"
Extern "C"
    Declare Function compressBound(Byval sourceLen As Ulong) As Ulong
    Declare Function uncompress(Byval dest As Ubyte Ptr, Byval destLen As Uinteger Ptr, Byval source As  Ubyte Ptr, Byval sourceLen As Ulong) As Long
    Declare Function compress(Byval dest As Ubyte Ptr, Byval destLen As Uinteger Ptr, Byval source As  Ubyte Ptr, Byval sourceLen As Ulong) As Long
End Extern

Function getpassedinfo(text As String,Byref passed_length As Integer) As String
    Dim As String var1,var2
    Dim As Integer pst
    #macro splice(stri,char,var1,var2)
    pst=Instr(stri,char)
    var1="":var2=""
    If pst<>0 Then
        var1=Mid(stri,1,pst-1)
        var2=Mid(stri,pst+1)
    Else
        var1=stri
    End If
    #endmacro
    splice(text,"|",var1,var2)
    text=var2
    passed_length=Valint(var1)
    Return text
End Function


'=================   UNPACK ===============
Function unpack(file As String) As String
    Dim As Integer passed_length
    Dim As String text=getpassedinfo(file,passed_length)
    Dim As Integer stringlength,destinationlength
    stringlength=Len(text)
    destinationlength =passed_length
    Dim As Ubyte Ptr source
    Dim As Ubyte Ptr  destination =Callocate(destinationlength,1)
    source=@text[0]
    Var mistake=uncompress(destination,@destinationlength, source, stringlength)
    If mistake<>0 Then Print "There was an error":Sleep:End
    Dim As String uncompressed
    uncompressed=String(destinationlength,0)
    For i As Integer = 0 To destinationlength- 1
        uncompressed[i]=(destination[i])
    Next
    Deallocate destination
    Return uncompressed
End Function

'===================  PACK ============
Function pack(file As String) As String
    Dim As String text=file
    Dim As Integer stringlength,destinationlength
    stringlength=Len(text)
    destinationlength = compressBound(stringlength)
    Dim As Ubyte Ptr source
    Dim As Ubyte Ptr destination =Callocate(destinationlength,1)
    source=@text[0]
    Var mistake=compress(destination, @destinationlength, source, stringlength)
    If mistake <>0 Then Print "There was an error"
    Dim As String compressed
    compressed=String(destinationlength,0)
    For n As Integer=0 To destinationlength-1
        compressed[n]=destination[n]
    Next n
    compressed=stringlength &"|"+compressed
    Deallocate destination
    Return compressed
End Function

End Namespace


'==================================================================
'==================================================================
'test zipper
'==================================================================
'==================================================================
screen 19

Dim Shared As String s

Randomize

s=""
dim as string check=""
dim as string compare=""
dim as longint length = 0
dim as double compression = 0
dim as longint loops = 0
do
   
    loops+=1
   
    'one time run , create initial string
    if loops = 1 then
        For n As Long = 1 To 10000
            s+=chr(Int(Rnd*256))'+48
        Next
        compare =  s
        length = len(s)
    else
        'modify compression to make further compression possible
       
        s = compress_loop(s)
       
    end if
    check = s
    compression = (100 - ( 100 / ( length / len(check) ) ))
   
    Print "original string"
    Print Len(s)
    Print
   
    Dim As String compressed=Zlibrary.pack(s)
    s = compressed
   
    Print "packed string "
    Print Len(compressed)
    Print
   
    Dim As String uncompressed=Zlibrary.unpack(compressed)
   
    Print "Retrieve"
    Print Len(uncompressed)
    Print
    'Print "compression ratio  "; 100 - ( 100 / ( Len(s) / len(compressed) ) ) ; "%"
    Print "compression ratio  "; 100 - ( 100 / ( length / len(s) ) ) ; "%"
    Print Iif(uncompressed=check,"OK","ERROR")
    Print "-------------------------------"
   
    'sleep 1000
   
    'if loops > 2 and (100 - ( 100 / ( length / len(s) ) )) < compression then exit do
   
    print "press a key for next compression." ; " loops = " ; loops ; " out of 100."
    print
    print "press esc to exit."
    sleep
   
    if inkey = chr(27) then exit do
   
loop until loops = 100

print "Press a key to decompress."
sleep

s = str(loops) + "_" + s ' save as an output file...

'==================================================================
'decompress
'==================================================================
dim as longint dec = instr(1,s,"_")
dim as longint count = val(left(s,dec-1))
dim as string comp = mid(s,dec+1)
dim as string val1
dim as string outs
for a as longint = count to 2 step -1
    s = Zlibrary.unpack(comp)
    outs = decompress_loop(s)
    comp = outs
next

comp = Zlibrary.unpack(comp)

print
print "input = "; length , "output = " ; len(comp) , "compression ratio  "; 100 - ( 100 / ( length / len(s) ) ) ; "%"
print
if comp = compare then print "Decompression successful." else print "ERROR"
print
Print "!!~~Done~~!!"

Sleep
end
'===============================================================================
'============================,===================================================
'begin functions
'===============================================================================
'================='==============================================================
Function compress_loop( chrs as string ) as string
    
    print "c inp = " ; len(chrs) ' , chrs
    
    dim as string outs = ""
    dim as string zeros = string( 8 , "0" )
    dim as string n1
    for a as longint = 1 to len( chrs ) step 1
        n1 = zeros + bin( chrs[ a - 1 ] )
        outs+= right( n1 , 8 )
    next
    
    dim as string outs1 = ""
    dim as string outs2 = ""
    for a as longint = 1 to len( outs ) step 3
        
        n1 = mid( outs , a , 3 )
        
        if val( "&B" + n1 ) < 4 then outs2+= "0"
        
        if n1 = "000" then outs1+= "0"
        if n1 = "001" then outs1+= "1"
        if n1 = "010" then outs1+= "2"
        if n1 = "011" then outs1+= "3"
        
        if n1 = "100" then outs2+= "1"
        if n1 = "101" then outs2+= "10"
        if n1 = "110" then outs2+= "2"
        if n1 = "111" then outs2+= "3"
    
    next
    
    print "c out = " ; len(outs1) ' , outs1
    print "c out = " ; len(outs2) ' , outs2
    
    dim as string final = ""
    dim as string s , n
    for a as longint = 1 to len( outs1 ) step 4
        s = mid( outs1 , a , 4 )
        n=""
        n+= right( "00" + bin( val( mid( s , 1 , 1 ) ) ) , 2 )
        n+= right( "00" + bin( val( mid( s , 2 , 1 ) ) ) , 2 )
        n+= right( "00" + bin( val( mid( s , 3 , 1 ) ) ) , 2 )
        n+= right( "00" + bin( val( mid( s , 4 , 1 ) ) ) , 2 )
        final+= chr( val( "&B" + n ) )
        'final+= chr( val( "&B" + mid( outs1 , a , 8 ) ) )
    next
    final+= "END"
    for a as longint = 1 to len( outs2 ) step 4
        s = mid( outs2 , a , 4 )
        n=""
        n+= right( "00" + bin( val( mid( s , 1 , 1 ) ) ) , 2 )
        n+= right( "00" + bin( val( mid( s , 2 , 1 ) ) ) , 2 )
        n+= right( "00" + bin( val( mid( s , 3 , 1 ) ) ) , 2 )
        n+= right( "00" + bin( val( mid( s , 4 , 1 ) ) ) , 2 )
        final+= chr( val( "&B" + n ) )
        'final+= chr( val( "&B" + mid( outs1 , a , 8 ) ) )
    next
    
    print "c fin = " ; len(final)
    
    return final
    
end function
'===============================================================================
'============================================================================
Function decompress_loop( chrs as string ) as string
    
    return chrs
    
end function

[albert]

@Dodicat

This one compresses... Not sure how..

Can you look over the code , to see if i have an error somewhere?

I figured that 1,000,000 bytes in , has all 65,536 values , so it shouldn't compress , but it does.. ( takes like 5 minutes per loop. )
But 1,000,000 bytes in compresses to under 930,000 on loop one.

Compresses 6% to 8% on loop 1

See: compress_loop()

Code: Select all

Declare Function   compress_loop( chrs as string ) as string
Declare Function decompress_loop( chrs as string ) as string


Namespace Zlibrary

#inclib "zlib"
Extern "C"
    Declare Function compressBound(Byval sourceLen As Ulong) As Ulong
    Declare Function uncompress(Byval dest As Ubyte Ptr, Byval destLen As Uinteger Ptr, Byval source As  Ubyte Ptr, Byval sourceLen As Ulong) As Long
    Declare Function compress(Byval dest As Ubyte Ptr, Byval destLen As Uinteger Ptr, Byval source As  Ubyte Ptr, Byval sourceLen As Ulong) As Long
End Extern

Function getpassedinfo(text As String,Byref passed_length As Integer) As String
    Dim As String var1,var2
    Dim As Integer pst
    #macro splice(stri,char,var1,var2)
    pst=Instr(stri,char)
    var1="":var2=""
    If pst<>0 Then
        var1=Mid(stri,1,pst-1)
        var2=Mid(stri,pst+1)
    Else
        var1=stri
    End If
    #endmacro
    splice(text,"|",var1,var2)
    text=var2
    passed_length=Valint(var1)
    Return text
End Function


'=================   UNPACK ===============
Function unpack(file As String) As String
    Dim As Integer passed_length
    Dim As String text=getpassedinfo(file,passed_length)
    Dim As Integer stringlength,destinationlength
    stringlength=Len(text)
    destinationlength =passed_length
    Dim As Ubyte Ptr source
    Dim As Ubyte Ptr  destination =Callocate(destinationlength,1)
    source=@text[0]
    Var mistake=uncompress(destination,@destinationlength, source, stringlength)
    If mistake<>0 Then Print "There was an error":Sleep:End
    Dim As String uncompressed
    uncompressed=String(destinationlength,0)
    For i As Integer = 0 To destinationlength- 1
        uncompressed[i]=(destination[i])
    Next
    Deallocate destination
    Return uncompressed
End Function

'===================  PACK ============
Function pack(file As String) As String
    Dim As String text=file
    Dim As Integer stringlength,destinationlength
    stringlength=Len(text)
    destinationlength = compressBound(stringlength)
    Dim As Ubyte Ptr source
    Dim As Ubyte Ptr destination =Callocate(destinationlength,1)
    source=@text[0]
    Var mistake=compress(destination, @destinationlength, source, stringlength)
    If mistake <>0 Then Print "There was an error"
    Dim As String compressed
    compressed=String(destinationlength,0)
    For n As Integer=0 To destinationlength-1
        compressed[n]=destination[n]
    Next n
    compressed=stringlength &"|"+compressed
    Deallocate destination
    Return compressed
End Function

End Namespace


'==================================================================
'==================================================================
'test zipper
'==================================================================
'==================================================================
screen 19

Dim Shared As String s

Randomize

s=""
dim as string check=""
dim as string compare=""
dim as longint length = 0
dim as double compression = 0
dim as longint loops = 0
do
   
    loops+=1
   
    'one time run , create initial string
    if loops = 1 then
        For n As Long = 1 To 10000
            s+=chr(Int(Rnd*256))'+48
        Next
        compare =  s
        length = len(s)
    else
        'modify compression to make further compression possible
       
        s = compress_loop(s)
       
    end if
    check = s
    compression = (100 - ( 100 / ( length / len(check) ) ))
   
    Print "original string"
    Print Len(s)
    Print
   
    Dim As String compressed=Zlibrary.pack(s)
    s = compressed
   
    Print "packed string "
    Print Len(compressed)
    Print
   
    Dim As String uncompressed=Zlibrary.unpack(compressed)
   
    Print "Retrieve"
    Print Len(uncompressed)
    Print
    'Print "compression ratio  "; 100 - ( 100 / ( Len(s) / len(compressed) ) ) ; "%"
    Print "compression ratio  "; 100 - ( 100 / ( length / len(s) ) ) ; "%"
    Print Iif(uncompressed=check,"OK","ERROR")
    Print "-------------------------------"
   
    'sleep 1000
   
    'if loops > 2 and (100 - ( 100 / ( length / len(s) ) )) < compression then exit do
   
    print "press a key for next compression." ; " loops = " ; loops ; " out of 100."
    print
    print "press esc to exit."
    sleep
   
    if inkey = chr(27) then exit do
   
loop until loops = 100

print "Press a key to decompress."
sleep

s = str(loops) + "_" + s ' save as an output file...

'==================================================================
'decompress
'==================================================================
dim as longint dec = instr(1,s,"_")
dim as longint count = val(left(s,dec-1))
dim as string comp = mid(s,dec+1)
dim as string val1
dim as string outs
for a as longint = count to 2 step -1
    s = Zlibrary.unpack(comp)
    outs = decompress_loop(s)
    comp = outs
next

comp = Zlibrary.unpack(comp)

print
print "input = "; length , "output = " ; len(comp) , "compression ratio  "; 100 - ( 100 / ( length / len(s) ) ) ; "%"
print
if comp = compare then print "Decompression successful." else print "ERROR"
print
Print "!!~~Done~~!!"

Sleep
end
'===============================================================================
'============================,===================================================
'begin functions
'===============================================================================
'================='==============================================================
Function compress_loop( chrs as string ) as string
    
    print "c inp = " ; len(chrs) ' , chrs
    
    dim as string outs = string( len( chrs ) , chr( 0 ) )
    dim as string check = string( len( chrs ) , "-" ) 
    dim as string n1
    dim as longint place
    dim as longint num = 65536
    for a as longint = 0 to 255
        for b as longint = 0 to 255
            
            num-= 1
            
            n1 = chr(a) + chr(b)
            
            place = 0
            do
                
                place = instr( place + 1 , chrs , n1 )
                
                if place > 0 then
                    if place mod 2 = 1 then
                        mid( chrs , place , 2 ) = "--"
                        mid( outs , place , 2 ) = mkshort( num )
                    end if
                end if
            
            loop until place = 0
        
            if chrs = check then goto done
            
        next
    next
    
    done:
    
    print "c out = " ; len(outs) ' , chrs
    
    dim as string final = outs
    
    print "c fin = " ; len(final)
    
    return final
    
end function
'===============================================================================
'============================================================================
Function decompress_loop( chrs as string ) as string
    
    return chrs
    
end function

[albert]

@Dodicat

I found out why it was compressing...

if place > 0 then
if place mod 2 = 1 then
mid( chrs , place , 2 ) = "--"
mid( outs , place , 2 ) = mkshort( num )
end if
end if


mid( chrs , place , 2 ) = "--" ,
when the input , gets to "--" , is why it was compressing ,
If , you take the mid ="--" , out , it doesn't compress.