| View previous topic :: View next topic |
| Author |
Message |
Ray
Guest
|
 Posted: Thu Sep 11, 2003 11:56 am Post subject: How to store a tree efficiently ? |
 |
|
Root
|
--------------------------------------------------------
| | | | | | |
2 | ------- ---------- ----- | ---------------
7 | | | | | | | | | | | |
------ 2 4 3 3 2 1 | 4 3 ----- -----
| | 4 | | | |
----- 1 3 1 2 2
| |
2 3
I have a tree like this
how to store it as compact as possible ? |
|
| |
|
 Back to top |
Jesper Nordenberg
Guest
|
| Posted: Thu Sep 11, 2003 3:54 pm Post subject: Re: How to store a tree efficiently ? |
|
|
a__l__k__@hotmail.com (Ray) wrote in message news:<514a7d7.0309102256.14ffe463@posting.google.com>...
[quote]Root
|
--------------------------------------------------------
| | | | | | |
2 | ------- ---------- ----- | ---------------
7 | | | | | | | | | | | |
------ 2 4 3 3 2 1 | 4 3 ----- -----
| | 4 | | | |
----- 1 3 1 2 2
| |
2 3
I have a tree like this
how to store it as compact as possible ?
[/quote]
I>m assuming that any tree node can have any number of sub-nodes
(children) and each leaf can have any value. One possible solution is
to recursively store each node as:
branch or leaf, 1 bit
number of children (for a branch) / value (for a leaf), n bits
<child node 1, if branch>
.....
To further decrease the space needed, compress the "number of
children/value" field using arithmetic or huffman coding. Or compress
the entire output using a good compression algorithm (like BWT).
/Jesper Nordenberg |
|
| |
|
| Back to top |
Ray
Guest
|
| Posted: Fri Sep 12, 2003 6:16 pm Post subject: Re: How to store a tree efficiently ? |
|
|
megagurka@yahoo.com (Jesper Nordenberg) wrote in message news:<9c838fb.0309110254.575b32e7@posting.google.com>...
[quote]a__l__k__@hotmail.com (Ray) wrote in message news:<514a7d7.0309102256.14ffe463@posting.google.com>...
Root
|
--------------------------------------------------------
| | | | | | |
2 | ------- ---------- ----- | ---------------
7 | | | | | | | | | | | |
------ 2 4 3 3 2 1 | 4 3 ----- -----
| | 4 | | | |
----- 1 3 1 2 2
| |
2 3
I have a tree like this
how to store it as compact as possible ?
I>m assuming that any tree node can have any number of sub-nodes
(children) and each leaf can have any value. One possible solution is
to recursively store each node as:
branch or leaf, 1 bit
number of children (for a branch) / value (for a leaf), n bits
child node 1, if branch
....
To further decrease the space needed, compress the "number of
children/value" field using arithmetic or huffman coding. Or compress
the entire output using a good compression algorithm (like BWT).
/Jesper Nordenberg
[/quote]
Thanks Jesper... this is a compressing method...
manage to change a file into what I display above...
just need a way to store the tree as small as possible... |
|
| |
|
| Back to top |
George Buyanovsky
Guest
|
| Posted: Sat Sep 13, 2003 12:58 am Post subject: Re: How to store a tree efficiently ? |
|
|
a__l__k__@hotmail.com (Ray) wrote in message news:<514a7d7.0309102256.14ffe463@posting.google.com>...
[quote]|
--------------------------------------------------------
| | | | | | |
2 | ------- ---------- ----- | ---------------
7 | | | | | | | | | | | |
------ 2 4 3 3 2 1 | 4 3 ----- -----
| | 4 | | | |
----- 1 3 1 2 2
| |
2 3
how to store it as compact as possible ?
[/quote]
You may found the article below useful.
http://www.ecs.csun.edu/~dsalomon/DC2advertis/QuadBuyan.pdf
--George |
|
| |
|
| Back to top |
|
