http://www.pcplus.co.uk/node/3074/
-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> http://www.pcplus.co.uk/node/3074/
> --
>    Darren New, San Diego CA, USA (PST)
>    Insanity is a small city on the western
>    border of the State of Mind.

Cool idea.  I've often wondered about the possibility of multiple child nodes,
and what situations would benefit.  Seems this is the case where three nodes is
optimum.

....Chambers

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> http://www.pcplus.co.uk/node/3074/

  One problem which I see with the tree building algorithm presented there
is that the tree is not balanced. The geometry of the tree will heavily
depend on which order you insert the strings into it. A suboptimal insertion
order will cause the tree to be heavily unbalanced.

  For example, assuming an alphabet of 26 characters, you may end up with
a tree such that if you try to search, for example, for the string "AAAA",
you first have to choose the left node 25 times before you find the first
one equal to A, after which you have to choose again the left node 25
times for the second A, and so on.

  However, if the tree was fully balanced, then you would only have to
choose the left node 5 times (or less) for each of the A's (because
log2(26) = 5). The problem of course accentuates itself with larger
alphabets (eg. if you had a full byte alphabet, ie. 256 distinct "letters").

  Thinking about the problem, I see two possible solutions: You could come
up with a really contrived solution, similar to how binary search trees are
kept balanced (eg. by using the same techniques as with a red-black tree).

  However, I can think of a much easier solution which doesn't need any
rebalancing:

  Always create every node so that it partitions the alphabet in two equal
parts. In other words, assuming an alphabet of A-Z, the root node would
*always* be N. Then create new nodes as needed (for the string to be
inserted): If the first character of the new string is less then N, then
create a G node at the left of the root (regardless of what the first
character of the string was). If it's larger, create a T node at the right.
If it was equal, then create an new N node as the "equal" child node for
the root. If the first character of the string was not N, keep splitting
like this until you end up with the character in question, and then always
create a new N node as a new child node for that. Repeat this until the
entire string has been inserted.

  There will be some extra nodes (something line O(log2(n)) extra nodes
per character), but the tree will always be fully balanced, and immediately
when a new string is added which already has an existing node in the tree,
it will benefit from it. In an optimal case the amount of extraneous nodes
in the tree will be quite small compared to the amount of "true" nodes.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> when a new string is added which already has an existing node in the tree,
> it will benefit from it. 

I think that would work with the caveat that you have to distinguish between 
nodes without a child and nodes whose only child is '\0'.  That is, not all 
your branches will end in a '\0' as shown in the picture. I'd have to think 
harder about the performance implications for failed lookups, too.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> I think that would work with the caveat that you have to distinguish between 
> nodes without a child and nodes whose only child is '\0'.  That is, not all 
> your branches will end in a '\0' as shown in the picture.

  Each node needs a bit of information denoting whether it's an end node
or not (ie. whether that node is the last character of a string stored in
the data structure or not) regardless. For example, if you store "CAT" and
"CATS" as two separate strings, you'll need a bit in the 'T' node to
indicate that there exists a string which end there.

  Doing it like I suggested doesn't change anything. For the extraneous
nodes you simply set the bit to "no string ends here".

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> I think that would work with the caveat that you have to distinguish between 
>> nodes without a child and nodes whose only child is '\0'.  That is, not all 
>> your branches will end in a '\0' as shown in the picture.
> 
>   Each node needs a bit of information denoting whether it's an end node
> or not (ie. whether that node is the last character of a string stored in
> the data structure or not) regardless. For example, if you store "CAT" and
> "CATS" as two separate strings, you'll need a bit in the 'T' node to
> indicate that there exists a string which end there.

I think the way the original paper worked it is to store the '\0' as part of 
the string in the tree. So your CAT vs CATS would be
-->C-->A-->T-->S-->\0
            |
            v
           \0

You could of course represent it as a separate bit instead.

>   Doing it like I suggested doesn't change anything. For the extraneous
> nodes you simply set the bit to "no string ends here".

