| |
 |
|
|
Science Forum Index » Compression Forum » Best existing binary compressor method?
Page 2 of 2 Goto page Previous 1, 2
|
| Author |
Message |
| Phil Carmody |
 Posted: Fri Feb 22, 2008 8:50 pm |
|
|
|
Guest
|
Mark Nelson <snorkelman@gmail.com> writes:
Quote: On Feb 21, 4:41 pm, Matt Mahoney <matmaho...@yahoo.com> wrote:
On Feb 18, 8:35 am, Einstein <michae...@gmail.com> wrote:
The absolute best algorithm is to try running all possible programs of
length 0, 1, 2... until you find one that outputs a file identical to
the one you want to compress. Then send that program.
Some of the programs may run for a long time. If a program goes into
an infinite loop, you can kill it and go to the next one. If you
But what if the optimal program takes a long, long, long time, and you
kill it prematurely?
Just 'long time'
Quote: Surely we can devise an algorithm that will analyse the program to
determine whether it is going to halt or not. After all, this is
comp.compression.
Just 'comp.ression'
FP
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration |
|
|
| Back to top |
|
| Stefano Brocchi |
| Posted: Sat Feb 23, 2008 3:35 am |
|
|
|
Guest
|
Quote: Surely we can devise an algorithm that will analyse the program to
determine whether it is going to halt or not. After all, this is
comp.compression.
For how it could seem strange, it has been proven that that no program
that analyses any other program and always gives a result 'it will
halt' or 'it will not halt' can exist.
It is a main result of computability theory.
So long,
Stefano |
|
|
| Back to top |
|
| Willem |
| Posted: Sat Feb 23, 2008 3:46 am |
|
|
|
Guest
|
Stefano wrote:
) Mark wrote:
)> Surely we can devise an algorithm that will analyse the program to
)> determine whether it is going to halt or not. After all, this is
)> comp.compression.
)
) For how it could seem strange, it has been proven that that no program
) that analyses any other program and always gives a result 'it will
) halt' or 'it will not halt' can exist.
) It is a main result of computability theory.
I think your sarcasm detectors need a bit of tuning.
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 |
|
|
| Back to top |
|
| Einstein |
| Posted: Sun Feb 24, 2008 2:37 am |
|
|
|
Guest
|
Ok after looking at both of them (methods), seems I have already
pretty much 'remade' both methods. I do not see any extra advantages
gained in either atm, so neither method seems to be really effective
for me  |
|
|
| Back to top |
|
| Thomas Richter |
| Posted: Sun Feb 24, 2008 6:13 am |
|
|
|
Guest
|
biject schrieb:
Quote: On Feb 22, 12:51 am, Thomas Richter <t...@math.tu-berlin.de> wrote:
biject schrieb:
if you use arithmetic
cmpression you
get closer than huffman to the entropy on average.
That is correct, but only due to the limitation of huffman not
being able assign symbols a fractional number of bits. IOW, as long as
the probabilities of the source alphabet are inverse powers of two, there
is no difference between huffman and arithmetic in the limit.
Actually that is not even exactly true. If you ignore the tables
and
if doing static, huffman or arihmetic then the statement above is
true.
Note that I'm talking about a zero-order i.i.d. Markov process. There is
absolutely no adaption needed here.
Quote: Actually it doe have something to do with it when you trying to
compress to the entropy limit if your not compressing bijectively
in either huffman or airhmetic you end up with longer compressed
files
The "final file length" I'm talking about is infinite. No, it's not
longer. It's exactly as long, namely infinite. The proper question is
on the average number of bits per symbol, and this *will* approach
the entropy on AC in the limit. As I already said above, I'm making
statistical statements and whether a code is bijective or not is completely
irrelevant for this result.
So long,
Thomas |
|
|
| Back to top |
|
| Mark Nelson |
| Posted: Sun Feb 24, 2008 7:17 am |
|
|
|
Guest
|
On Feb 23, 7:46 am, Willem <wil...@stack.nl> wrote:
Quote:
I think your sarcasm detectors need a bit of tuning.
The perpetual problem with text-only communications...
|
| Mark Nelson - http://marknelson.us
| |
|
|
| Back to top |
|
| Stefano Brocchi |
| Posted: Mon Feb 25, 2008 2:31 am |
|
|
|
Guest
|
Quote: I think your sarcasm detectors need a bit of tuning.
Ok, in fact I read the thread a bit hastily and I didn't catch the
context of the discussion... I promise I'll be more 'tuned' next
time :)
So long,
Stefano |
|
|
| Back to top |
|
| |
Page 2 of 2 Goto page Previous 1, 2
All times are GMT - 5 Hours
The time now is Tue Oct 07, 2008 2:26 pm
|
|