COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

Compression bit by bit ,minor correction

• Email
• Follow

```This is a repost, with a minor correction. I have not coded this
but it is clearly evident that it works, although I intend to code
this shortly. I have also done some independent thinking on hashing
where some methods yield compression but seem to require massive
computation on large numbers. I have another simpler idea but am
not sure whether it yields compression. It is clear that both the
theoretical and practical limit of compression is pretty much
limitless, and entropy must be determined as a lower bound and not
as an upper bound.

This is for coding a binary sequence. Let n be the length of the
sequence and r the number of 1's in it.

In regular binary encoding, the individual bit positions are assigned
fixed weights. Since compression is desired therefore

1) The weights assigned must be variable , and

2) The weight of any position must only be dependent on the number of
one's so far or r.

Clearly if there are r 1's in a sequence of length n, the weight of
the n+1'th position will be

w = (2^(r-1))(n - r), where ^ is exponentiation.

Posted using www.webuse.net

Posted using www.webuse.net
```
 0

See related articles to this posting

```daydreamer wrote:
> I have not coded this but it is clearly evident
> that it works, although I intend to code
> this shortly.

I think at least half of the threads to
comp.compression start like this.
```
 0

```daydreamer wrote:
) This is for coding a binary sequence. Let n be the length of the
) sequence and r the number of 1's in it.
)
) In regular binary encoding, the individual bit positions are assigned
) fixed weights. Since compression is desired therefore
)
) 1) The weights assigned must be variable , and
)
) 2) The weight of any position must only be dependent on the number of
)    one's so far or r.

3) Therefore, you have to send the value of r beforehand, which takes more
bits than what you'll save with the subsequent compression.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
```
 0

```Willem <willem@turtle.stack.nl> wrote:

> daydreamer wrote:
> ) This is for coding a binary sequence. Let n be the length of the
> ) sequence and r the number of 1's in it.
> )
> ) In regular binary encoding, the individual bit positions are assigned
> ) fixed weights. Since compression is desired therefore
> )
> ) 1) The weights assigned must be variable , and
> )
> ) 2) The weight of any position must only be dependent on the number of
> )    one's so far or r.
>
> 3) Therefore, you have to send the value of r beforehand, which takes more
>    bits than what you'll save with the subsequent compression.
>
>
> SaSW, Willem

Hello,
The value of r is at most 32 bits for a sequence of length 2^32
bits, and r is always <= n /2. No offence to the mad hatter.
It is rudimentary mathematics. Kindly stop misguiding and misleading
people. Have you even tried it. The idea is phenomenal, so please
stop the misinformation.

Posted using www.webuse.net
```
 0

```daydreamer wrote:
) Willem <willem@turtle.stack.nl> wrote:
)
)> daydreamer wrote:
)> ) This is for coding a binary sequence. Let n be the length of the
)> ) sequence and r the number of 1's in it.
)> )
)> ) In regular binary encoding, the individual bit positions are assigned
)> ) fixed weights. Since compression is desired therefore
)> )
)> ) 1) The weights assigned must be variable , and
)> )
)> ) 2) The weight of any position must only be dependent on the number of
)> )    one's so far or r.
)>
)> 3) Therefore, you have to send the value of r beforehand, which takes more
)>    bits than what you'll save with the subsequent compression.
)>
)>
)> SaSW, Willem
)
) Hello,
)     The value of r is at most 32 bits for a sequence of length 2^32
) bits, and r is always <= n /2. No offence to the mad hatter.

Which is roughly the number of bits you can save on average with your
method.  Do the maths and stop handwaving about 'rudimentary mathematics'.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
```
 0
Reply willem5 (84) 3/3/2011 5:01:43 PM

