Re: 47bit to 10 char A,,,Z revisted

briggs_at_encompasserve.org
Date: 04/25/05 

Date: 25 Apr 2005 12:28:10 -0500

In article <Xns9643516604DECH110W296LC45WIN3030R@213.155.197.138>, "David A. Scott" <daVvid_a_scott@email.com> writes:
> briggs@encompasserve.org wrote in
> news:ReDvofYqGWJz@eisner.encompasserve.org:
>
>> In article <Xns9641E3DC0F7D2H110W296LC45WIN3030R@213.155.197.138>,
>> "David A. Scott" <daVvid_a_scott@email.com> writes:
>>> I just moded arb255 to do the conversion to the 26
>>> character A..Z for the uncompress in a bijective way
>>> The fact is you can't code all binary bit strings
>>> from 1 bit to 47 bits with strings of ASCII A..Z
>>> where you allow only 1 to 10 character in a string.
>>
>> A very simple calculation would have told you this.
>>
>> 2^48 - 2 > (26^11-1)/25 - 1
>>
>> The calculation is even simpler if you include the null
>> strings.
>>
>> In the binary case, including variable length strings in the
>> mix effectively doubles the size of the code space. It is
>> thus worth one bit of information.
>>
>> In the alphabetic case, including variable length strings in
>> the mix multiplies the code space by a factor of 26/25. It
>> is thus worth log2(26/25) ~= .027 bits of information.
>>
>> We already knew that 10 characters (fixed length) was enough
>> to encode 47 bits (fixed length) with about .002 bits to spare.
>> It should have been no surprise that 10 characters (maximum
>> length) was not enough to encode 47 bits (maximum length).
>>
>> John Briggs
>>
>
> I am glad you and "We" already knew that 10 character strings or
> less could not cover all bit string from 1 to 47 bits. But have you
> seen code before that would code all strings of 470,000 bits or less
> with less then 100,000 characters of A..Z

Read it again, simpleton.

We knew that you can code all 2^47 fixed length 47 bit strings
using a subset of the 26^10 fixed length 10 character strings.

That's what we call in the trade:

        BLOODY FUCKING OBVIOUS

We did not know that you can code all 2^48-2 variable length bit
strings of no more than 47 and no less than 1 bit using
a subset of the (26^11-1)/25 - 1 variable length character strings
of no more than 10 and no less than 1 character.

Because that's what we call in the trade:

        NOT EVEN TRUE

Noticing that it is possible to encode 2^470,001 - 2 variable
length bit strings using (26^100,001-1)/25 - 1 variable length character
strings comes under the heading of:

        YEAH, SO?

> at
> http://bijective.dogma.net/abzt2.zip
>
> and for strings to binary file
>
> http://bijective.dogma.net/a012b01.zip

And the existence of code to actually perform the transformation
comes under that same heading. The requisite inequalities are loose
enough that even crude hackery can get the job done.

        John Briggs

Quantcast