| |
 |
|
|
Science Forum Index » Compression Forum » generating function algo...
Page 1 of 1
|
| Author |
Message |
| BrainDumb... |
 Posted: Thu May 15, 2008 9:01 am |
|
|
|
Guest
|
Did anybody experiment with applying generating functions to
compression? Clearly, not all sequences will have a power series
expansion (ie. sequence of primes) but many do.
Also, can anyone recommend an efficient method of compressing
timestamps which could be expressed as string or numerically, ie.
11:35:22.244, disitribution of values is random.
thanks |
|
|
| Back to top |
|
| Thomas Richter... |
| Posted: Thu May 15, 2008 3:26 pm |
|
|
|
Guest
|
BrainDumb wrote:
Quote: Did anybody experiment with applying generating functions to
compression? Clearly, not all sequences will have a power series
expansion (ie. sequence of primes) but many do.
Why would you believe that your typical input sequence will have a
simple generating function? What is your input data? Unless you
have very special input, the generating function will be as complex
to represent as the original input.
Why do you believe that the sequence of primes does not have a
generating function? It does. It's just not writable with the
"usual" transcendental functions or as a rational or otherwise
"nice" function. Here we go:
primes(z) = 2 + 3z + 5 z^2 + 7 z^3 + 11 z^4 + ...
Quote: Also, can anyone recommend an efficient method of compressing
timestamps which could be expressed as string or numerically, ie.
11:35:22.244, disitribution of values is random.
Then, you need log(24 * 60 * 60) bits in total, ignoring leap-seconds.
If you have milliseconds in your time stamp, you need log(24*60*60*1000)
bits. The algorithm for optimal compression is simple: Convert your
timestamp into the number of milliseconds from an average starting time,
and represent this number with the number of bits computed above, which
is clearly sufficient. This is the (a) optimal representation for random
distribution. (Homework: Show why!)
So long,
Thomas |
|
|
| Back to top |
|
| Bartosz Wójcik... |
| Posted: Thu May 15, 2008 5:34 pm |
|
|
|
Guest
|
On Thu, 15 May 2008 12:01:41 -0700 (PDT), BrainDumb wrote:
Quote: Did anybody experiment with applying generating functions to
compression? Clearly, not all sequences will have a power series
expansion (ie. sequence of primes) but many do.
I've seen something like this at:
http://www.oberhumer.com/products/lzo-professional/
described as "Data To Code Transformations (D2CT)", but I couldn't get in
touch with them (not only me...) to get any more information, so if you
want to get more information you should probably fake NASA employee because
they don't talk with an ordinary people...
--
Bartosz Wójcik | www.pelock.com |
|
|
| Back to top |
|
| Thomas Richter... |
| Posted: Fri May 16, 2008 1:43 am |
|
|
|
Guest
|
Bartosz Wójcik schrieb:
Quote: On Thu, 15 May 2008 12:01:41 -0700 (PDT), BrainDumb wrote:
Did anybody experiment with applying generating functions to
compression? Clearly, not all sequences will have a power series
expansion (ie. sequence of primes) but many do.
I've seen something like this at:
http://www.oberhumer.com/products/lzo-professional/
described as "Data To Code Transformations (D2CT)", but I couldn't get in
touch with them (not only me...) to get any more information, so if you
want to get more information you should probably fake NASA employee because
they don't talk with an ordinary people...
Sounds like snake oil to me. No products available for testing. If they
enhanced the LZO code, their code is GPL'd, too, so the sources will
have to be made available. I somehow doubt that this will happen...
So long,
Thomas |
|
|
| Back to top |
|
| Phil Carmody... |
| Posted: Fri May 16, 2008 4:15 am |
|
|
|
Guest
|
Thomas Richter <thor at (no spam) math.tu-berlin.de> writes:
Quote: Bartosz Wójcik schrieb:
On Thu, 15 May 2008 12:01:41 -0700 (PDT), BrainDumb wrote:
Did anybody experiment with applying generating functions to
compression? Clearly, not all sequences will have a power series
expansion (ie. sequence of primes) but many do.
I've seen something like this at:
http://www.oberhumer.com/products/lzo-professional/
described as "Data To Code Transformations (D2CT)", but I couldn't get in
touch with them (not only me...) to get any more information, so if you
want to get more information you should probably fake NASA employee because
they don't talk with an ordinary people...
Sounds like snake oil to me. No products available for testing. If they
enhanced the LZO code, their code is GPL'd, too, so the sources will
have to be made available. I somehow doubt that this will happen...
Do what? They're allowed to license their own code under any
other license they see fit, including having it closed source.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration |
|
|
| Back to top |
|
| BrainDumb... |
| Posted: Tue May 20, 2008 11:54 am |
|
|
|
Guest
|
On May 15, 4:26 pm, Thomas Richter <t... at (no spam) math.tu-berlin.de> wrote:
Thomas, what do you mean by log(24 * 60 * 60*1000) bits. That's ~8
bits per what?
Obviously, given random distribution, the only approach is to
represent 1ms with 1bit. So that's 24 * 60 * 60 * 1000 bits |
|
|
| Back to top |
|
| Thomas Richter... |
| Posted: Wed May 21, 2008 9:52 am |
|
|
|
Guest
|
BrainDumb schrieb:
Quote: On May 15, 4:26 pm, Thomas Richter <t... at (no spam) math.tu-berlin.de> wrote:
Thomas, what do you mean by log(24 * 60 * 60*1000) bits. That's ~8
bits per what?
Bits per timestamp.
Quote: Obviously, given random distribution, the only approach is to
represent 1ms with 1bit. So that's 24 * 60 * 60 * 1000 bits
No, the problem is not to encode events or one bit per event, but to encode a given time
with a given resolution.
So long,
Thomas |
|
|
| Back to top |
|
| BrainDumb... |
| Posted: Thu May 22, 2008 2:39 pm |
|
|
|
Guest
|
Quote: Obviously, given random distribution, the only approach is to
represent 1ms with 1bit. So that's 24 * 60 * 60 * 1000 bits
No, the problem is not to encode events or one bit per event, but to encode a given time
with a given resolution.
No, allow me to disagree. The problem is compress data without loss.
My example
is about time sequence, at a millisecond resolution. Details are
insignificant.
I thought somebody knew a clever way to compress set of timestamps.
It appears there isn't a way. |
|
|
| Back to top |
|
| Thomas Richter... |
| Posted: Fri May 23, 2008 1:14 am |
|
|
|
Guest
|
BrainDumb schrieb:
Quote: Obviously, given random distribution, the only approach is to
represent 1ms with 1bit. So that's 24 * 60 * 60 * 1000 bits
No, the problem is not to encode events or one bit per event, but to encode a given time
with a given resolution.
No, allow me to disagree. The problem is compress data without loss.
My example
is about time sequence, at a millisecond resolution. Details are
insignificant.
I thought somebody knew a clever way to compress set of timestamps.
It appears there isn't a way.
There might be a way, but you need to know more about the data you
compress. If all you have is a set of random time stamps, there is no
better way indeed. If you have a sequence of data, not sampled at
*random*, then there's hope, but you didn't say so.
So long,
Thomas |
|
|
| Back to top |
|
| Phil Carmody... |
| Posted: Fri May 23, 2008 3:33 am |
|
|
|
Guest
|
BrainDumb <vortexsny at (no spam) hotmail.com> writes:
Quote: Obviously, given random distribution, the only approach is to
represent 1ms with 1bit. So that's 24 * 60 * 60 * 1000 bits
No, the problem is not to encode events or one bit per event, but to encode a given time
with a given resolution.
No, allow me to disagree. The problem is compress data without loss.
My example
is about time sequence, at a millisecond resolution. Details are
insignificant.
I thought somebody knew a clever way to compress set of timestamps.
It appears there isn't a way.
Time stamps are just data. You can't compress data.
Now if you know something special about the distribution of
the data, then perhaps something can be done. However, you've
not mentioned any such special distribution so we have to
presume there's none. I know that in my inertial reference
frame all microseconds are of equal length, and thus it's
equally likely that an arbitrary event will occur in each
microsecond.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Mon Oct 13, 2008 2:23 pm
|
|