recommended data structure while designing something like a dictionary?

Is TRIE the most recommended data structure while designing something like a dictionary for storing words? Any other alternatives that improve either the time or memory performance?

I believe a hash may be good if there's no collision but then memory requirements start getting bad for overlapping words: over, overlap, overlaps, overlapped, overlapping all occupy exclusive storage while we could share space in trie.

EDIT: Thanks @Moron and to all of you for the very useful answers. I agree -- generating the hash key is O(n) and so is a TRIE search. However, for hash things can be worse with chaining adding to the time while for TRIE this will not happen. My concern remains that for every node in a TRIE I need to keep a pointer which may be blowing things if the dictionary size is small.

A trie has the following advantages over a Hash table:

Looking up data in a trie is faster in the worst case, O(m) time, compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.
There are no collisions of different keys in a trie.
Buckets in a trie which are analogous to hash table buckets that store key collisions are only necessary if a single key is associated with more than one value.
There is no need to provide a hash function or to change hash functions as more keys are added to a trie.
A trie can provide an alphabetical ordering of the entries by key.

Tries have the following drawbacks:

Tries can be slower in some cases than hash tables for looking up data, especially if the data is directly accessed on a hard disk drive or some other secondary storage device where the random access time is high compared to main memory.
It is not easy to represent all keys as strings, such as floating point numbers - a straightforward encoding using the bitstring of their encoding leads to long chains and prefixes that are not particularly meaningful.

If the drawbacks are something that you can live with, I'd suggest going with the trie.

Source: Wikipedia: Trie#As a replacement of other data structures

+1. I don't think drawback #2 applies though, the OP clearly mentions he needs it to store words like in a dictionary.

MAK 2010-07-07 18:58:53

I'd classify a hash table with a worst-case lookup time of O(N) as "pathological" not "imperfect"! Even if every entry hashed to the same bucket, you normally keep the overflow chain sorted and do a binary search on that.

TMN 2010-07-07 19:09:15

@MAK that's right #2 doesn't apply to his case.

Vivin Paliath 2010-07-07 19:41:22

@Arpan: If space is important, I would recommend a DAWG (see my answer) which is kind of a generalization of a trie, but it saves space both in prefixes (like tries do) and suffixes (like tries don't).

Moron 2010-07-07 21:35:12

@TMN: I would even consider using a second hash table (different hash function) as a bucket.

Matthieu M. 2010-07-08 13:51:40

@Matthieu: That's interesting, I wonder if that might be leveraged for multi-part keys (e.g., hash first on post code, then again by surname).

TMN 2010-07-09 12:30:58

You mean O(1) for reasonable hashes?

Justin K 2010-07-07 18:42:23

@Justin: No I mean O(n), where n = length of word to be searched. n is not the size of dictionary.

Moron 2010-07-07 18:46:28

@Moron: hashing the key and searching the hash table using the resultant hash are considered two separate operations (since the search can't really start until the hash is available), so hash table search is considered to have O(1) cost (for reasonable hashes).

TMN 2010-07-07 19:18:01

@TMN. You also need to consider the time taken to compute the hash, especially for _supercalifragilisticexpialidocious_ words. And sorry, I don't agree that it can be ignored, especially when you consider your input size = size of word.

Moron 2010-07-07 21:22:23

@Moron: Yeah, I seem to have overlooked the definition of n in the question. Sorry.

Justin K 2010-07-07 21:32:16

+1 for mentioning DAWG. DAWG is essentially a trie but with identical suffixes collapsed. BTW, wiki failed to cite the paper where DAWG was first proposed. It is a paper published in 1985.

2010-07-08 02:27:15

@Moron: depends on the hash. Lots of hash functions truncate or pad keys as appropriate so they always have a fixed-size key to operate on.

TMN 2010-07-08 19:00:08

@TMN: If you start ignoring characters when hashing, you will increase the chance of collisions. That is why I said 'reasonable' hash. If the hash computation for strings is O(1), then the collision chance would be too high.

Moron 2010-07-08 19:24:54

@Moron: Not really. Theoretically "more is better", but you hit a point of diminishing returns once your key size of more than twice your hash size (8 chars for a 32-bit hash, and who uses 2GB hash tables?). Don't forget, your hash needs to work for small keys as well as large ones, so it can't rely on key size for good distribution.

TMN 2010-07-08 20:02:21

@TMN: You seem to be arguing that hashes are not a good idea when your keys are variable length strings. Don't dispute that :-)

Moron 2010-07-08 20:13:34

@Moron: No, what I'm saying is that hashes have O(1) search cost which is invariant on key length. If you don't believe me, then maybe I'll be the guy they hire to come in and fix up your code. ;)

TMN 2010-07-09 12:23:29

@TMN: It is obvious that if you consider only a fixed part of the key, the hash function will suck when keys could get arbitrarly long (which is obvious when we start talking about our string length/key size being the input size!). Sorry, they won't hire you :-) Anyway, no point continuining this discussion further.

Moron 2010-07-09 13:44:57

@Moron:I never said a "fixed part"; typically one would take something like the first N/2 and the last N/2 chars, or use the Fibonacci sequence as character indexes. Obviously you've never written a production-quality hash function, so I agree, further discussion is pointless.

TMN 2010-07-12 13:43:34

ansaurus

tags:

views:

answers:

recommended data structure while designing something like a dictionary?

related questions