Trie Tree:A trie (from retrieval), is a multi-way tree structure useful for storing strings over an alphabet. It has been used to store large dictionaries of English (say) words in spelling-checking programs and in natural-language "understanding" programs. Given the data:
The idea is that all strings sharing a common stem or prefix hang off a common node. When the strings are words over {a..z}, a node has at most 27 children - one for each letter plus a terminator.
The elements in a string can be recovered in a scan from the root to the leaf that ends a string. All strings in the trie can be recovered by a depth-first scan of the tree.
More explanation is here.
http://www.kakarak.com/dl/java/Trie2.java
http://shashank7s.blogspot.com/2011/03/wap-to-spell-checking-using-trie.html
- an, ant, all, allot, alloy, aloe, are, ate, be
The idea is that all strings sharing a common stem or prefix hang off a common node. When the strings are words over {a..z}, a node has at most 27 children - one for each letter plus a terminator.
The elements in a string can be recovered in a scan from the root to the leaf that ends a string. All strings in the trie can be recovered by a depth-first scan of the tree.
More explanation is here.
http://www.kakarak.com/dl/java/Trie2.java
http://shashank7s.blogspot.com/2011/03/wap-to-spell-checking-using-trie.html
No comments:
Post a Comment