Re: Encoding materialized path in an atomic value.

David Cressey wrote:
> The recent discussion in another thread about encoding an entire
> materialized path in a single value started me down the following path.
>
> It's common practice on genealogy websites to adopt a numeric encoding
> method for family trees of ancestors of a given person. The tree of a
> person's descendants follow a pattern familiar to us as "parent child
> relationships".
>
> But genealogists sometimes work the family tree the other way. That is,
> you have two parents, and each of your parents has two parents giving you
> four grandparents, eight greatgrandparents, this process is limited, but we
> can ignore that for now.
>
> Anyway, a common encoding technique for ancestor's is to assign a number
> for each ancestor, according to a binary pattern, with one for a father
> and zero for a mother.
>
> Thus your ancestor number 23 is as follows: writing the number in binary,
> but showing the bits backwards (LSB first): 11101

As Hugo mentioned, it's ambiguous. Although boolean tree encodings do exist.

Encode all the numbers in unary numerical system (written backwards for convenience), e.g.

1 - 1
2 - 01
3 - 001
4 - 0001

This encoding is an "economical" version of http://toponewithties.blogspot.com/2005/03/path-enumeration-using-prime-number.html (scroll down to mikito's comment)

I have a book in work with a chapter surveying many known tree encodings. Received on Sat Sep 24 2005 - 00:18:43 CEST