Yes, that's another way to do it. However, if you want to associate some 
data with each string (e.g., you're using it in place of a hashtable map, 
instead of in place of a list of strings like a spelling checker might use), 
you'll want a place to store the pointer associated with the "string ends 
here" anyway, and it might be more space-efficient to have a '\0' node to 
tack that pointer onto than it would be to have that pointer on every 
character whether it's the end of a string or not. If you have '\0' nodes, 
you could special-case the "next character" (i.e., middle) pointer to point 
to the data you want to associate with the word.

I wonder how ugly this would be to implement functionally.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> I think the way the original paper worked it is to store the '\0' as part of 
> the string in the tree. So your CAT vs CATS would be
> -->C-->A-->T-->S-->\0
>             |
>             v
>            \0

  But that's not a null pointer indicating the end of the string. That's
a regular node containing a special character which indicates the end of
the string. Implementing my automatically-balanced tree creation idea can
use the exact same method for marking ends of strings.

  Btw, the node containing an end-of-string value idea works only as long
as there's a special character value which never appears in a string. It
can't be done like that if the range of values of each character in your
"string" can hold is the full 0-255 range. Of course you could use values
larger than 8 bits, but that's just basically the exact same thing as having
an end-of-string bit at each node. (And given that the "character" in the
node will probably take 4 bytes for alignment purposes anyways, there's
plenty of unused bits.)

  Which got me thinking: This data container uses quite a lot of space,
actually. Each node requires three pointers plus the character itself.
In a 32-bit system the pointers will be 4 bytes each, and as said, memory
alignment requires for the character to take 4 bytes as well, for a grand
total of 16 bytes per node (and this assuming you are storing each node
optimally in an array rather than allocating each node separately).
16 bytes to store one single character sounds quite a lot... :)

  Of course strings with equal beginnings will share nodes, but if the
strings are very diverse, they will still end up using quite a lot of
memory.

> If you have '\0' nodes, 
> you could special-case the "next character" (i.e., middle) pointer to point 
> to the data you want to associate with the word.

  In fact, since no character can be smaller than '\0', you could also
have additional '\0' nodes on the left branch, each one pointing to
associated data. That way you can have a multiset, ie. the same key
pointing to multiple data, rather than just one.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> I think the way the original paper worked it is to store the '\0' as part of 
>> the string in the tree. So your CAT vs CATS would be
>> -->C-->A-->T-->S-->\0
>>             |
>>             v
>>            \0
> 
>   But that's not a null pointer indicating the end of the string. That's
> a regular node containing a special character which indicates the end of
> the string. Implementing my automatically-balanced tree creation idea can
> use the exact same method for marking ends of strings.

Then we're in agreement. I was using \0 to indicate ASCII NUL, not C's NULL 
pointer.  You can either use a node whose character value is '\0', or you 
can use a separate bit, depending on your needs.

>   Btw, the node containing an end-of-string value idea works only as long
> as there's a special character value which never appears in a string. It
> can't be done like that if the range of values of each character in your
> "string" can hold is the full 0-255 range. Of course you could use values
> larger than 8 bits, but that's just basically the exact same thing as having
> an end-of-string bit at each node.

Yep. Or you could have another pointer that points to the data that is 
associated with that string (i.e., the "value" of the "key/value" pair), and 
if that's not NULL, then a string ends at that node.

> 16 bytes to store one single character sounds quite a lot... :)

And a fourth pointer for the value associated, yes. Of course, any tree 
structure is going to be close to the same size too.  If you have lots and 
lots of strings, and you're more worried about space than speed, a hash 
table works out better, I expect.

>   Of course strings with equal beginnings will share nodes, but if the
> strings are very diverse, they will still end up using quite a lot of
> memory.

If you're using up enough memory to be worried about it, chances are you 
have enough strings that the beginnings will overlap a lot? I mean, unless 
you're really memory-constrained.

