How to store a trie

[Wictorian]

How should one store a trie in a database?

[AbydosOne]

26 minutes ago, Wictorian said:

a trie

A what? 

[Eigenvektor]

4 hours ago, AbydosOne said:

A what? 

I assume this: https://en.m.wikipedia.org/wiki/Trie

When you're working with such recursive data structures, you might want to also learn about Common Table Expressions (CTE)

 

Since this is basically a tree, a table with a key, some value(s) and a reference to a key should suffice.

~edit:

trie {
  id: int,
  parentId: int,
  …
  <values>
}

 

 

For example this trie could be stored as:

 Id | ParentId | Value
  0 |     null | 
  1 |        0 | t
  2 |        0 | i
  3 |        0 | A
  4 |        1 | to
  5 |        1 | te
  6 |        2 | in
  7 |        5 | tea
  8 |        5 | ted
  9 |        5 | ten
 10 |        6 | inn

[AbydosOne]

36 minutes ago, Eigenvektor said:

I assume this: https://en.m.wikipedia.org/wiki/Trie

Oh, there's a name for that concept... surprised I haven't heard it before...

 

36 minutes ago, Eigenvektor said:

For example this trie could be stored as:

Couldn't you iterate up the parent IDs and store only one character at each node? Or maybe I'm missing the point of a trie (I just like iterating up pointer trails for some reason, so that's how I end up imagining algorithms).

 Id | ParentId | Value
  0 |     null | 
  1 |        0 | t
  2 |        0 | i
  3 |        0 | A
  4 |        1 | o
  5 |        1 | e
  6 |        2 | n
  7 |        5 | a
  8 |        5 | d
  9 |        5 | n
 10 |        6 | n

[Eigenvektor]

11 minutes ago, AbydosOne said:

Oh, there's a name for that concept... surprised I haven't heard it before...

 

Couldn't you iterate up the parent IDs and store only one character at each node?

Sure, you could do that. But depending on how you're using that thing, it could be much faster to have what you need right away rather than recursing through the tree. It's essentially a space vs speed tradeoff.

 

~edit: Let's say you need to check if an entry for "tea" already exists, in my example that could be done with a simple select, in your example you'd need to recurse through the entries, starting with "t", to see if you can form that combination.

[wanderingfool2]

5 hours ago, Wictorian said:

How should one store a trie in a database?

Is there any context into why you are trying to insert it into a database?

 

I mean there could be a few ways to store it.  If you are ultimately trying to store it as a dictionary, might as well just store it the way a database would work (in a table)...and then rebuild the trie on demand if you need it.

 

e.g. having a table with keys dictionary_id, word
So then you can do a select word from dictionary where dictionary_id = 123;  To get the entire dictionary.  Then iterate through creating the trie.

 

I mean you could I guess use a binary datatype, but I mean ultimately it comes back to needing to still re-import it most likely.

[Franck]

1 hour ago, Eigenvektor said:

Sure, you could do that. But depending on how you're using that thing, it could be much faster to have what you need right away rather than recursing through the tree. It's essentially a space vs speed tradeoff.

This is a really good point, creating a recursive will only optimize the storage space, not the query performance. Recursive query is extremely costly on database. If you have a thousand sub level that could be many tens of thousand of query while some speed optimized structure can do it in a single query.

[Wictorian]

1 hour ago, wanderingfool2 said:

Is there any context into why you are trying to insert it into a database?

 

I mean there could be a few ways to store it.  If you are ultimately trying to store it as a dictionary, might as well just store it the way a database would work (in a table)...and then rebuild the trie on demand if you need it.

 

e.g. having a table with keys dictionary_id, word
So then you can do a select word from dictionary where dictionary_id = 123;  To get the entire dictionary.  Then iterate through creating the trie.

 

I mean you could I guess use a binary datatype, but I mean ultimately it comes back to needing to still re-import it most likely.

what I mean by database is some dort of file on the hard drive so I dont have to reconstruct it every time I run a script.

[wanderingfool2]

36 minutes ago, Wictorian said:

what I mean by database is some dort of file on the hard drive so I dont have to reconstruct it every time I run a script.

Well I mean insertion into a Trie is pretty lightweight for inserts...it's an O(n) efficiency.

 

I mean you could always get tricky by loading all the data in some set structure so that you can just read in the file and have it in the layout you need [would vary by language].

 

Ultimately if your thought was storing it as a flat file/similar, I would just reconstruct it each time.  Unless there is a bunch of words/phrases that is really slowing it down (or calling it to load a bunch of times) then you might want to consider different methods.

 

You could do things like loading in to memory (easier in things like c/C++ kind of thing)...or other ways that I could think of would really be a lot more effort to implement than just adding in again...ie the performance gains from doing such a thing, is likely not worth the time it would take to get it optimized as such.

 

 

[Eigenvektor]

8 hours ago, Wictorian said:

what I mean by database is some dort of file on the hard drive so I dont have to reconstruct it every time I run a script.

While at the end of the day a database is technically "just a (bunch of) file(s)", it really isn't. You should normally distinguish between the two.

 

A database is optimized for fast retrieval (e.g. indexes) of individual rows and has its own query language. This can allow you to quickly load some subset of the data without having to keep everything in memory. Depending on how you're using the data, a flat file may "good enough", but as I pointed out above, databases support CTEs which can make retrieval of recursive data much more efficient.

 

In any case, you can still use the same overall structure for a flat file and e.g. use a simple CSV. You can use its columns and rows pretty much the same way as you would a single database table.

 

As @wanderingfool2 said, consider reconstructing it instead. If you're loading everything into memory on startup, loading it from disk is only really worth it if that is faster than reconstructing it on the fly. If you only need a subset and there's a good way to query what you need, then an actual database can start to make sense.

[Franck]

14 hours ago, Wictorian said:

what I mean by database is some dort of file on the hard drive so I dont have to reconstruct it every time I run a script.

If you need to load or modify portion on that data a database is what you need. If you will always and only use that tree when fully loaded you want a simple serialization.

[AnotherMax]

If you want to store it in a database you can use: Neo4J which is a graph database letting you store "nodes" and "links".

 

Alternativly and probably simpler, you can use graphviz which I use the python library (pypi) to parse graphs / construct and parse etc. These can be saved to ".dot" files and uses the "DOT Language".