Re: [Cbor] Ordering of items in the prefix table

[Carsten Bormann <[e-mail]>]

On 2020-08-28, at 20:24, Michael Richardson <[e-mail]> wrote:
> 
> 
> Jim Schaad <[e-mail]> wrote:
>> I was just going through an expansion algorithm and I started to wonder if
>> we should have a requirement about order of items in the prefix table.
>> Specifically if an entry in the prefix table uses a prefix itself  (i.e.
>> entry 3 in the table is 6.2872("foo")), does that entry need to occur after
>> the entry it references?
> 
> I also asked that question.
> If we don't enforce that rule, then the decoder has to take care of dealing
> with loops.

Right.

> This means either having a maximum loop depth, or, using a mark to refuse to
> expand any specific dictionary item more than once.
> I would prefer that all references are forward references.

(Backward references?)

This is easy with just one kind of table entry, but gets harder when prefixes can reference shared items which can reference other prefixes and so on.

Of course, the tables could be merged, but that loses exactly one bit per reference that can be derived from the prefix vs. shared reference.

One other thing to keep in mind is that not all places in the table are equal — the compressor will likely sort the entries by frequency of use.  Requiring infrequent entries to occupy all the good positions does not lead to very compact encoding.

Grüße, Carsten