DAWG or B-Tree?

I want to make a simple dictionary of words now I don't know which structure is bettera B-Tree or a DAWG?I want to have the fastest search through the words?any opinion or comparision are wellcome

[218 byte] By [mehdi62ba] at [2007-10-2 2:02:28]

«« sorting by a alphabetical order with two string properties
»» What framework and tools should I use?

# 1

HashSet?

YAT_Archivista at 2007-7-15 19:43:50 >

top of Java-index,Other Topics,Algorithms...

# 2

Dictionary sounds like your words map to something, so HashMap?-) Harald.

pifpafpufa at 2007-7-15 19:43:50 >

# 3

What kind of searches will be performed? E.g. Only prefix matches or general substring matches?If you are wanting to do prefix matching, then using a triestructure is a good idea. http://www.graphbuilder.com/trie/

rkippena at 2007-7-15 19:43:50 >

# 4

>>What kind of searches will be performed? E.g.

>>Only prefix matches or general substring matches?

I thought you meant a specific word from a "general substring"

well,I want to find just a specific word not all the words which have a specific prefix,I don' know which one is better?

(for prefixes I think a DAWG is better because it would have less nodes.how I can implement DAWG?)

thanks.

mehdi62ba at 2007-7-15 19:43:50 >

# 5

Both DAWG and B-Tree are general structures. If you want to determine if a word is in a container, then you could throw all the words in a hashtable. Depends what how the words are going to be searched, which seems unclear at the moment. Both hashtable and trie offer O(1) lookup. Tries have the added advantage of prefix matching in O(1) time. B-Tree would be log(n). DAWG is just a general name, directed acyclic weighted graph.Not sure how you plan on using DAWG to find words.

rkippena at 2007-7-15 19:43:50 >

# 6

>>Both hashtable and trie offer O(1) lookup. Tries have the added >>advantage of prefix matching in O(1) time. B-Tree would be log(n). yes,I got it!

mehdi62ba at 2007-7-15 19:43:50 >

# 7

> DAWG is just a general name, directed acyclic weighted graph.Actually it has an alternative expansion of directed acyclic word graph, according to DADS.

YAT_Archivista at 2007-7-15 19:43:50 >

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

DAWG or B-Tree?

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified