Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed3a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <54E49995.6040403@davea.name>
References: <e45a71b2-7ec0-4c7d-88ae-c48aebe154b7@googlegroups.com> <54E34C68.6040700@davea.name> <mailman.18785.1424183690.18130.python-list@python.org> <65b209a0-33fc-4c1f-8af6-de3a4626623c@googlegroups.com> <54E49995.6040403@davea.name>
Date: Thu, 19 Feb 2015 01:16:00 +1100
Subject: Re: python implementation of a new integer encoding algorithm.
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.18820.1424268970.18130.python-list@python.org>
Lines: 45
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:85794

On Thu, Feb 19, 2015 at 12:54 AM, Dave Angel <davea@davea.name> wrote:
>>> I've tried to read through the original algorithm description, but I'm
>>> not entirely sure: How many payload bits per transmitted byte does it
>>> actually achieve?
>>
>>
>> I don't think that payload bits per byte makes sense in this concept.
>>
>
> Correct.  Presumably one means average payload bits per byte.
>
> First one would have to define what the "standard" unencoded variable length
> integer format was.  Then one could call that size the payload size.  Then,
> in order to compute an average, one would have to specify an expected, or
> target distribution of values.  One then compares and averages the payload
> size for each typical value with the encoded size.

Average, or separately for different ranges. Alternatively, identify
which ranges of numbers can be encoded with how many bytes. For
instance, if you have a varlen length (in bytes) followed by that many
packed bytes, you would have:

2: up to 1<<8-1
3: up to 1<<16-1
4: up to 1<<24-1
...
128: up to 1<<1016-1
130: up to 1<<1024-1
131: up to 1<<1032-1
etc

Using varlen directly gives:

1: up to 1<<7-1
2: up to 1<<14-1
3: up to 1<<21-1
etc

So if your number is around about 1<<20, you know it's going to take 3
bytes to encode as varlen, or 4 to encode with the meta-length. Easy
comparisons.

I'm not sure how this algorithm compares, because it's extremely clever.

ChrisA