```On Mar 4, 12:01=A0am, Willem <wil...@turtle.stack.nl> wrote:
> daydreamer wrote:
> ) Hello,
> ) =A0 =A0 The value of r is at most 32 bits for a sequence of length 2^32
> ) bits, and r is always <=3D n /2. No offence to the mad hatter.
>
> Which is roughly the number of bits you can save on average with your
> method. =A0Do the maths and stop handwaving about 'rudimentary mathematic=
s'.

2^n =3D sum C(n,k)
-- Omar Khayy=E1m

Up from Earth's Centre through the seventh Gate
I rose, and on the Throne of Saturn sate,
And many Knots unravel'd by the Road;
But not the Knot of Human Death and Fate.
-- Omar Khayy=E1m

HTH.
James Dow Allen
```
 0
Reply jdallen2000 (495) 3/3/2011 6:24:16 PM

5 Replies
214 Views

Similar Articles

12/13/2013 12:08:44 PM
page loaded in 4834 ms. (0)

Similar Artilces:

compression bit by bit
This is for coding a binary sequence. Let n be the length of the sequence and r the number of 1's in it. The sequence is called X and the bits are numbered from 0-n-1, from right to left, so the individual bits from right to left are X[0], X[1],..... In regular binary encoding, the individual bit positions are assigned fixed weights. Since compression is desired therefore 1) The weights assigned must be variable , and 2) The weight of any position must only be dependent on the number of one's so far or r. Clearly if there are r 1's in a sequence of length n, the weight ...

bits of this, bits of that
Hi, I need to write some data types into an array of unsigned chars. These are basically "signals" within a message, so each signal will have a start bit and a length. The signals will also have a type, one of: unsigned long signed long float double The signals with float and double will be 32 or 64 bits long, as appropriate. I need to just shift the bits and throw them into the array, untouched. Whats the best way of doing this? Since I can't bit shift a float around, I was thinking of a union of the 4 types, and doing all the bit twiddling using the ...

Need a bit of information about Compression
Well i have done quite a good amount of research in compression methods and stuff but currently i am in a fix so i was hopeing to get my self out of it with your help. What my question is that "What is the best possible method to compress a file that only has 3 different Chr and one of them repeates alot?" for example File = "///1/////1/2//////2///21/////1/2/12//1/12/1/21/2/212121///////////12/////////12/////1/1///1///1//1//11/2//" a file with random letter place some what like this should be able to compress alot right since there are only 3 different Chr so as per the...

Compress a subset of bits form
Hi! What is the best algorithm to compress the information, where a want to point out a subset of 16 bits from 128 bits. a give one example where a only use a subset of only 4 bits from the 128, we say we have a packet of 128 bits, now a want to use the bit in place 6, 45, 68, 120, how can a describe these places with a less bits as possibly? a do not want to use 7 * 4 bits /Ulf Ulf wrote: ) Hi! ) What is the best algorithm to compress the information, where a want to ) point out a subset of 16 bits from 128 bits. a give one example where a ) only use a subset of only 4 bits from the 128, ...

compressing 1-bit music
hello everyone. Lately, I've been developing lots of 1-bit music for aesthetic characteristics, but it occurred to me last night that it must be very compressible, too. I'm looking for the *program* not the algorithm to do it. As some might realize, "real-life" music (possibly dithered and) quantized to 1-bit would not be very compressible, but my music consists of techno-like loops of waveforms consisting of 1's and 0's of varying lengths. There are some effects like 1-bit comb filters and 1-bit ring modulation which make more complex waveforms, but still lots ...

Compression on a 8 bit micro
I'm using a 8 bit micro and i need an efficient algorithm for bi-level images (that after the decompression can be visualized by an lcd).I think an RLE compression, but the compression rate is low, so i'm searching a better compression algorithm. Any suggestions? Thanks lionelgreenstreet@gmail.com writes: > I'm using a 8 bit micro and i need an efficient algorithm for bi-level > images (that after the decompression can be visualized by an lcd).I > think an RLE compression, but the compression rate is low, so i'm > searching a better compression algorithm. Any sugg...

