1

I have a spring boot application, that simply does, takes a set of characters and lists out possible english words. Now, as everyone knows , its fairly easy, build a trie data-structure to load up a dictionary.

Now, the problem is let's say 170,000 words in english dictionary, need to be in-memory, how do I achieve that ?

I have mostly used in-memory databases like H2 with spring boot, but I am not sure how would I store a trie in database.

Other caches (like redis) store key-value data structure, since trie is not a key-value pair, I am not sure how to store it.

Any suggestions would be welcome.

  • Have you tried just storing the object in the servers memory and see what happens? – Esben Skov Pedersen Oct 16 '19 at 6:43
  • Yeah, so how do I do that , just make a Bean with static initializer? – MithunS Oct 16 '19 at 23:14
  • Yeah something like that. Or the server startup hook. Can't remember the name right now. – Esben Skov Pedersen Oct 17 '19 at 3:16
0

A trie is a special kind of graph, where every node represents a letter with outgoing edges for each possible subsequent letter. Finding an entry consists of traversing the graph using one letter after the other.

You can therefore use all the storage techniques used for graphs. Typically a graph database would be the nice choice. But you can also use key values, the key being a node id, an the value the node content.

Worth to be mentioned: some math need to be done before, to check if it’s worth the extra complexity. With 170 000 words, a key value store with the words stored, as they are, would need 13 accesses with a binary tree index, but only 5 accesses with a B-Tree of order 10. If the average length of your word is around 5 the trie may not necessarily result in faster searches in view of the storage media access constraints. If performance matters, a benchmark could make sense. And there are some trie applications that cannot just be reduced to fulll word search either.

| improve this answer | |
  • Here is my doubt, I would rather prefer to keep this data structure in memory right. Since, each time I need to search for a word, I don't wish to query db and populate a data structure to then traverse through it to find prefix(-es) or the actual word. Second thing, I don't understand how a hashmap or key-value type structure would help, the node id has no semblance to a prefix ? Please correct me if I am wrong. – MithunS Oct 17 '19 at 1:08
  • Like any graph, in the database (be it on disk or in memory) you have to store the nodes. How do we find nodes ? Using the letter as index is not possible since several nodes will use same letter. Using the sequence of prefix is not helpful either, because then you could directly search for the full word. THerefore you'd use node id. With a good hashing function, the node could be found in O(1). This is the db equivalent for an object reference you'd use for an in-memory trie. – Christophe Oct 17 '19 at 6:45
  • Yeah, but what is the relation between node id and actual sequence of characters or prefix. If I need to search for words starting with test, how do I find the node ? – MithunS Oct 18 '19 at 16:24
  • @MithunS exactly as you do in a native trie: you start from the rootnode, you look for the edge corresponding to “t”, get to that node, look at the edge for “e” and so on. Imho, if you do not need persistence, keep the native trie. – Christophe Oct 18 '19 at 16:37
  • Can you point me to some sample code, that does this ? I am just not sure how the regular trie traversal will work on a server exposing trie as a rest-api? – MithunS Dec 18 '19 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.