Best data structure for implementing a dictionary?

by

Depending on what you want to do, there are many good data structures.

If you just want to store the words and ask “is this word here or not?”, a standard hash table with no other fancy machinery is a reasonable approach. If that word is list fixed in advance, consider using a perfect hash table to get excellent performance and space usage.

If you want to be able to check if a given prefix exists while supporting fast lookups, a trie is a good option, though it can be a bit space-inefficient. It also supports fast insertions or deletions. It also allows for iteration in alphabetical order, which hashing doesn’t offer. This is essentially the structure you’ve described in your answer, but depending on the use case other representations of tries might be better.

If in addition to the above, you know for a fact that the word list is fixed, consider using a DAWG (directed acyclic word graph), which is essentially a minimum-state DFA for the language. It’s substantially more compact than the trie, but supports many of the same operations.

If you want trie-like behavior but don’t want to pay a huge space penalty, the ternary search tree is another viable option, as is the radix tree. These are very different structures, but can be much better than the trie in different circumstances.

If space is a concern but you want a trie, look into the succinct trie representation, which has slower lookups but just about theoretically optimal space usage. The link discusses how it’s being used in JavaScript as an easy way to transmit a huge amount of data. An alternative compact representation is the double-array trie, though admittedly I know very little about it.

If you want to use the dictionary for operations like spell-checking where you need to find words similar to other words, the BK-tree is an excellent data structure to consider.

Hope this helps!

More Related Contents:

  1. Ukkonen’s suffix tree algorithm in plain English
  2. Reverse the ordering of words in a string
  3. Algorithm to convert an IEEE 754 double to a string?
  4. How to generate all the permutations of a multiset?
  5. Finding the ranking of a word (permutations) with duplicate letters
  6. Algorithm to find articles with similar text
  7. Does C have any tools for doing string addition?
  8. How to check if an integer is in a set of given ranges? [closed]
  9. Parse usable Street Address, City, State, Zip from a string [closed]
  10. hash function for string
  11. “The argument type ‘String?’ can’t be assigned to the parameter type ‘String'” when using stdin.readLineSync()
  12. Format a Go string without printing?
  13. C++/CLI Converting from System::String^ to std::string
  14. Bash: Split string into character array
  15. String with array structure to Array [duplicate]
  16. Replacing characters in Ant property
  17. How do I convert a Vec to Vec?
  18. What is the difference between tree depth and height?
  19. O(klogk) time algorithm to find kth smallest element from a binary heap
  20. Python: find closest string (from a list) to another string
  21. Approximate string matching algorithms
  22. Grouping arrays in PHP
  23. Is there an owned version of String::chars?
  24. Recursive diff of two dictionaries (keys and values)?
  25. scala string.split does not work
  26. How can I make the map::find operation case insensitive?
  27. How expensive are Python dictionaries to handle?
  28. How to get the number of characters in a string
  29. Why is vector array doubled?
  30. Does conversion between alias types in Go create copies?

Leave a Comment