Need help in compressing 512 bit sequence.
Hello all, I have a 512 bit sequence that contains 100 set bits. This gives a 19.5 : 80.5 ratio of "1" to "0". What is the best method to use to compress the 512 bit sequence to a new sequence that approaches a 1:1 ratio. Ideally the best case should give a 200 bit sequence output with a small book-keeping index (hopefully 56 bits which would give me 256 bits to clear up other overhead data.) Someone here has probably encountered this problem before and has a solution at hand. A quick solution will save me months of thought. If there is no solution I must know so that I ...

8 bit LZW Compressed TIFF image to PDF conversion
Hi , I have written a C code which converts 8 bit uncompressed Tiff Image to PDF file. Now i am trying for 8 bit LZW compressed Tiff Image. But using the same code i am getting error " A Drawing Error has occured" and then a blank page is displayed. The following are the details : The image is 8 bit LZW compressed image. I have the values Image File Directory ( IFD ). ImageWidth =3D 0x237 , ImageLength =3D 0x1b7 , BitsPerSample =3D 8 , Compression =3D 5 , StripOffsets =3D 0x18 , RowsperStrip =3D 0x0c , StripByteCounts =3D 0x29b84 I have taken ImageWidth as width. ImageLength...

Good software development, a bit like "compression"?
Hows this for a software development idea? Now, good code generally is tight code. The smaller the better, because less code means less bugs. Once you start copy/pasting lines all over the place, you start getting unmaintainable code because you need to fix bugs in every place you've copy/pasted the code! And in general, the idea is to basically "identify patterns" in your code. Where two pieces of code are doing mostly the same thing, so much similar that they can be "refactored" out into their own helper function, which just gets called with different parameters. ...

64-bit and 128 bit integer as a combination of 32-bits
Hi all, How to program 64-bit and 128-bit integers as a combination of 32bits. I need this string to integer conversion. Thank you On Aug 2, 10:51=A0am, xyz <lavanyaredd...@gmail.com> wrote: > > How to program 64-bit and 128-bit integers as a combination of 32bits. > I need this string to integer conversion. > It's easiest in assembler. Instruction sets for 32-bit microprocessors have the ability to access the carry when two numbers are added, or to take the high 32 bits from a multiplication. It's more difficult to achieve this in C. The easiest way ...

Run 32-bit and 64-bit listener at the same time on W3K 64-bit
I have Oracle 10.2.0.4-64 bit running on W3K-64-bit. Now I need to run a 32-bit 9.2.0.5 (yes I know, ouch) on this box. I cannot get the listener to work. I use batch file to specifically point to the 9.2 environment, but for some reason it points to the 64-bit version. Any clues? E:\dbscripts>rem set oracle 9.2 environment E:\dbscripts>set ORACLE_HOME=C:\oracle\ora92 E:\dbscripts>set path=C:\oracle\ora92\bin;C:\WINDOWS\system32;C:\WINDOWS;C:\WINDOWS\System32\Wbem;\\CFOLDC1\fopublic\ E:\dbscripts>set TNS_ADMIN=C:\oracle\ora92\network\admin E:\dbscripts>c: C:\...

16 bit to 32 bit
Hello, Under Windows XP, I run a simple pwd.exe in cmd, the error message looks like this: 16 bit MS-DOC Subsystemm, The system file is not suitable for running MS-DOC and Microsoft Windows applications. NOt sure how to convert cmd from 16 bit to 32 bit to run the pwd.exe etc djgpp compiled program? one2001boy@yahoo.com <one2001boy@yahoo.com> wrote: > Hello, > Under Windows XP, I run a simple pwd.exe in cmd, > the error message looks like this: Please report the *exact* error message. "Looks like" isn't good enough. > 16 bit MS-DOC Subsystemm, The sys...

32-bit or 64-bit
How to check my Sun Solaris is 32-bit or 64-bit. I could not retrieve the information by using uname -a Thanks. blackdog wrote: > How to check my Sun Solaris is 32-bit or 64-bit. I could not retrieve > the information by > using uname -a How about "isainfo -v"? - Logan On Mon, 9 Jan 2006, blackdog wrote: > How to check my Sun Solaris is 32-bit or 64-bit. I could not retrieve As a rule of thumb, if you're running on 64-bit capable HW, you'll be running the 64-bit kernel. WHen in doubt, isainfo -b will confirm one way or another. HTH, -- Rich Teer, SCN...

