The best data structure to implement a dictionary

[endazyar]

Hey everyone, I'm planning to implement a dictionary on C#. I have about 30,000 words in my database( i keep them in access database right now. Maybe we can make a decision about which database it should be. )

a word and a definition may contain from 1 to 25-30 chars.

The search should work like that ; when user types a, the app should find all the words starting with a.

So the algorithms that i thought about are;

1-) Binarysearch will fail, since there might be some duplicate elements.

2-) Binary Search Tree will fail, since i have all the words in ascending order, when i add the words to the tree, it will be an unbalanced tree( more likely a linked list ) So the performance will be O(n)

3-) Ternary Search Tree, dunno yet if i'll be ok to implement a function that finds the word starts with(...)(to find any word when user starts typing something . for example when the user type "hello" it should search for h, he, hel, hell, hello. It will definitely be so fast for finding exact word. ( and also will work fine for misspelling situations )

4-) Or should i use hash tables ?

Could please gimme some ideas. I couldnt make a decision between these things. Which one will be better or is there any other algorithm for dictionaries that you know.

Thanks in advance.

[kadghar]

I would use any SQL data base server with:

SELECT * FROM dictionary WHERE word LIKE = '[search]%'

Im not quite sure I'd be able to make an algorithm that beats MySQL in this query.

[kadghar]

Now, on the other hand. if your dictionary is well sorted, you can make a binary search to find the first and the last word that matches.

This range of words will be the one you show to the user and also you'll only be searching inside this range when a new character is written.

Or you can combine this idea with my previous post; perhaps it gives better results.

[endazyar]

thank you for ur reply, i implemented it with ternary search tree. And dont need to have a database. Just storing the data in text file since the dictionary is well sorted. Ternary search tree also helps it to find the best matched words.