>   In fact, since no character can be smaller than '\0', you could also
> have additional '\0' nodes on the left branch, each one pointing to
> associated data. That way you can have a multiset, ie. the same key
> pointing to multiple data, rather than just one.

Hmmmmm. Well, certainly the '\0' node could point to a different structure 
than the other nodes. You already have three pointers there to play with, 
and you could reasonably hang an entire tree underneath if you wanted.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Warp wrote:
> Each node requires three pointers plus the character itself.

Or, with enough work, you could get away with not using full-sized pointers, 
perhaps. Indexes into arrays (with said arrays split into chunks if you have 
trouble finding that much contiguous address space) might work too.

Or, if it's on disk, you could have two kinds of nodes - ones that point to 
other nodes nearby (or in the same block or file, say), and others that 
point to different files. So the root and first 2 or 3 levels might be in 
one block, with the "leaves" in other blocks or files or something. Since 
you don't randomly walk around the tree when you're updating it, you don't 
need to worry quite so much about caching as you might otherwise.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> > 16 bytes to store one single character sounds quite a lot... :)

> And a fourth pointer for the value associated

  That's not necessary if you use the '\0' node to end strings, as you
pointed out.

> Hmmmmm. Well, certainly the '\0' node could point to a different structure 
> than the other nodes. You already have three pointers there to play with, 
> and you could reasonably hang an entire tree underneath if you wanted.

  You can't use the "right child" pointer of the '\0' node for ancillary
data because it can be part of the regular tree structure.

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > Each node requires three pointers plus the character itself.

> Or, with enough work, you could get away with not using full-sized pointers, 
> perhaps. Indexes into arrays (with said arrays split into chunks if you have 
> trouble finding that much contiguous address space) might work too.

  I suppose that if you limit the size of the data container to 2^24 nodes,
you could use "pointers" of 3 bytes, which would be 9 bytes plus the
character. Alignment usually requires to round that up to 12 bytes. (The
extra space could be used for the end-of-string bit.)

  If you limited the number of nodes to 2^16 then you could use 8 bytes
per node. However, I'm not sure if such a limitation is very practical.

  Of course if you are willing to sacrifice some speed in order to squeeze
space, you could break the word/half-word boundaries, and compact eg. the
three 24-bit pointers and the 8-bit character into a 10-byte node in a
byte array. Or if you are not afraid of bit-fu, something more exotic like
21 bits for the "pointers" (giving a maximum of 2097152 nodes), 8 bits for
the characters and 1 bit for the end-of-string bit, which would result in
9 bytes per node.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   You can't use the "right child" pointer of the '\0' node for ancillary
> data because it can be part of the regular tree structure.

True, true. :-)

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Warp wrote:
>   I suppose that if you limit the size of the data container to 2^24 nodes,

No, you could use "offsets to next element" or something, too, methinks. But 
yeah, that's kind of the thing I was thinking about. By the time you have 
more than 2^16 nodes, you're probably worrying more about speed, paging, etc 
than you are about raw size, perhaps. And you're going to start to see a lot 
of overlap in the earlier parts of the strings.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>   However, I can think of a much easier solution which doesn't need any
> rebalancing:
>
>   Always create every node so that it partitions the alphabet in two equal
> parts. In other words, assuming an alphabet of A-Z, the root node would
> *always* be N.

This would require your data to have a linear distribution.

What if all your keys had the form "img00000000002AC73F.jpg"?


As a matter of fact, there already are good tree concepts out there that include
automatic balancing without any a-priori knowledge of the data. Not perfect, but
with a certain guaranteed minimum quality. Red-Black-Trees are a quite popular
example. I'd expect the same principle to be adaptable to ternary trees, too.

Post a reply to this message

clipka wrote:
> Red-Black-Trees are a quite popular example. 

Skip lists are also a cool data structure for when you have a lot of data 
you'd like to put in a tree but don't want to balance things etc. 
Generalized to skip graphs in the same sense that a DHT generalizes a hashtable.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   I suppose that if you limit the size of the data container to 2^24 nodes,

