Open Mind Tree

if you are all thinking what is cloud computing then there is a good video which you can all check out

Data Structures, Algorithms, & Applications in Java
Tries
Copyright 1999 Sartaj Sahni

What Is A Trie?
Let us, for a moment, step back and reflect on the many sort methods developed in the text. We see that the majority of these methods (e.g., insertion sort, bubble sort, selection sort, heap sort, merge sort, and quick sort) accomplish the sort by comparing pairs of elements. Radix sort (and bin sort, which is a special case of radix sort), on the other hand, does not perform a single comparison between elements. Rather, in a radix sort, we decompose keys into digits using some radix; and the elements are sorted digit by digit using a bin sort.

Now, let us reflect on the dictionary methods developed in the text. The hashing methods use a hash function to determine a home bucket, and then use element (or key) comparisons to search either the home bucket chain (in the case of a chained hash table) or a contiguous collection of full buckets beginning with the home bucket (in the case of linear open addressing). The search tree data structures direct the search based on the result of comparisons performed between the search key and the element(s) in the root of the current subtree. We have not, as yet, seen a dictionary data structure that is based on the digits of the keys!

The trie (pronounced ``try'' and derived from the word retrieval) is a data structure that uses the digits in the keys to organize and search the dictionary. Although, in practice, we can use any radix to decompose the keys into digits, in our examples, we shall choose our radixes so that the digits are natural entities such as decimal digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) and letters of the English alphabet (a-z, A-Z).

