How to design dictionary app using trie?

Question

I have planned to use trie data structure implementation in dictionary application, but the problem is loading more than 10,000 words into the trie. Though trie takes out redundancy of letters and total memory loaded in primay would nothing more than couple of kbs but still the time required for loading all the words into the trie would take a lot of time nwould take even more if it's implemented for a mobile phone app..

Any suggestions of what could be done?

i have not tested but it should take a long time.. more than 80k words are there in the database I have. Should take a considerable amount of time or the mobile may force quit the app.. :/ — Ashwin Surana
– Ashwin Surana, Commented Mar 20, 2013 at 8:23
80K is not that much, I would suggest you test it before coming to conclusions, you may be surprised. Also, what mobile phone are you targetting? Depending on your needs, if you need nothing more than just checking if a word is in the dictionary, a hash table will do the job and will be loaded faster. This is JavaScript but the concepts apply: ejohn.org/blog/javascript-trie-performance-analysis — Pin
– Pin, Commented Mar 20, 2013 at 8:43
Check this too: ejohn.org/blog/revised-javascript-dictionary-search — Pin
– Pin, Commented Mar 20, 2013 at 8:50
Thanks @pin.. interesting article .. :) Let me implement it and will be back with the results i got . :) — Ashwin Surana
– Ashwin Surana, Commented Mar 20, 2013 at 11:09

cyon · Accepted Answer · 2013-03-20 11:54:07Z

1

Instead of (or maybe in addition to) shipping a database containing a dictionary along with your app, you could ship a serialized trie containing all the dictionary words. This could be serialized in any way you want (perhaps as a blob in a database or xml file) and you could then deserialize it to create a java trie object when the app starts up.

To do this you could use a deploy script which creates the trie by going through all dicitionary words, places them into the trie and then serializes the trie into some file or blob and packages this serialized trie with the released app.

answered Mar 20, 2013 at 11:54

cyon

9,5684 gold badges24 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to design dictionary app using trie?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related