> No, you could use "offsets to next element" or something, too, methinks. But 
> yeah, that's kind of the thing I was thinking about. By the time you have 
> more than 2^16 nodes, you're probably worrying more about speed, paging, etc 
> than you are about raw size, perhaps. And you're going to start to see a lot 
> of overlap in the earlier parts of the strings.

  I'd say it's the exact opposite: When you start having more than 2^16
nodes, that's when you need to star worrying about the amount of space the
data structure is taking. With less than 2^16 nodes the size of an individual
node is rather irrelevant.

-- 
                                                          - Warp

Post a reply to this message

clipka <nomail@nomail> wrote:
> This would require your data to have a linear distribution.

  No, it doesn't. For an alphabet of eg. 26 characters you need to perform
at most 5 steps per character, period, completely regardless of what the
stored strings are.

  With an unbalanced tree the worst case scenario is that you end up having
to perform 25 steps per character.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   I'd say it's the exact opposite: When you start having more than 2^16
> nodes, that's when you need to star worrying about the amount of space the
> data structure is taking. With less than 2^16 nodes the size of an individual
> node is rather irrelevant.

My thought was that if you have that much data, you're probably running on a 
machine where the memory limits aren't very tight (i.e., a desktop system, 
say).  Of course, the killer is the ratio of the number of nodes to the 
amount of memory, so sure, when you start getting up in the 2^25 number of 
nodes range the size of the nodes is going to be prohibitive on a 32-bit 
machine again.

The nice thing is the tree doesn't need rotations, so you can clip off a 
large sub-tree of the tree and put it in its own address space. That's hard 
to do if you have to balance nodes and stuff.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   I'd say it's the exact opposite: When you start having more than 2^16
> > nodes, that's when you need to star worrying about the amount of space the
> > data structure is taking. With less than 2^16 nodes the size of an individual
> > node is rather irrelevant.

> My thought was that if you have that much data, you're probably running on a 
> machine where the memory limits aren't very tight (i.e., a desktop system, 
> say).

  Well, I may be biased because of my programming history background, but
usually an app crunching tons of data requires space-efficient data containers
(so that it can crunch as much data as possible with a given amount of RAM).
You usually want your app to be able to handle as much data as possible.

  Also my recent programming history can also have some effect on how I view
these things, namely programming for handheld systems. For example, games
which require a full (eg. English) dictionary are an extremely typical case
where you need a very fast data container which should take as little space
as possible (because a handheld system won't have a multi-GHz CPU nor
gigabytes of RAM). A typical English dictionary is excruciatingly annoying
in this regard because they usually go just a bit over the magical limit
of 65536 words, especially if the game requires plurals and other inflected
forms. (And even if the dictionary did have under 65536 words, the total
amount of character data would still be well beyond that limit, and since
words are of differing lengths you really need byte-pointers/indices.)

>  Of course, the killer is the ratio of the number of nodes to the 
> amount of memory, so sure, when you start getting up in the 2^25 number of 
> nodes range the size of the nodes is going to be prohibitive on a 32-bit 
> machine again.

  Hmm, I'm not so sure. 2^25 nodes, each node taking eg. 16 bytes, would
require "only" 512 MB of RAM, which is well below the capacity of any
modern desktop system.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> You usually want your app to be able to handle as much data as possible.

Yeah. My background tends towards needing to crunch arbitrary amounts of 
data, and hence I look at data structures that cache to disk more 
efficiently. The sorts of stuff I write can't rely on having enough memory 
to hold it all, but also tend to assume you're not going to look at all of 
it at once (like a database of customers, for example, rather than a game, 
where you really want the whole level in memory at once).

>   Also my recent programming history can also have some effect on how I view
> these things, namely programming for handheld systems. 

Cool. Yeah, I'm kind of impressed, actually. I'm writing code for set top 
boxes right now, and the boss has me porting webkit to the machine. He's all 
worried about the performance, and I'm saying "maybe you shouldn't have two 
layers of interpreted language on top of your 100MHz CPU just to draw your 
top-level menus."

