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

[Michael Richardson <[e-mail]>]

Carsten Bormann <[e-mail]> wrote:
    > 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?)

I guess it depends upon your point of view. All references need to point in
the same direction :-)

    > 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.

I think that things in the static dictionary(ies) can not reference things in
the shared (dynamic) dictionary.  I am grumpy about the terminology now, btw.
"shared" is a bit ambiguous now.

I also think that my understanding of the prefix space is too shallow.

But, it seems that we ought to be able to build a reasonable DAG.

    > 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.

When you say merged, do you mean that they receive some kind of collective
numbering?

    > 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.

unidirectional references are just one way of dealing with the loop.
Another is just to have a big enough bitmap to be able to mark things.

A third loop detection involves two pointers, one which moves at half the
rate of the other: I know this works for single-linked lists, but it might
not work for a tree. I have think about this.

--
Michael Richardson <[e-mail]>, Sandelman Software Works
 -= IPv6 IoT consulting =-