Dictionary search

[HiteshVaghani1]

i am making dictionary and in that i wanted to search word..because there are millions word in that so i would like to implement best one..so please tell me,
which is the best searching techniques for dictionary search ? and how?
thanking you in advance.

[AbstractionAnon]

A lot depends on how you intend to access the dictionary.
Are you doing translation?
Do you have other information you intend to associate with each word?
Or are you doing something simple such as a spell checker or a Scrabble type of game?

The easiest to implement is set<string>.
http://www.cplusplus.com/reference/stl/set/
Search time is implementation dependent, but is usually logarithmic.

[HiteshVaghani1]

i am storing all data and meaning something like Translation..
e.g if entered smile : facial expression by spreading the lips would be output.
My question is about which algorithm would be most efficient for my code...?

[AbstractionAnon]

For storing the definition along with the word, I would recommend the map container.
map<string,string>
Where the first string is the unique dictionary word and the second string contains the definition.

Like the set container I mentioned earlier, the performance of the map container is logarithimic. It's hard to improve on the performance of STL containers.

[BlackSheep]

You could also do something like this:

struct Word
{
     std::string word;
     std::string definition;
     bool operator<(Word rhs)
         {
                return word < rhs.word;
         }
};

std::vector<Word> Dictionary;
//Push back all the words.
std::sort(Dictionary.begin(), Dictionary.end());

Then you can use a binary search algorithm. The time complexity is the same as for map, but the overhead is much less.

EDIT: The reason that you can do stuff like this with less overhead than map, but map still exists, is that a binary search on a vector requires the vector to be sorted. This means that any insertions require a full re-sort. Therefore, using a vector is generally only viable with static data.

Map on the other hand is relatively good at insertions, but again has a lot of overhead. Whichever you use depends on if you need to do insertions at runtime, or just need to parse a file, sort it, and then find the words.

[HiteshVaghani1]

@Black Sheep you are right binary search tree is bad idea for my problem..
i was thinking about M-ary tree where solution of search is path... i think that would be best for me. If you have any other suggestion than suggest me please and thank you.

[HiteshVaghani1]

@AbstractionAnon: i want to use my own data structure. STL will increase my algorithm complexity..