Coming from the credit card terminal world, where having 14K of ram was 
pretty much top-of-the-line, it's a little boggling to have a whole 128M of 
RAM. :-)

Handheld machines are definitely still the cutting edge of resource pain, 
tho, yes.  Especially since people expect them to do flashy things 
efficiently and cheaply and responsively.  CC terminals need to be quick, 
but nobody really cares if you have a 16x4 text-only B&W screen on one.

>>  Of course, the killer is the ratio of the number of nodes to the 
>> amount of memory, so sure, when you start getting up in the 2^25 number of 
>> nodes range the size of the nodes is going to be prohibitive on a 32-bit 
>> machine again.
> 
>   Hmm, I'm not so sure. 2^25 nodes, each node taking eg. 16 bytes, would
> require "only" 512 MB of RAM, which is well below the capacity of any
> modern desktop system.

Fair enough. It's getting close to the limit of what you can put in one 
address space conveniently, is all. (On a 32-bit machine, that is.) Of 
course you still have the malloc()/free() space overhead for each blob, and 
whatever the rest of the program is doing, and etc.

You can run into limits either way, with small memories or with google-sized 
data. With my work, I tend to run into problems with google-sized data, 
where the speed of even copying files from one place on the disk to another 
is a significant overhead. I can see how if you're looking at it from a game 
console or handheld device POV, you can see the space problem in a different 
way.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message

Warp wrote:

>   One problem which I see with the tree building algorithm presented there
> is that the tree is not balanced. The geometry of the tree will heavily
> depend on which order you insert the strings into it. A suboptimal insertion
> order will cause the tree to be heavily unbalanced.

As far as I can tell, it's only the letter selection part of the tree 
which can be unbalanced. E.g., if you have a million strings, you won't 
ever have to do a million comparisons to find a given string. You might 
end up doing 25 comparisons per character or something, but you'll never 
need to do a million.

(A common optimisation I've seen is to store the shared prefix in a tree 
and then any unique suffix is stored all in one lump rather than as tree 
nodes. As similar keys are added, the unique lump gets expanded out. 
This way, the work is proportional to the size of the shared key prefix, 
not the whole key.)

>   However, I can think of a much easier solution which doesn't need any
> rebalancing:
> 
>   Always create every node so that it partitions the alphabet in two equal
> parts.

Assuming the range of permissible "characters" is small and known prior 
to starting, sure.

(You might use this algorithm, e.g., with IP addresses as keys, and then 
the key string elements aren't characters any more. But hey, if you're 
going to use fixed-width binary data, there are better structures 
available...)

Post a reply to this message

Darren New wrote:
> http://www.pcplus.co.uk/node/3074/

I just implemented it... partial matching and all. ;-)

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> As far as I can tell, it's only the letter selection part of the tree 
> which can be unbalanced. E.g., if you have a million strings, you won't 
> ever have to do a million comparisons to find a given string. You might 
> end up doing 25 comparisons per character or something, but you'll never 
> need to do a million.

  But if the strings themselves are very long, then it can make a
significant difference whether you have to make 25 comparisons per
character or 5.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> As far as I can tell, it's only the letter selection part of the tree 
>> which can be unbalanced. E.g., if you have a million strings, you won't 
>> ever have to do a million comparisons to find a given string. You might 
>> end up doing 25 comparisons per character or something, but you'll never 
>> need to do a million.
> 
>   But if the strings themselves are very long, then it can make a
> significant difference whether you have to make 25 comparisons per
> character or 5.

Sure. I'm just saying, if the number of comparisons were dependent on 
the number of keys, you'd be in a whole other *complexity class*. That 
puts "really slow" into perspective.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> http://www.pcplus.co.uk/node/3074/
> 
> I just implemented it... partial matching and all. ;-)

...and then somebody on the Haskell mailing list announces that they're 
releasing this on Hackage. Go figure!

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message