Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: LawCounsels@aol.com Newsgroups: comp.compression Subject: Re: Mankind's centuries old Kraft's Inequality / Pigeonholes hurdles Date: Tue, 10 Apr 2012 02:29:06 -0700 (PDT) Organization: http://groups.google.com Lines: 98 Message-ID: <32016146.1695.1334050146969.JavaMail.geo-discussion-forums@vbex14> References: <27720309.364.1333215152376.JavaMail.geo-discussion-forums@vbhy1> <32199220.558.1333700643174.JavaMail.geo-discussion-forums@ynbq18> <30572244.769.1333870880706.JavaMail.geo-discussion-forums@vbvd13> <7c4de374-7475-4a05-bd99-aaa1a6311b0b@h4g2000pbe.googlegroups.com> <24603421.783.1333951092279.JavaMail.geo-discussion-forums@vbhy1> <7a3f0e0d-48e5-4930-8a95-8691f26b3402@s10g2000pbc.googlegroups.com> <66b8e0fb-8fa9-4407-9dad-4db79bf02f26@p6g2000yqi.googlegroups.com> NNTP-Posting-Host: 195.191.66.226 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1334050231 22293 127.0.0.1 (10 Apr 2012 09:30:31 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 10 Apr 2012 09:30:31 +0000 (UTC) In-Reply-To: <66b8e0fb-8fa9-4407-9dad-4db79bf02f26@p6g2000yqi.googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=195.191.66.226; posting-account=r0WWUAkAAABOH45ROaD3Sg3uPclryRTY User-Agent: G2/1.0 Xref: csiph.com comp.compression:1220 On Monday, 9 April 2012 17:03:04 UTC+1, biject wrote: > On Apr 9, 5:19=A0am, James Dow Allen wrote: > > On Apr 9, 12:58=A0pm, lawcouns...@gmail.com wrote: > > > > > a source with probability of producing an 'a' symbol 25% of time > > > a 'b' symbol 25% of times a 'c' symbol 50% of times > > > > Allow me to recommend the optimal Huffman code: > > =A0 =A0c - 0 > > =A0 =A0a - 10 > > =A0 =A0b - 11 > > This can be improved, though only slightly, using details > > you've omitted from your summary. > > > > This was so trivial, I'll discount it down to, say $950. > > > > If this is unsatisfactory, I'll withdraw from the contest. > > Even paid at minimum wage I'm afraid it would take significant > > funds (payable in advance, please!) just to elicit a > > proper problem statement from you. > > > > I don't have PayPal. =A0Contact me for instructions on how > > to pay the $950. =A0:-) > > > > James >=20 > Lets see c is .5 * 1 =3D .5 b =3D .25*2 =3D .5 c =3D .25*2 =3D .5 > see thats .5 + .5 + .5 =3D 1.5 for the average sequence while > if you encode each with 1.5849625 you save about .0849625 which > is more than the .08 It appears your in the money. I have a > hunch that there still is something missing in which case I would > not count on the money yet. >=20 > First of all does he want at least .08 bits saved in every case > or just the average case. If its the average case you could be > on the right track. If its every case then since you write only > whole numbers of bits the .08 savings gets a little harder. It > would be nice if the guy decides you haven't won just what does > he want. I have read it several times and yet I do not think its > clear enough to tackle without him saying oh I meant this and not > that. >=20 > Assuming he doesn't declare you the winner > 1) is the savings an average things or does each file have to be less. > 2) how do you measure the savings is it .08 from a 1.5849625 per > symbol > or is it .08 less then 1.5 > 3) not sure why you say source C =3D .5 while A and B =3D .25 the > fact is even if the source is A =3D B =3D C =3D 1/3 for short files > if you run the sources enough times and created a 100 files each > you still could get the same set of 100 files for both cases. > So you test set up is not valid. There is nothing magical about > your source. Except if I know its a fixed IID souce from say 2 or > 3 different models as you create more files. You can with increasing > probability determine which one it most likely is. But you can't be > 100% certain which one it is unless you do an ever increasing number > of file. >=20 >=20 > David A. Scott > -- > My Crypto code > http://bijective.dogma.net/crypto/scott19u.zip > http://www.jim.com/jamesd/Kong/scott19u.zip old version > My Compression code http://bijective.dogma.net/ > **TO EMAIL ME drop the roman "five" ** > 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. > As a famous person once said "any cryptograhic > system is only as strong as its weakest link" THE COMPLETE SPECIFICATIONS : =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D 1. generates a number eg 1,000 of such sequences ( each sequence composed o= f ternary symbols 'a' 'b' 'c' , when # of 'c' =3D # of 'b' + 2 Then sequenc= e ENDS & next sequences begins ) using a source producing symbol 'a' 25% o= f times symbol 'b' 25% of times symbol 'c' 50% of times ) .... call the tot= al # of symbols in these 1,000 sequences N . NOTE : among these eg 1,000 se= quences the # of 'a' is invariable near =3D the # of 'b' & the # of 'c' is= invariable near =3D 2 * the # of 'b' THUS the probability model here is 2= 5% : 25% : 50%=20 2. compresses these eg 1,000 generated sequences using your .exe , & must d= ecode back to the same 1,000 sequences=20 3. IF you compressed file bitslength =3D< 1.5 * N - ( 0.08 * N ) THEN = YOU WIN THE REWARDS ! ie if your .exe saves 'on average' 0.08 bit each se= quences you WON ( needs not be invariable every time on every conceivable f= ile ! ) , but note the original # of sequences is here taken to be of bitsl= ength N * 1.5 bits long ( as originally 'explicit' stated to be 1.5 * N b= its long , NOT 1.5849625 * N bits long ) 4. there is no restrictions on memory storage requirements , you may even s= how your .exe works on 'research network supercomputer cluster' , BUT proce= ssing must complete within a day