Indexing structure used in wordweb(english dictionary)

One of my friends faced this in his recent interview. I'm posting 2 questions here for better solution & fyi.

--say if you type "light", suggestions in dropdown are mostly starts with "light" and comes as and when you type and changes with every character, but if you type "tigress" or "possi", suggestions include "d开发者_如何学运维igress" or few others(same sound word?). How this suggestions feature can be achieved?

--what is the best way to store and retrieve synonyms, antonyms, types, typeof etc. have a look at those tabs.

I don't thinks this can be solved by simple dictionary kind of algo(correct me if i'm wrong). Even though he was not asked to write any sample code, this sounds like tough question for me.

First question:

I would use a Trie data structure based on the common prefix property and build it to yield ligh -> light. My guess would be, when we have to go the other way round tigress -> digress, build the Trie using common suffix property. That is, instead of building the trie, character by character, from left to right, build it from right-to-left.

Thus, tigress would be parsed as: s->s->e->r->g->i->t AND digress would be parsed as: s->s->e->r->g->i->d

I think this would work for suggestions at the beginning. But, I'd like to learn how could we support suggesting next character both at the beginning and at the end.

Re your first question.

The edit distance provides a measure of how "different" two words are. A straightforward implementation could work by comparing the entry against a master list of words (the dictionary), and then offering as suggestions the top N words with minimum score.

I'd probably use a directed acyclic word graph to store the words (to easily make suggestions based on prefix), but instead of a simple NULL for an end of word marker I'd have a terminal node which included the soundex value for the word.

Synonyms, antonyms, and soundex matches would be in a separate set of unique data structures. An associative array would suffice although just a sorted list of keys/indices into a compact data array would probably be fine for small wordsets.