‣tries‣TSTs‣applicationsAlgorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 26, 2010 8:19:33 AM5.2 TriesReview: summary of the performance of symbol-table implementationsFrequency of operations.Q. Can we do better?A. Yes, if we can avoid examining the entire key, as with string sorting.2implementationtypical caseorderedoperationsoperationson keysimplementationsearchinsertdeleteorderedoperationsoperationson keysred-black BST1.00 lg N1.00 lg N1.00 lg NyescompareTo()hashing1 †1 †1 †noequals()hashcode()† under uniform hashing assumptionString symbol table. Symbol table specialized to string keys.Goal. As fast as hashing, more flexible than binary search trees.3String symbol table basic API public class StringST<Value> public class StringST<Value>string symbol table typestring symbol table typeStringST()StringST()create an empty symbol tablevoidput(String key, Value val)put(String key, Value val)put key-value pair into the symbol tableValueget(String key)get(String key)return value paired with given keybooleancontains(String key)contains(String key)is there a value paired with the given key?4String symbol table implementations cost summaryChallenge. Efficient performance for string keys.Parameters•N = number of strings•L = length of string•R = radixfilesizewordsdistinctmoby.txt1.2 MB210 K32 Kactors.txt82 MB11.4 M900 Kcharacter accesses (typical case)character accesses (typical case)character accesses (typical case)character accesses (typical case)dedupdedupimplementationsearchhitsearchmissinsertspace(links)moby.txtactors.txtred-black BSTL + c lg 2 Nc lg 2 Nc lg 2 N4 N1.4097.4hashingLLL4 N to 16 N0.7640.65‣tries‣TSTs‣string symbol table APITries. [from retrieval, but pronounced "try"]•Store characters and values in nodes (not keys).•Each node has R children, one for each possible character.Ex. she sells sea shells by the6TriesAnatomy of a triethe5she0ells1lls3by4a2value for she in nodecorresponding tolast key characterlabel each node withcharacter associatedwith incoming linklink to trie for all keysthat start with slink to trie for all keysthat start with sherootkey value4by2sea1sells0she3shells5theFollow links corresponding to each character in the key.•Search hit: node where search ends has a non-null value. •Search miss: reach a null link or node where search ends has null value.7Search in a trieTrie search hit outcomesthe5she0ells1lls3by4a2get("shells")the5she0ells1lls3by4a2return the value in thenode corresponding tothe last key character (0)get("she")return the value in thenode corresponding tothe last key character (3)search may terminateat an internal nodeTrie search hit outcomesthe5she0ells1lls3by4a2get("shells")the5she0ells1lls3by4a2return the value in thenode corresponding tothe last key character (0)get("she")return the value in thenode corresponding tothe last key character (3)search may terminateat an internal nodeFollow links corresponding to each character in the key.•Search hit: node where search ends has a non-null value.•Search miss: reach a null link or node where search ends has null value.8Search in a trieTrie search miss outcomesthe5she0ells1lls3by4a2get("shell")the5she0ells1lls3by4a2no link for the o,so return nullget("shore")no value in the node corresponding to the last keycharacter, so return nullTrie search miss outcomesthe5she0ells1lls3by4a2get("shell")the5she0ells1lls3by4a2no link for the o,so return nullget("shore")no value in the node corresponding to the last keycharacter, so return nullFollow links corresponding to each character in the key.•Encounter a null link: create new node.•Encounter the last character of the key: set value in that node. 9Insertion into a trieTrie insertion examplesthe5she0ells1lls6by4a7put("sea", 7)the5she0ells1ll7ores3by4a2put("shore", 8)node corresponding tothe last key characterexists, so set its valuenodes corresponding tocharacters at the end of thekey do not exist, so create themand set the value of the last oneTrie insertion examplesthe5she0ells1lls6by4a7put("sea", 7)the5she0ells1ll7ores3by4a2put("shore", 8)node corresponding tothe last key characterexists, so set its valuenodes corresponding tocharacters at the end of thekey do not exist, so create themand set the value of the last one10Trie construction examplesheTrie construction trace for standard indexing clientkey value key valuerootone nodefor eachkey charactervalue is in nodecorresponding tolast characterkey is sequenceof characters fromroot to value0the5she0ells1she0ells1a2she0ells1lls3a20she1sells2sea3shellsshe0ells1lls3by4a24byshe0ells1lls3by4a25thenodes corresponding tocharacters at the end of thekey do not exist, so create themand set the value of the last onekey valueore7the5she0ells1lls3by4a66seathe5she0ells1lls3by4a67shorenode corresponding tothe last key characterexists, so reset its value11Trie representation: Java implementationNode. A value, plus references to R nodes.private static class Node{ private Object value; private Node[] next = new Node[R];}use Object instead of Value sinceno generic array creation in JavaTrie representationeach node hasan array of linksand a valuecharacters are implicitlydefined by link indexshe0ells1asheellsa012212Trie representation: Java implementationNode. A value, plus references to R nodes.private static class Node{ private Object value; private Node[] next = new Node[R];}Trie representation (R = 26)each node hasan array of linksand a valuecharacters are implicitlydefined by link indexshe0ells1asheellsa2 021use Object instead of Value sinceno generic array creation in Javapublic class TrieST<Value>{ private static final int R = 256; private Node root; private static class Node { /* see previous slide */ } public void put(String key, Value val) { root = put(root, key, val, 0); } private Node put(Node x, String key, Value val, int d) { if (x == null) x = new Node(); if (d == key.length()) { x.val = val; return x; } char c = key.charAt(d); x.next[c] = put(x.next[c], key, val, d+1); return x; }}13R-way trie: Java implementationextended ASCII public boolean contains(String key) { return get(key) != null; } public Value get(String key) { Node x = get(root, key, 0); if (x == null) return null; return (Value) x.val; } private Node get(Node x, String key, int d) { if (x == null) return null; if (d ==
View Full Document
Unlocking...