Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 09 Apr 2015 08:03:51 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: python implementation of a new integer encoding algorithm.
References: <e45a71b2-7ec0-4c7d-88ae-c48aebe154b7@googlegroups.com> <mailman.18784.1424182393.18130.python-list@python.org> <515047c1-a20d-430e-a029-1c2d77db2f1a@googlegroups.com> <mailman.18823.1424278025.18130.python-list@python.org> <2a717ffb-d61d-4407-9082-1c17cd7ee573@googlegroups.com> <mailman.18839.1424298000.18130.python-list@python.org> <993f64c3-fc85-48a7-9d02-a4f12ecb33c6@googlegroups.com> <mailman.18894.1424370292.18130.python-list@python.org> <c6007d78-7c21-4841-814f-4ca529889298@googlegroups.com>
In-Reply-To: <c6007d78-7c21-4841-814f-4ca529889298@googlegroups.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.164.1428581054.12925.python-list@python.org>
Lines: 57
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:88711

On 04/09/2015 05:33 AM, janhein.vanderburg@gmail.com wrote:
> Op donderdag 19 februari 2015 19:25:14 UTC+1 schreef Dave Angel:
>> I wrote the following pair of functions:

    <snip>
>>
>> Here's a couple of ranges of output, showing that the 7bit scheme does
>> better for values between 384 and 16379.
> Thanks for this test; I obviously should have done it myself.
> Please have a look at http://optarbvalintenc.blogspot.nl/2015/04/inputs-from-complangpython.html and the next two postings.
>

I still don't see where you have anywhere declared what your goal is. 
Like building a recursive compression scheme [1], if you don't have a 
specific goal in mind, you'll never actually be sure you've achieved it, 
even though you might be able to fool the patent examiners.

Any method of encoding will be worse for some values in order to be 
better for others.  Without specifying a distribution, you cannot tell 
whether a "typical" set of integers is better with one method than another.

For example, if you have uniform distribution of all integer values up 
to 256**n-1, you will not be able to beat a straight n-byte binary storage.

Other than that, I make no claims that any of the schemes previously 
discussed in this thread is unbeatable.

You also haven't made it clear whether you're assuming such a compressed 
bit stream is required to occupy an integral number of bytes.  For 
example, if your goal is to store a bunch of these arbitrary length 
integers in a file of minimal size, then you're talking classic 
compression techniques.  Or maybe you should be minimizing the time to 
convert such a bit stream to and from a conventional one.

I suggest you study Huffman encoding[2], and see what makes it tick.  It 
makes the assumptions that there are a finite set of symbols, and that 
there exists a probability distribution of the likelihood of each 
symbol, and that each takes an integral number of *bits*.

Then study arithmetic-encoding[3], which no longer assumes that a single 
symbol occupy a whole number of bits.  A mind-blowing concept. 
Incidentally, it introduces a "stop-symbol" which is given a very low 
probability.

See the book "Text Compression", 1990, by Bell, Cleary, and Witten.

[1] - http://gailly.net/05533051.html
[2] - http://en.wikipedia.org/wiki/Huffman_coding
[3] - http://en.wikipedia.org/wiki/Arithmetic_coding

If you're going to continue the discussion on python-list, you probably 
should start a new thread, state your actual goals, and


-- 
DaveA