Suppose that the elements in our dictionary are student records that contain fields such as student name, major, date of birth, and social security number (SS#). The key field is the social security number, which is a nine digit decimal number. To keep the example manageable, assume that the dictionary has only five elements. The name and SS# fields for each of the five elements in our dictionary are shown below.

Name | Social Security Number (SS#)
Jack | 951-94-1654
Jill | 562-44-2169
Bill | 271-16-3624
Kathy | 278-49-1515
April | 951-23-7625
Figure 1 Five elements (student records) in a dictionary

To obtain a trie representation for these five elements, we first select a radix that will be used to decompose each key into digits. If we use the radix 10, the decomposed digits are just the decimal digits shown in Figure 1. We shall examine the digits of the key field (i.e., SS#) from left to right. Using the first digit of the SS#, we partition the elements into three groups--elements whose SS# begins with 2 (i.e., Bill and Kathy), those that begin with 5 (i.e., Jill), and those that begin with 9 (i.e., April and Jack). Groups with more than one element are partitioned using the next digit in the key. This partitioning process is continued until every group has exactly one element in it.

The partitioning process described above naturally results in a tree structure that has 10-way branching as is shown in Figure 2. The tree employs two types of nodes--branch nodes and element nodes. Each branch node has 10 children (or pointer/reference) fields. These fields, child[0:9], have been labeled 0, 1, ..., 9 for the root node of Figure 2. root.child[i] points to the root of a subtrie that contains all elements whose first digit is i. In Figure 2, nodes A, B, D, E, F, and I are branch nodes. The remaining nodes, nodes C, G, H, J, and K are element nodes. Each element node contains exactly one element of the dictionary. In Figure 2, only the key field of each element is shown in the element nodes.

Figure 2 Trie for the elements of Figure 1


Searching a Trie
To search a trie for an element with a given key, we start at the root and follow a path down the trie until we either fall off the trie (i.e., we follow a null pointer in a branch node) or we reach an element node. The path we follow is determined by the digits of the search key. Consider the trie of Figure 2. Suppose we are to search for an element with key 951-23-7625. We use the first digit, 9, in the key to move from the root node A to the node A.child[9] = D. Since D is a branch node, we use the next digit, 5, of the key to move further down the trie. The node we reach is D.child[5] = F. To move to the next level of the trie, we use the next digit, 1, of the key. This move gets us to the node F.child[1] = I. Once again, we are at a branch node and must move further down the trie. For this move, we use the next digit, 2, of the key, and we reach the element node I.child[2] = J. When an element node is reached, we compare the search key and the key of the element in the reached element node. Performing this comparison at node J, we get a match. The element in node J, is to be returned as the result of the search.

When searching the trie of Figure 2 for an element with key 951-23-1669, we follow the same path as followed for the key 951-23-7625. The key comparison made at node J tells us that the trie has no element with key 951-23-1669, and the search returns the value null.

To search for the element with key 562-44-2169, we begin at the root A and use the first digit, 5, of the search key to reach the element node A.child[5] = C. The key of the element in node C is compared with the search key. Since the two keys agree, the element in node C is returned.

When searching for an element with key 273-11-1341, we follow the path A, A.child[2] = B, B.child[7] = E, E.child[3] = null. Since we fall off the trie, we know that the trie contains no element whose key is 273-11-1341.

When analyzing the complexity of trie operations, we make the assumption that we can obtain the next digit of a key in O(1) time. Under this assumption, we can search a trie for an element with a d digit key in O(d) time.

Keys With Different Length
In the example of Figure 2, all keys have the same number of digits (i.e., 9). In applications in which different keys may have a different number of digits, we normally add a special digit (say #) at the end of each key so that no key is a prefix of another. To see why this is done, consider the example of Figure 2. Suppose we are to search for an element with the key 27. Using the search strategy just described, we reach the branch node E. What do we do now? There is no next digit in the search key that can be used to reach the terminating condition (i.e., you either fall off the trie or reach an element node) for downward moves. To resolve this problem, we add the special digit # at the end of each key and also increase the number of children fields in an element node by one. The additional child field is used when the next digit equals #.

Height of a Trie
In the worst case, a root-node to element-node path has a branch node for every digit in a key. Therefore, the height of a trie is at most number of digits + 1.

A trie for social security numbers has a height that is at most 10. If we assume that it takes the same time to move down one level of a trie as it does to move down one level of a binary search tree, then with at most 10 moves we can search a social-security trie. With this many moves, we can search a binary search tree that has at most 210 - 1 = 1023 elements. This means that, we expect searches in the social security trie to be faster than searches in a binary search tree (for student records) whenever the number of student records is more than 1023. The breakeven point will actually be less than 1023 because we will normally not be able to construct full or complete binary search trees for our element collection.

Since a SS# is nine digits, a social security trie can have up to 109 elements in it. An AVL tree with 109 elements can have a height that is as much as (approximately) 1.44 log2(109+2) = 44. Therefore, it could take us four times as much time to search for elements when we organize our student record dictionary as an AVL tree than when this dictionary is organized as a trie!

Space Required and Alternative Node Structures
The use of branch nodes that have as many child fields as the radix of the digits (or one more than this radix when different keys may have different length) results in a fast search algorithm. However, this node structure is often wasteful of space because many of the child fields are null. A radix r trie for d digit keys requires O(rdn) child fields, where n is the number of elements in the trie. To see this, notice that in a d digit trie with n information nodes, each information node may have at most d ancestors, each of which is a branch node. Therefore, the number of branch nodes is at most dn. (Actually, we cannot have this many branch nodes, because the information nodes have common ancestors like the root node.)

We can reduce the space requirements, at the expense of increased search time, by changing the node structure. For example, each branch node of a trie could be replaced by any of the following:
A chain of nodes, each node having the three fields digitValue, child, next. Node A of Figure 2, for example, would be replaced by the chain shown in Figure 3.

Figure 3 Chain for node A of Figure 2


The space required by a branch node changes from that required for r children/pointer/reference fields to that required for 2p pointer fields and p digit value fields, where p is the number of children fields in the branch node that are not null. Under the assumption that pointer fields and digit value fields are of the same size, a reduction in space is realized when more than two-thirds of the children fields in branch nodes are null. In the worst case, almost all the branch nodes have only 1 field that is not null and the space savings become almost (1 - 3/r) * 100%.

A (balanced) binary search tree in which each node has a digit value and a pointer to the subtrie for that digit value. Figure 4 shows the binary search tree for node A of Figure 2.

Figure 4 Binary search tree for node A of Figure 2


Under the assumption that digit values and pointers take the same amount of space, the binary search tree representation requires space for 4p fields per branch node, because each search tree node has fields for a digit value, a subtrie pointer, a left child pointer, and a right child pointer. The binary search tree representation of a branch node saves us space when more than three-fourths of the children fields in branch nodes are null. Note that for large r, the binary serach tree is faster to search than the chain described above.

A binary trie (i.e., a trie with radix 2). Figure 5 shows the binary trie for node A of Figure 2. The space required by a branch node represented as a binary trie is at most (2 * ceil(log2r) + 1)p.

Figure 5 Binary trie for node A of Figure 2


A hash table. When a hash table with a sufficiently small loading density is used, the expected time performance is about the same as when the node structure of Figure 1 is used. Since we expect the fraction of null child fields in a branch node to vary from node to node and also to increase as we go down the trie, maximum space efficiency is obtained by consolidating all of the branch nodes into a single hash table. To accomplish this, each node in the trie is assigned a number, and each parent to child pointer is replaced by a triple of the form (currentNode, digitValue, childNode). The numbering scheme for nodes is chosen so as to easily distinguish between branch and information nodes. For example, if we expect to have at most 100 elements in the trie at any time, the numbers 0 through 99 are reserved for information nodes and the numbers 100 on up are used for branch nodes. The information nodes are themselves represented as an array information[100]. (An alternative scheme is to represent pointers as tuples of the form (currentNode, digitValue, childNode, childNodeIsBranchNode), where childNodeIsBranchNode = true iff the child node is a branch node.)

Suppose that the nodes of the trie of Figure 2 are assigned numbers as given below. This number assignment assumes that the trie will have no more than 10 elements.

Node A B C D E F G H I J K
Number 10 11 0 12 13 14 1 2 15 3 4


The pointers in node A are represented by the tuples (10,2,11), (10,5,0), and (10,9,12). The pointers in node E are represented by the tuples (13,1,1) and (13,8,2).

The pointer triples are stored in a hash table using the first two fields (i.e., the currentNode and digitValue) as the key. For this purpose, we may transform the two field key into an integer using the formula currentNode * r + digitValue, where r is the trie radix, and use the division method to hash the transformed key into a home bucket. The data presently in information node i is stored in information[i].

To see how all this works, suppose we have set up the trie of Figure 2 using the hash table scheme just described. Consider searching for an element with key 278-49-1515. We begin with the knowledge that the root node is assigned the number 10. Since the first digit of the search key is 2, we query our hash table for a pointer triple with key (10,2). The hash table search is successful and the triple (10,2,11) is retrieved. The childNode component of this triple is 11, and since all information nodes have a number 9 or less, the child node is determined to be a branch node. We make a move to the branch node 11. To move to the next level of the trie, we use the second digit 7 of the search key. For the move, we query the hash table for a pointer with key (11,7). Once again, the search is successful and the triple (11,7,13) is retrieved. The next query to the hash table is for a triple with key (13,8). This time, we obtain the triple (13,8,2). Since, childNode = 2 < 10, we know that the pointer gets us to an information node. So, we compare the search key with the key of the element information[2]. The keys match, and we have found the element we were looking for. When searching for an element with key 322-167-8976, the first query is for a triple with key (10,3). The hash table has no triple with this key, and we conclude that the trie has no element whose key equals the search key. The space needed for each pointer triple is about the same as that needed for each node in the chain of nodes representation of a trie node. Therefore, if we use a linear open addressed hash table with a loading density of alpha, the hash table scheme will take approximately (1/alpha - 1) * 100% more space than required by the chain of nodes scheme. However, when the hash table scheme is used, we can retrieve a pointer in O(1) expected time, whereas the time to retrieve a pointer using the chain of nodes scheme is O(r). When the (balanced) binary search tree or binary trie schemes are used, it takes O(log r) time to retrieve a pointer. For large radixes, the hash table scheme provides significant space saving over the scheme of Figure 2 and results in a small constant factor degradation in the expected time required to perform a search. The hash table scheme actually reduces the expected time to insert elements into a trie, because when the node structure of Figure 2 is used, we must spend O(r) time to initialize each new branch node (see the description of the insert operation below). However, when a hash table is used, the insertion time is independent of the trie radix. To support the removal of elements from a trie represented as a hash table, we must be able to reuse information nodes. This reuse is accomplished by setting up an available space list of information nodes that are currently not in use (see Section 3.5 (Simulating Pointers) of the text). Inserting into a Trie To insert an element theElement whose key is theKey, we first search the trie for an existing element with this key. If the trie contains such an element, then we replace the existing element with theElement. When the trie contains no element whose key equals theKey, theElement is inserted into the trie using the following procedure. Case 1 For Insert Procedure If the search for theKey ended at an element node X, then the key of the element in X and theKey are used to construct a subtrie to replace X. Suppose we are to insert an element with key 271-10-2529 into the trie of Figure 2. The search for the key 271-10-2529 terminates at node G and we determine that the key, 271-16-3624, of the element in node G is not equal to the key of the element to be inserted. Since the first three digits of the keys are used to get as far as node E of the trie, we set up branch nodes for the fourth digit (from the left) onwards until we reach the first digit at which the two keys differ. This results in branch nodes for the fourth and fifth digits followed by element nodes for each of the two elements. Figure 6 shows the resulting trie. Figure 6 Trie of Figure 2 with 271-10-2529 inserted Case 2 For Insert Procedure If the search for theKey ends by falling off the trie from the branch node X, then we simply add a child (which is an element node) to the node X. The added element node contains theElement. Suppose we are to insert an element with key 987-33-1122 to the trie of Figure 2. The search for an element with key equal to 987-33-1122 ends when we fall off the trie while following the pointer D.child[8]. We replace the null pointer D.child[8] with a pointer to a new element node that contains theElement, as is shown in Figure 7. Figure 7 Trie of Figure 2 with 987-33-1122 inserted The time required to insert an element with a d digit key into a radix r trie is O(dr) because the insertion may require us to create O(d) branch nodes and it takes O(r) time to intilize the children pointers in a branch node. Removing an Element To remove the element whose key is theKey, we first search for the element with this key. If there is no matching element in the trie, nothing is to be done. So, assume that the trie contains an element theElement whose key is theKey. The element node X that contains theElement is discarded, and we retrace the path from X to the root discarding branch nodes that are roots of subtries that have only 1 element in them. This path retracing stops when we either reach a branch node that is not discarded or we discard the root. Consider the trie of Figure 7. When the element with key 951-23-7625 is removed, the element node J is discarded and we follow the path from node J to the root node A. The branch node I is discarded because the subtrie with root I contains the single element node K. We next reach the branch node F. This node is also discarded, and we proceed to the branch node D. Since the subtrie rooted at D has 2 element nodes (K and L), this branch node is not discarded. Instead, node K is made a child of this branch node, as is shown in Figure 8. Figure 8 Trie of Figure 7 with 951-23-7635 removed To remove the element with key 562-44-2169 from the trie of Figure 8, we discard the element node C. Since its parent node remains the root of a subtrie that has more than one element, the parent node is not discarded and the removal operation is complete. Figure 9 show the resulting trie. Figure 9 Trie of Figure 8 with 562-44-2169 removed The time required to remove an element with a d digit key from a radix r trie is O(dr) because the removal may require us to discard O(d) branch nodes and it takes O(r) time to determine whether a branch node is to be discarded. The complexity of the remove operation can be reduced to O(r+d) by adding a numberOfElementsInSubtrie field to each branch node. Prefix Search and Applications You have probably realized that to search a trie we do not need the entire key. Most of the time, only the first few digits (i.e., a prefix) of the key is needed. For example, our search of the trie of Figure 2 for an element with key 951-23-7625 used only the first four digits of the key. The ability to search a trie using only the prefix of a key enables us to use tries in applications where only the prefix might be known or where we might desire the user to provide only a prefix. Some of these applications are described below. Criminology Suppose that you are at the scene of a crime and observe the first few characters CRX on the registration plate of the getaway car. If we have a trie of registration numbers, we can use the characters CRX to reach a subtrie that contains all registration numbers that begin with CRX. The elements in this subtrie can then be examined to see which cars satisfy other properties that might have been observed. Automatic Command Completion When using an operating system such as Unix or DOS, we type in system commands to accomplish certain tasks. For example, the Unix and DOS command cd may be used to change the current directory. Figure 10 gives a list of commands that have the prefix ps (this list was obtained by executing the command ls /usr/local/bin/ps* on a Unix system). ps2ascii ps2pdf psbook psmandup psselect ps2epsi ps2pk pscal psmerge pstopnm ps2frag ps2ps psidtopgm psnup pstops ps2gif psbb pslatex psresize pstruct Figure 10 Commands that begin with "ps" We can simply the task of typing in commands by providing a command completion facility which automatically types in the command suffix once the user has typed in a long enough prefix to uniquely identify the command. For instance, once the letters psi have been entered, we know that the command must be psidtopgm because there is only one command that has the prefix psi. In this case, we replace the need to type in a 9 character command name by the need to type in just the first 3 characters of the command! A command completion system is easily implemented when the commands are stored in a trie using ASCII characters as the digits. As the user types the command digits from left to right, we move down the trie. The command may be completed as soon as we reach an element node. If we fall off the trie in the process, the user can be informed that no command with the typed prefix exists. Although we have described command completion in the context of operating system commands, the facilty is useful in other environments: A network browser keeps a history of the URLs of sites that you have visited. By organizing this history as a trie, the user need only type the prefix of a previously used URL and the browser can complete the URL. A word processor can maintain a dictionary of words and can complete words as you type the text. Words can be completed as soon as you have typed a long enough prefix to identify the word uniquely. An automatic phone dialler can maintain a list of frequently called telephone numbers as a trie. Once you have punched in a long enough prefix to uniquely identify the phone number, the dialler can complete the call for you. LZW Compression Algorithm The LZW compression algorithm was developed in Section 7.5 of the text. Recall that the primary operation performed during compression is the determination of the longest prefix (of the uncompressed portion of the file that is begin compressed) for which we have a code in the code table. Let us call this operation longestPrefix. In Section 7.5.2, the code table was implemented as a hash table and the operation longestPrefix was performed by searching this hash table first using a prefix of size 1, then a prefix of size 2, and so on until the first unsuccessful search. Since each hash table search has an expected complexity of O(1), a longestPrefix operation takes O(s) expected time, where s is the length of the longest prefix for which we have a code in our code table. We may use a trie for the code table. In this application, we add a code field to each branch node. The code field of a branch node gives the code for the string defined by the path from the trie root to this branch node. The trie for LZW codes has no element nodes. The longestPrefix operation may be implemented as follows. Scan the characters in the uncompressed portion of the file from left to right. Use these characters to follow a path down the code trie until you fall off the trie. Once you fall off, the longest matching prefix is identified, and the code for this prefix is in the code field of the branch node you fell off of. Using a trie, the actual complexity of the longestPrefix operation is O(s). Compressed Tries Take a close look at the trie of Figure 2. This trie has a few branch nodes (nodes B, D, and F) that do not partition the elements in their subtrie into two or more nonempty groups. We often can improve both the time and space performance metrics of a trie by eliminating all branch nodes that have only one child. The resulting trie is called a compressed trie. When branch nodes with a single child are removed from a trie, we need to keep additional information so that dictionary operations may be performed correctly. The additional information stored in three compressed trie structures is described below. Compressed Tries with Digit Numbers In a compressed trie with digit numbers, each branch node has an additional field digitNumber that tells us which digit of the key is used to branch at this node. Figure 11 shows the compressed trie with digit numbers that corresponds to the trie of Figure 2. The leftmost field of each branch node of Figure 11 is the digitNumber field. Figure 11 Compressed trie with digit numbers Searching a Compressed Trie with Digit Numbers A compressed trie with digit numbers may be searched by following a path from the root. At each branch node, the digit, of the search key, given in the branch node's digitNumber field is used to determine which subtrie to move to. For example, when searching the trie of Figure 11 for an element with key 951-23-7625, we start at the root of the trie. Since the root node is a branch node with digitNumber = 1, we use the first digit 9 of the search key to determine which subtrie to move to. A move to node A.child[9] = I is made. Since, I.digitNumber = 4, the fourth digit, 2, of the search key tells us which subtrie to move to. A move is now made to node I.child[2] = J. We are now at an element node, and the search key is compared with the key of the element in node J. Since the keys match, we have found the desired element. Notice that a search for an element with key 913-23-7625 also terminates at node J. However, the search key and the element key at node J do not match and we conclude that the trie contains no element with key 913-23-7625. Inserting into a Compressed Trie with Digit Numbers To insert an element with key 987-26-1615 into the trie of Figure 11, we first search for an element with this key. The search ends at node J. Since, the search key and the key, 951-23-7625, of the element in this node do not match, we conclude that the trie has no element whose key matches the search key. To insert the new element, we find the first digit where the search key differs from the key in node J and create a branch node for this digit. Since, the first digit where the search key 987-26-1615 and the element key 951-23-7625 differ is the second digit, we create a branch node with digitNumber = 2. Since, digit values increase as we go down the trie, the proper place to insert the new branch node can be determined by retracing the path from the root to node J and stopping as soon as either a node with digit value greater than 2 or the node J is reached. In the trie of Figure 11, this path retracing stops at node I. The new branch node is made the parent of node I, and we get the trie of Figure 12. Figure 12 Compressed trie following the insertion of 987-26-1615 into the compressed trie of Figure 11 Consider inserting an element with key 958-36-4194 into the compressed trie of Figure 11. The search for an element with this key terminates when we fall of the trie by following the pointer I.child[3] = null. To complete the insertion, we must first find an element in the subtrie rooted at node I. This element is found by following a downward path from node I using (say) the first non null link in each branch node encountered. Doing this on the compressed trie of Figure 11, leads us to node J. Having reached an element node, we find the first digit where the element key and the search key differ and complete the insertion as in the previous example. Figure 13 shows the resulting compressed trie. Figure 13 Compressed trie following the insertion of 958-36-4194 into the compressed trie of Figure 11 Because of the possible need to search for the first non null child pointer in each branch node, the time required to insert an element into a compressed tries with digit numbers is O(rd), where r is the trie radix and d is the maximum number of digits in any key. Removing an Element from a Compressed Trie with Digit Numbers To remove an element whose key is theKey, we do the following: Find the element node X that contains the element whose key is theKey. Discard node X. If the parent of X is left with only one child, discard the parent node also. When the parent of X is discarded, the sole remaining child of the parent of X becomes a child of the grandparent (if any) of X. To remove the element with key 951-94-1654 from the compressed trie of Figure 13, we first locate the node K that contains the element that is to be removed. When this node is discarded, the parent I of K is left with only one child. Consequently, node I is also discarded, and the only remaining child J of node I is the made a child of the grandparent of K. Figure 14 shows the resulting compressed trie. Figure 14 Compressed trie following the removal of 951-94-1654 from the compressed trie of Figure 13 Because of the need to determine whether a branch node is left with two or more children, removing a d digit element from a radix r trie takes O(d+r) time. Compressed Tries with Skip Fields In a compressed trie with skip fields, each branch node has an additional field skip which tells us the number of branch nodes that were originally between the current branch node and its parent. Figure 15 shows the compressed trie with skip fields that corresponds to the trie of Figure 2. The leftmost field of each branch node of Figure 15 is the skip field. Figure 15 Compressed trie with skip fields The algorithms to search, insert, and remove are very similar to those used for a compressed trie with digit numbers. Compressed Tries with Edge Information In a compressed trie with edge information, each branch node has the following additional information associated with it: a pointer/reference element to an element (or element node) in the subtrie, and an integer skip which equals the number of branch nodes eliminated between this branch node and its parent. Figure 16 shows the compressed trie with edge information that corresponds to the trie of Figure 2. The first field of each branch node is its element field, and the second field is the skip field. Figure 16 Compressed trie with edge information Even though we store the ``edge information'' with branch nodes, it is convenient to think of this information as being associated with the edge that comes into the branch node from its parent (when the branch node is not the root). When moving down a trie, we follow edges, and when an edge is followed. we skip over the number of digits given by the skip field of the edge information. The value of the digits that are skipped over may be determined by using the element field. When moving from node A to node I of the compressed trie of Figure 16, we use digit 1 of the key to determine which child field of A is to be used. Also, we skip over the next 2 digits, that is, digits 2 and 3, of the keys of the elements in the subtrie rooted at I. Since all elements in the subtrie I have the same value for the digits that are skipped over, we can determine the value of these skipped over digits from any of the elements in the subtrie. Using the element field of the edge information, we access the element node J, and determine that the digits that are skipped over are 5 and 1. Searching a Compressed Trie with Edge Information When searching a compressed trie with edge information, we can use the edge information to terminate unsuccessful searches (possibly) before we reach an element node or fall off the trie. As in the other compressed trie variants, the search is done by following a path from the root. Suppose we are searching the compressed trie of Figure 16 for an element with key 921-23-1234. Since the skip value for the root node is 0, we use the first digit 9 of the search key to determine which subtrie to move to. A move to node A.child[9] = I is made. By examining the edge information (stored in node I), we determine that, in making the move from node A to node I, the digits 5 and 1 are skipped. Since these digits do not agree with the next two digits of the search key, the search terminates with the conclusion that the trie contains no element whose key equals the search key. Inserting into a Compressed Trie with Edge Information To insert an element with key 987-26-1615 into the compressed trie of Figure 16, we first search for an element with this key. The search terminates unsuccessfully when we move from node A to node I because of a mismatch between the skipped over digits and the corresponding digits of the search key. The first mismatch is at the first skipped over digit. Therefore, we insert a branch node L between nodes A and I. The skip value for this branch node is 0, and its element field is set to reference the element node for the newly inserted element. We must also change the skip value of I to 1. Figure 17 shows the resulting compressed trie. Figure 17 Compressed trie following the insertion of 987-26-1615 into the compressed trie of Figure 16 Suppose we are to insert an element with key 958-36-4194 into the compressed trie of Figure 16. The search for an element with this key terminates when we move to node I because of a mismatch between the digits that are skipped over and the corresponding digits of the search key. A new branch node is inserted between nodes A and I and we get the compressed trie that is shown in Figure 18. Figure 18 Compressed trie following the insertion of 958-36-4194 into the compressed trie of Figure 16 The time required to insert a d digit element into a radix r compressed trie with edge information is O(r+d). Removing an Element from a Compressed Trie with Edge Information This is similar to removal from a compressed trie with digit numbers except for the need to update the element fields of branch nodes whose element field references the removed element. Space Required by a Compressed Trie Since each branch node partitions the elements in its subtrie into two or more nonempty groups, an n element compressed trie has at most n-1 branch nodes. Therefore, the space required by each of the compressed trie variants described by us is O(nr), where r is the trie radix. When compressed tries are represented as hash tables, we need an additional data structure to store the nonpointer fields of branch nodes. We may use an array (much like we use the array information) for this purpose. Exercises Draw the compressed trie with digit numbers for the keys aabbbbaaa, bbbaaabb, aaabaabb, aaaaabaaa, bbbaabaa, and aabba. You will need to append a special symbol (code class=var># to each of the keys.
Draw the information on edge compressed trie for the keys aabbbbaaa, bbbaaabb, aaabaabb, aaaaabaaa, bbbaabaa, and aabba. You will need to append a special symbol (code class=var># to each of the keys.
Develop the class CompressedTrieWithDigitNumber which implements compressed tries with digit numbers. Use nodes that have as many children fields as the alphabet size plus one (for the special symol at the end of each key). You must include methods to search (both exact match and prefix match), insert, and remove.
Develop the class CompressedTrieWithDigitNumber which implements compressed tries with digit numbers. Use the hash table scheme. You must include methods to search (both exact match and prefix match), insert, and remove.
Develop the class CompressedTrieWithEdgeInformation which implements compressed tries with digit numbers. Use nodes that have as many children fields as the alphabet size plus one (for the special symol at the end of each key). You must include methods to search (both exact match and prefix match), insert, and remove.
Develop the class CompressedTrieWithEdgeInformation which implements compressed tries with digit numbers. Use the hash table scheme. You must include methods to search (both exact match and prefix match), insert, and remove.


References and Selected Readings
For more information on tries, see the texts:
The Art of Computer Programming: Sorting and Searching, Second Edition, by D. Knuth, Addison-Wesley, 1998.
Fundamentals of Data Structures in C++, by E. Horowitz, S. Sahni, and D. Mehta, Computer Science Press, 1995.


In these texts, the discussion of alternatives to scanning keys from left to right, external tries, and the data structure Patricia (practical algorithm for information coded in alphanumeric), which is a binary trie in which element nodes are replaced by a single element field in each branch node is of particular interest.

hey guys got this great tutorial in data structure pls do check it out

BREADTH FIRST SEARCH
December 16th, 2009 | Author: Robin
Breadth First Search (BFS) searches breadth-wise in the problem space. Breadth-First search is like traversing a tree where each node is a state which may a be a potential candidate for solution. Breadth first search expands nodes from the root of the tree and then generates one level of the tree at a time until a solution is found. It is very easily implemented by maintaining a queue of nodes. Initially the queue contains just the root. In each iteration, node at the head of the queue is removed and then expanded. The generated child nodes are then added to the tail of the queue.

ALGORITHM: BREADTH-FIRST SEARCH

Create a variable called NODE-LIST and set it to the initial state.
Loop until the goal state is found or NODE-LIST is empty.
Remove the first element, say E, from the NODE-LIST. If NODE-LIST was empty then quit.
b) For each way that each rule can match the state described in E do:
i) Apply the rule to generate a new state.
ii) If the new state is the goal state, quit and return this state.
Iii) Otherwise add this state to the end of NODE-LIST

Since it never generates a node in the tree until all the nodes at shallower levels have been generated, breadth-first search always finds a shortest path to a goal. Since each node can be generated in constant time, the amount of time used by Breadth first search is proportional to the number of nodes generated, which is a function of the branching factor b and the solution d. Since the number of nodes at level d is bd, the total number of nodes generated in the worst case is b + b2 + b3 +… + bd i.e. O(bd) , the asymptotic time complexity of breadth first search.

ADVANTAGES OF BREADTH-FIRST SEARCH

Breadth first search will never get trapped exploring the useless path forever.
If there is a solution, BFS will definitely find it out.
If there is more than one solution then BFS can find the minimal one that requires less number of steps.

DISADVANTAGES OF BREADTH-FIRST SEARCH

The main drawback of Breadth first search is its memory requirement. Since each level of the tree must be saved in order to generate the next level, and the amount of memory is proportional to the number of nodes stored, the space complexity of BFS is O(bd). As a result, BFS is severely space-bound in practice so will exhaust the memory available on typical computers in a matter of minutes.

If the solution is farther away from the root, breath first search will consume lot of time.

The Lion that Sprang to Life

Another story from the album of Panchatantra goes like this. Once upon a time, there were four friends in a village. Three of these four friends were learned in all sciences, but had no common sense. The fourth friend by the name of Subuddhi was not much learned in scriptures or sciences, but had common sense. He was quite practical in his approach towards life and knew what was good or bad for him.

One day, the three learned friends thought that there was no use of their learning, unless it brought them money to fulfill their needs. They decided to travel to all distant towns and cities in order to try their luck. They didn’t want to take their fourth friend with them, as he was not learned. However, they agreed to take him along with them, taking into account that he was their friend since childhood.

After this, the four friends set out on a long journey. They wandered from one town to another, looking for an opportunity to earn money. One day, during their journey, they had to cross a dense forest. While passing through the forest, they saw a heap of bones lying under a tree. On seeing the heap, one of the learned friends said, “Friends, this is a good opportunity to test our skills. I think these bones are of a certain animal. Let us bring it to life using the knowledge we have acquired.”

The first friend said, “Fine. I will use my skills to assemble the bones into a skeleton”. Then he chanted some mantra and ordered all the bones to come together forming a skeleton. When the skeleton was ready, the second friend chanted some other mantra, commanding flesh and blood to fill the skeleton and skin to cover it. Now, it looked like a lifeless lion.

As the third learned friend stood up to do the final act of putting life into the lifeless body of the animal, the fourth friend shouted, “Stop! This looks like the body of a lion. If it comes to life, he will kill all of us.” The friend, who was to put life into the body of the animal said, “You are a fool. What do you know in the field of learning and knowledge? Do you think I will lose this opportunity to test my learning? It would be better, if you keep your mouth shut.”

Ignoring what the fourth friend had said, the learned friend started chanting the mantra to bring the animal back to life. The fourth friend shouted, “Wait a minute” and quickly climbed up a tree nearby. The three learned friends laughed on the act of their friend. The third friend put life in the lifeless body of the lion. The lion sprang to life and killed all the three learned men. The fourth friend safely went back to his village.

Moral: Knowledge without common sense is useless.

Applications of AI

Q. What are the applications of AI?

A. Here are some.

game playing
You can buy machines that can play master level chess for a few hundred dollars. There is some AI in them, but they play well against people mainly through brute force computation--looking at hundreds of thousands of positions. To beat a world champion by brute force and known reliable heuristics requires being able to look at 200 million positions per second.
speech recognition
In the 1990s, computer speech recognition reached a practical level for limited purposes. Thus United Airlines has replaced its keyboard tree for flight information by a system using speech recognition of flight numbers and city names. It is quite convenient. On the the other hand, while it is possible to instruct some computers using speech, most users have gone back to the keyboard and the mouse as still more convenient.
understanding natural language
Just getting a sequence of words into a computer is not enough. Parsing sentences is not enough either. The computer has to be provided with an understanding of the domain the text is about, and this is presently possible only for very limited domains.
computer vision
The world is composed of three-dimensional objects, but the inputs to the human eye and computers' TV cameras are two dimensional. Some useful programs can work solely in two dimensions, but full computer vision requires partial three-dimensional information that is not just a set of two-dimensional views. At present there are only limited ways of representing three-dimensional information directly, and they are not as good as what humans evidently use.
expert systems
A ``knowledge engineer'' interviews experts in a certain domain and tries to embody their knowledge in a computer program for carrying out some task. How well this works depends on whether the intellectual mechanisms required for the task are within the present state of AI. When this turned out not to be so, there were many disappointing results. One of the first expert systems was MYCIN in 1974, which diagnosed bacterial infections of the blood and suggested treatments. It did better than medical students or practicing doctors, provided its limitations were observed. Namely, its ontology included bacteria, symptoms, and treatments and did not include patients, doctors, hospitals, death, recovery, and events occurring in time. Its interactions depended on a single patient being considered. Since the experts consulted by the knowledge engineers knew about patients, doctors, death, recovery, etc., it is clear that the knowledge engineers forced what the experts told them into a predetermined framework. In the present state of AI, this has to be true. The usefulness of current expert systems depends on their users having common sense.
heuristic classification
One of the most feasible kinds of expert system given the present knowledge of AI is to put some information in one of a fixed set of categories using several sources of information. An example is advising whether to accept a proposed credit card purchase. Information is available about the owner of the credit card, his record of payment and also about the item he is buying and about the establishment from which he is buying it (e.g., about whether there have been previous credit card frauds at this establishment).

Branches of AI

Q. What are the branches of AI?

A. Here's a list, but some branches are surely missing, because no-one has identified them yet. Some of these may be regarded as concepts or topics rather than full branches.

logical AI
What a program knows about the world in general the facts of the specific situation in which it must act, and its goals are all represented by sentences of some mathematical logical language. The program decides what to do by inferring that certain actions are appropriate for achieving its goals. The first article proposing this was [McC59]. [McC89] is a more recent summary. [McC96b] lists some of the concepts involved in logical aI. [Sha97] is an important text.
search
AI programs often examine large numbers of possibilities, e.g. moves in a chess game or inferences by a theorem proving program. Discoveries are continually made about how to do this more efficiently in various domains.
pattern recognition
When a program makes observations of some kind, it is often programmed to compare what it sees with a pattern. For example, a vision program may try to match a pattern of eyes and a nose in a scene in order to find a face. More complex patterns, e.g. in a natural language text, in a chess position, or in the history of some event are also studied. These more complex patterns require quite different methods than do the simple patterns that have been studied the most.
representation
Facts about the world have to be represented in some way. Usually languages of mathematical logic are used.
inference
From some facts, others can be inferred. Mathematical logical deduction is adequate for some purposes, but new methods of non-monotonic inference have been added to logic since the 1970s. The simplest kind of non-monotonic reasoning is default reasoning in which a conclusion is to be inferred by default, but the conclusion can be withdrawn if there is evidence to the contrary. For example, when we hear of a bird, we man infer that it can fly, but this conclusion can be reversed when we hear that it is a penguin. It is the possibility that a conclusion may have to be withdrawn that constitutes the non-monotonic character of the reasoning. Ordinary logical reasoning is monotonic in that the set of conclusions that can the drawn from a set of premises is a monotonic increasing function of the premises. Circumscription is another form of non-monotonic reasoning.
common sense knowledge and reasoning
This is the area in which AI is farthest from human-level, in spite of the fact that it has been an active research area since the 1950s. While there has been considerable progress, e.g. in developing systems of non-monotonic reasoning and theories of action, yet more new ideas are needed. The Cyc system contains a large but spotty collection of common sense facts.
learning from experience
Programs do that. The approaches to AI based on connectionism and neural nets specialize in that. There is also learning of laws expressed in logic. [Mit97] is a comprehensive undergraduate text on machine learning. Programs can only learn what facts or behaviors their formalisms can represent, and unfortunately learning systems are almost all based on very limited abilities to represent information.
planning
Planning programs start with general facts about the world (especially facts about the effects of actions), facts about the particular situation and a statement of a goal. From these, they generate a strategy for achieving the goal. In the most common cases, the strategy is just a sequence of actions.
epistemology
This is a study of the kinds of knowledge that are required for solving problems in the world.
ontology
Ontology is the study of the kinds of things that exist. In AI, the programs and sentences deal with various kinds of objects, and we study what these kinds are and what their basic properties are. Emphasis on ontology begins in the 1990s.
heuristics
A heuristic is a way of trying to discover something or an idea imbedded in a program. The term is used variously in AI. Heuristic functions are used in some approaches to search to measure how far a node in a search tree seems to be from a goal. Heuristic predicates that compare two nodes in a search tree to see if one is better than the other, i.e. constitutes an advance toward the goal, may be more useful. [My opinion].
genetic programming
Genetic programming is a technique for getting programs to solve a task by mating random Lisp programs and selecting fittest in millions of generations. It is being developed by John Koza's group and here's a tutorial.

Basic Questions

Q. What is artificial intelligence?

A. It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable.

Q. Yes, but what is intelligence?

A. Intelligence is the computational part of the ability to achieve goals in the world. Varying kinds and degrees of intelligence occur in people, many animals and some machines.

Q. Isn't there a solid definition of intelligence that doesn't depend on relating it to human intelligence?

A. Not yet. The problem is that we cannot yet characterize in general what kinds of computational procedures we want to call intelligent. We understand some of the mechanisms of intelligence and not others.

Q. Is intelligence a single thing so that one can ask a yes or no question ``Is this machine intelligent or not?''?

A. No. Intelligence involves mechanisms, and AI research has discovered how to make computers carry out some of them and not others. If doing a task requires only mechanisms that are well understood today, computer programs can give very impressive performances on these tasks. Such programs should be considered ``somewhat intelligent''.

Q. Isn't AI about simulating human intelligence?

A. Sometimes but not always or even usually. On the one hand, we can learn something about how to make machines solve problems by observing other people or just by observing our own methods. On the other hand, most work in AI involves studying the problems the world presents to intelligence rather than studying people or animals. AI researchers are free to use methods that are not observed in people or that involve much more computing than people can do.

Q. What about IQ? Do computer programs have IQs?

A. No. IQ is based on the rates at which intelligence develops in children. It is the ratio of the age at which a child normally makes a certain score to the child's age. The scale is extended to adults in a suitable way. IQ correlates well with various measures of success or failure in life, but making computers that can score high on IQ tests would be weakly correlated with their usefulness. For example, the ability of a child to repeat back a long sequence of digits correlates well with other intellectual abilities, perhaps because it measures how much information the child can compute with at once. However, ``digit span'' is trivial for even extremely limited computers.

However, some of the problems on IQ tests are useful challenges for AI.

Q. What about other comparisons between human and computer intelligence?

Arthur R. Jensen [Jen98], a leading researcher in human intelligence, suggests ``as a heuristic hypothesis'' that all normal humans have the same intellectual mechanisms and that differences in intelligence are related to ``quantitative biochemical and physiological conditions''. I see them as speed, short term memory, and the ability to form accurate and retrievable long term memories.

Whether or not Jensen is right about human intelligence, the situation in AI today is the reverse.

Computer programs have plenty of speed and memory but their abilities correspond to the intellectual mechanisms that program designers understand well enough to put in programs. Some abilities that children normally don't develop till they are teenagers may be in, and some abilities possessed by two year olds are still out. The matter is further complicated by the fact that the cognitive sciences still have not succeeded in determining exactly what the human abilities are. Very likely the organization of the intellectual mechanisms for AI can usefully be different from that in people.

Whenever people do better than computers on some task or computers use a lot of computation to do as well as people, this demonstrates that the program designers lack understanding of the intellectual mechanisms required to do the task efficiently.

Q. When did AI research start?

A. After WWII, a number of people independently started to work on intelligent machines. The English mathematician Alan Turing may have been the first. He gave a lecture on it in 1947. He also may have been the first to decide that AI was best researched by programming computers rather than by building machines. By the late 1950s, there were many researchers on AI, and most of them were basing their work on programming computers.

Q. Does AI aim to put the human mind into the computer?

A. Some researchers say they have that objective, but maybe they are using the phrase metaphorically. The human mind has a lot of peculiarities, and I'm not sure anyone is serious about imitating all of them.

Q. What is the Turing test?

A. Alan Turing's 1950 article Computing Machinery and Intelligence [Tur50] discussed conditions for considering a machine to be intelligent. He argued that if the machine could successfully pretend to be human to a knowledgeable observer then you certainly should consider it intelligent. This test would satisfy most people but not all philosophers. The observer could interact with the machine and a human by teletype (to avoid requiring that the machine imitate the appearance or voice of the person), and the human would try to persuade the observer that it was human and the machine would try to fool the observer.

The Turing test is a one-sided test. A machine that passes the test should certainly be considered intelligent, but a machine could still be considered intelligent without knowing enough about humans to imitate a human.

Daniel Dennett's book Brainchildren [Den98] has an excellent discussion of the Turing test and the various partial Turing tests that have been implemented, i.e. with restrictions on the observer's knowledge of AI and the subject matter of questioning. It turns out that some people are easily led into believing that a rather dumb program is intelligent.

Q. Does AI aim at human-level intelligence?

A. Yes. The ultimate effort is to make computer programs that can solve problems and achieve goals in the world as well as humans. However, many people involved in particular research areas are much less ambitious.

Q. How far is AI from reaching human-level intelligence? When will it happen?

A. A few people think that human-level intelligence can be achieved by writing large numbers of programs of the kind people are now writing and assembling vast knowledge bases of facts in the languages now used for expressing knowledge.

However, most AI researchers believe that new fundamental ideas are required, and therefore it cannot be predicted when human-level intelligence will be achieved.

Q. Are computers the right kind of machine to be made intelligent?

A. Computers can be programmed to simulate any kind of machine.

Many researchers invented non-computer machines, hoping that they would be intelligent in different ways than the computer programs could be. However, they usually simulate their invented machines on a computer and come to doubt that the new machine is worth building. Because many billions of dollars that have been spent in making computers faster and faster, another kind of machine would have to be very fast to perform better than a program on a computer simulating the machine.

Q. Are computers fast enough to be intelligent?

A. Some people think much faster computers are required as well as new ideas. My own opinion is that the computers of 30 years ago were fast enough if only we knew how to program them. Of course, quite apart from the ambitions of AI researchers, computers will keep getting faster.

Q. What about parallel machines?

A. Machines with many processors are much faster than single processors can be. Parallelism itself presents no advantages, and parallel machines are somewhat awkward to program. When extreme speed is required, it is necessary to face this awkwardness.

Q. What about making a ``child machine'' that could improve by reading and by learning from experience?

A. This idea has been proposed many times, starting in the 1940s. Eventually, it will be made to work. However, AI programs haven't yet reached the level of being able to learn much of what a child learns from physical experience. Nor do present programs understand language well enough to learn much by reading.

Q. Might an AI system be able to bootstrap itself to higher and higher level intelligence by thinking about AI?

A. I think yes, but we aren't yet at a level of AI at which this process can begin.

Q. What about chess?

A. Alexander Kronrod, a Russian AI researcher, said ``Chess is the Drosophila of AI.'' He was making an analogy with geneticists' use of that fruit fly to study inheritance. Playing chess requires certain intellectual mechanisms and not others. Chess programs now play at grandmaster level, but they do it with limited intellectual mechanisms compared to those used by a human chess player, substituting large amounts of computation for understanding. Once we understand these mechanisms better, we can build human-level chess programs that do far less computation than do present programs.

Unfortunately, the competitive and commercial aspects of making computers play chess have taken precedence over using chess as a scientific domain. It is as if the geneticists after 1910 had organized fruit fly races and concentrated their efforts on breeding fruit flies that could win these races.

Q. What about Go?

A. The Chinese and Japanese game of Go is also a board game in which the players take turns moving. Go exposes the weakness of our present understanding of the intellectual mechanisms involved in human game playing. Go programs are very bad players, in spite of considerable effort (not as much as for chess). The problem seems to be that a position in Go has to be divided mentally into a collection of subpositions which are first analyzed separately followed by an analysis of their interaction. Humans use this in chess also, but chess programs consider the position as a whole. Chess programs compensate for the lack of this intellectual mechanism by doing thousands or, in the case of Deep Blue, many millions of times as much computation.

Sooner or later, AI research will overcome this scandalous weakness.

Q. Don't some people say that AI is a bad idea?

A. The philosopher John Searle says that the idea of a non-biological machine being intelligent is incoherent. He proposes the Chinese room argument www-formal.stanford.edu/jmc/chinese.html The philosopher Hubert Dreyfus says that AI is impossible. The computer scientist Joseph Weizenbaum says the idea is obscene, anti-human and immoral. Various people have said that since artificial intelligence hasn't reached human level by now, it must be impossible. Still other people are disappointed that companies they invested in went bankrupt.

Q. Aren't computability theory and computational complexity the keys to AI? [Note to the layman and beginners in computer science: These are quite technical branches of mathematical logic and computer science, and the answer to the question has to be somewhat technical.]

A. No. These theories are relevant but don't address the fundamental problems of AI.

In the 1930s mathematical logicians, especially Kurt Gödel and Alan Turing, established that there did not exist algorithms that were guaranteed to solve all problems in certain important mathematical domains. Whether a sentence of first order logic is a theorem is one example, and whether a polynomial equations in several variables has integer solutions is another. Humans solve problems in these domains all the time, and this has been offered as an argument (usually with some decorations) that computers are intrinsically incapable of doing what people do. Roger Penrose claims this. However, people can't guarantee to solve arbitrary problems in these domains either. See my Review of The Emperor's New Mind by Roger Penrose. More essays and reviews defending AI research are in [McC96a].

In the 1960s computer scientists, especially Steve Cook and Richard Karp developed the theory of NP-complete problem domains. Problems in these domains are solvable, but seem to take time exponential in the size of the problem. Which sentences of propositional calculus are satisfiable is a basic example of an NP-complete problem domain. Humans often solve problems in NP-complete domains in times much shorter than is guaranteed by the general algorithms, but can't solve them quickly in general.

What is important for AI is to have algorithms as capable as people at solving problems. The identification of subdomains for which good algorithms exist is important, but a lot of AI problem solvers are not associated with readily identified subdomains.

The theory of the difficulty of general classes of problems is called computational complexity. So far this theory hasn't interacted with AI as much as might have been hoped. Success in problem solving by humans and by AI programs seems to rely on properties of problems and problem solving methods that the neither the complexity researchers nor the AI community have been able to identify precisely.

Algorithmic complexity theory as developed by Solomonoff, Kolmogorov and Chaitin (independently of one another) is also relevant. It defines the complexity of a symbolic object as the length of the shortest program that will generate it. Proving that a candidate program is the shortest or close to the shortest is an unsolvable problem, but representing objects by short programs that generate them should sometimes be illuminating even when you can't prove that the program is the shortest.