Hi all. I'm working on something where I need to read a (binary) file bit by bit and do something depending on whether the bit is 0 or 1. Any help on doing the actual file reading is appreciated. Thanks in advance Alfred Bovin wrote: > I'm working on something where I need to read a (binary) file bit by bit > and do something depending on whether the bit is 0 or 1. Well, smallest unit you can read is an octet/byte. You then check the individual digits of the byte using binary masks. f = open(...) data = f.read() for byte in data: fo...

32 bit or 64 bit?
I'm tryin to configure a SAMP server , not sure whether to go for 32 bit or 64 bit . Solaris os 9 Apache 2.2 MySQL 5 PHP 5 And how do i configure all the pre-quesite and the above mentioned packages in 64 bit? Please advise. RajSasidharan@gmail.com wrote: > I'm tryin to configure a SAMP server , not sure whether to go for 32 > bit or 64 bit . > > Solaris os 9 > Apache 2.2 > MySQL 5 > PHP 5 > > And how do i configure all the pre-quesite and the above mentioned > packages in 64 bit? > > Please advise. > My suggestion is to go for Solaris 10...

32-bit or 64-bit
hi, i have two questions: 1) how do i know my processor is 32-bit or 64-bit? 2) Which version of aix (32-bit or 64-bit) running on my system? is there a command equalent of isainfo on solaris? Thanking you, regards, kiran hi, KIRAN MN wrote: > hi, > > i have two questions: > > 1) how do i know my processor is 32-bit or 64-bit? lsconf bootinfo -y (not sure about is this is proc or kernel) lsattr -El proc0 > 2) Which version of aix (32-bit or 64-bit) running on my system? ls -la / unix -> /usr/lib/boot/unix_64 --> means 64 Bit-Kernel > > is ...

96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor 64-bit division, etc.
Hi, To effectively solve a research problem, I need a very fast (sub-microsecond, if possible) method to determine whether one 96-bit integer is an exact multiple of another 96-bit integer. The high-level application is mostly written in Perl and is intended to be portable, but right now I am concentrating on the hardware that I have in-hand, which include 2.4 GHz Xeons, a 1.8 GHz Athlon64 ("3000+), a 1.8GHz Pentium M, and a Mac with a G5 CPU (sorry, I don't know the CPU speed). The x86s (except for the Pentium M) are running Linux, the Pentium M is running Windows XP and the Mac i...

32 bit or 64 bit? #3
I'm tryin to configure a SAMP server , not sure whether to go for 32 bit or 64 bit . Solaris os 9 Apache 2.2 MySQL 5 PHP 5 And how do i configure all the pre-quesite and the above mentioned packages in 64 bit? Please advise. ...

Porting 16 bit to 32 bit
Years ago I wrote an app in VB 4.0 16 bit. The program is still selling, but the clients want to upgrade to 32 bit. Should I go for VB 4.0 32 bit, or version 5, or version 6? There is only a tiny budget for this, and I don't want to do any rewrites so VB.NET is out! Also, are there any "gotchas" that I need to be aware of? many thanks in advance and sorry if this question has been asked and answered before - I did a search and couldn't find anything. Edward Edward wrote: > Years ago I wrote an app in VB 4.0 16 bit. The program is still > selling, but the clients...

8 bit/16 bit data
Will Gimp support 16 bit tiff data in the near future? Win XP Pro + Gimp 2,2 On Tue, 2007-01-02 at 23:42 +0000, David Vincent-Jones wrote: > Will Gimp support 16 bit tiff data in the near future? > > Win XP Pro + Gimp 2,2 > > Um. No real way to tell. The developers have been talking about including GEGL into GIMP, which should give that capability and more, but that's been in discussion for several years now. If you're prepared to accept a decrease in the list of tools, you can use Gimp's bastard offspring, cinepaint. ( http://www.cinepaint.org/ ) Hopefull...