please the the answer in java foam in java foam please

and by using trie

TRIE Overview There are different ways to represent a set of words. For example, a hash table. But there's another structure that was created to represent a set of words: a trie. The term "trie" comes from the word retrieval, and is usually pronounced try, to distinguish it from other tree structures. However, a trie is basically a tree data structure, but it just has a few rules to follow in terms of how it is created and used. a trie is a tree-like data structure where in the nodes of the tree store the entire alphabet, and strings / words be retrieved by traversing down a branch path of the tree. Structure of a Node in TRIE A trie is a tree-like data structure whose nodes store the letters of an alphabet. By structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree. Each trie has an empty root node, with links (or references) to other nodes - one for each possible alphabetic value. The number of child nodes in a trie depends completely upon the total number of values possible. For example, if we are representing the English alphabet, then the total number of child nodes is directly connected to the total number of letters possible. In the English alphabet, there are 26 letters, so the total number of child nodes will be 26. However, if we were creating a trie to hold words from the Khmer (Cambodian) alphabet, which is the longest known alphabet with 74 characters. In that case, the root node would contain 74 links to 74 other child nodes. empty root node * The shape and structure of a trie is always a set of linked nodes, all connecting back to an empty root node. Each node contains an array (child holes"), one for each possible alphabetic value *Note: the sinje of a thrie is directly connected /correlated to the sine f the alphabet, that is being represented. A single node in a trie contains just two things: 1. A value, which might be null 2. An array of references to child nodes, all of which also might be null Each node in a trie, including the root node itself, has only these two aspects to it. When a trie representing the English language is created, it consists of a single root node, whose value is usually set to an empty string: "". That root node will also have an array that contains 26 references, all of which will point to null at first. As the trie grows, those pointers start to get filled up with references to other nodes. We can use the array's indexes to find specific references to nodes. For example, our root node will hold an array of indexes through 25, since there are 26 possible slots for the 26 letters of the alphabet. Since the alphabet is in order, we know that the reference to the node that will contain the letter A will live at index 0. What's in a single node of a trie ? ww O OO *Both the value and the references to other nodes could empty! O be - Value Generally, the O Milliy References to other nodes value of the root node is 7 an empty ** string: Cross-section of a trie's node: Sienki AN link is defined A Each node contains array of references/links. The character / letter contained at by the link's index at the array (The character "A" would live index of o). at the armay Example In the trie shown below, we're representing the nursery rhyme that starts off with something like "Peter Piper picked a peck of pickled peppers". There are six different words that we're representing in this trie: Peter, piper, picked, peck, pickled, and peppers. if we search for the key "pie", we traverse down each nodes array, and look to see if there is a value for the branch path:p-i-e. If it does have a value, we can simply return it. This is sometimes referred to as a search hit, since we were able to find a value for the key. But what if we search for something that doesn't exist in our trie? What if we search for the word "pi", which we haven't added as a key with a value? Well, we'll go from the root node to the node at index p, and then we'll go from the node at p to the node at index i. When we get to this point, we'll see if the node at the branch path p-i has a value. In this case, it doesn't have a value; it's pointing at null. So, we can be sure that the key "pi" doesn't exist in our trie as a string with a value. This is often referred to as a search miss, since we could not find a value for the key. Deleting a Node from TRIE How can we remove a key and its value from our trie structure? Suppose we have added another word "pies" to our trie. We now have both the keys "pie" and "pies", each with their own values. Let's say we want to remove the key "pies" from our trie. In order to do this, we'd need to take two steps: 1. First, we need to find the node that contains the value for that key, and set its value to null. This means traversing down and finding the last letter of the word "pies, and then resetting the value of the last node from 12 to null. 2. Second, we need to check the node's references and see if all of its pointers to other nodes are also null. If all of them are empty, that means that there are no other words/branches below this one, and they can all be removed. However, if there are pointers for other nodes that do have values, we don't want to delete the node that we've just set to null. This last check is particularly important in order to not remove longer strings when we remove substrings of a word. Assignment Description Through this assignment we want to implement a dictionary of words. We intend to help our user to find the meaning and synonyms of an entered word using the trie data structure. Data Items A trie node must consist of the following data items: 1. Meaning of the word 2. List of synonyms of the word. 3. Array of pointers of type trie node of length 26. 4. Flag that indicates the completion of the word. You can add other data items as per your logic. Operations The "TRIE class must have the following methods. 1. void CreateDictionary("./triel dictionary.txt") Requirements: None Result: Root node 20 Peter Piper picked :peck pickled O peppers 1 E what if we wanted to add the word to this list? ( pecked E Weld check that this word didn't already through they aren't all shown here! exist We'd follow * Remember that every node the links from has 20 children, even one node to another until we reached a NULL node. Then, wed insert a value in the mode, Looking at our trie, we can see that we have an empty root node, as is typical for a trie structure. We also have six different words that we're representing in this trie: Peter, piper, picked, peck, pickled, and peppers. We have only drawn the references that actually have nodes in them; it's important to remember that, even though they're not illustrated here, every single node has 26 references to possible child nodes. Notice how there are six different "branches" to this trie, one for each word that's being represented. We can also see that some words are sharing parent nodes. For example, all of the branches for the words Peter, peck, and peppers share the nodes for p and for e. Similarly, the path to the word picked and pickled share the nodes p, i, c, and k. Inserting a New Node What if we wanted to add the word pecked to this list of words represented by this trie? We'd need to do two things in order to make this happen: 1. First, we'd need to check that the word pecked doesn't already exist in this trie. 2. Next, if we've traversed down the branch where this word ought to live and the words doesn't exist yet, we'd insert a value into the node's reference where the word should go. In this case, we'd insert e and d at the correct references. But how do we actually go about checking if the word exists? And how do we insert the letters into their correct places? This is easier to understand with a small trie as an example, so let's look at a trie that is empty, and try inserting something into it. new node for P. We know that we'll have an empty root node, which will have a value of "", and an array with 26 references in it, all of which will be empty (pointing to null) to start. Let's say that we want to insert the word "pie", and give it a value of 5. Key / value Key ALTIPLA We find a null link at P pointer, So we create a ATITTI2 We encounter another null link for pointer I, so we create another new node. AE We reach the last character, E, of our 5 Key "PIE", This is 2 where we set our value. We'll first look for the pointer for p, since the first letter in our key "pie" is p. Since this trie doesn't have anything in just yet, the reference at p in our root node will be null. So, we'll create a new node for p, and the root node now has an array with 25 empty slots, and 1 slot (at index 15) that contains a reference to a node. Now we have a node at index 15, holding the value for p. But, our string is "pie", so we're not done yet. We'll do the same thing for this node: check if there is a null pointer at the next letter of the key: i. Since we encounter another null link for the reference at i, we'll create another new node. Finally, we're at the last character of our key: the e in "pie". We create a new node for the array reference to e, and inside of this third node that we've created, we'll set our value: 5. Searching a Word from TRIE Searching through a *If we search for the word/Keyspie" and are able to find it, we can look to see if it has a value, and return it: 6. ' Search miss! 1 Savch hit! #lf we search for the Key "pi" and find the node at the last letter we can look to see its value. If it has a NULL means that "pi" is not currently a key value, A trie is created from dictionary.txt. The file is in the following format: -piper --someone who plays the bagpipe bagpiper musician player instrumentalist unu Pecked --of a bird) strike or bite something with its beak. strike beat niet pick The line starting with single dash (-) consists of the word. The line starting with double dash (--) consists of the meaning of the word. Afterwards the lines without any dashes consist of the synonyms until the next word or end of file. 2. vector OutputAscending) Requirements: Trie is not empty. Result: Output all the words in ascending order. 3. bool Find Word(key) Requirements: Trie is not empty. Result: Search for the word with the given key. 4. vector FindSynonyms(key) Requirements: Trie is not empty. Result: Search for all the synonyms for a given key. 5. string Find Meaning(key) Requirements: Trie is not empty Result: Search for the meaning of a given word. 6. vector OutputPrefix(prefix) Requirements: Trie is not empty. Result: Search for all the words with the given prefix. 7. vector OutputSE(length) Requirements: Trie is not empty Requirements: Trie is not empty. Result: Search for all the synonyms for a given key. 5. string Find Meaning(key) Requirements: Trie is not empty. Result: Search for the meaning of a given word. 6. vector OutputPrefix(prefix) Requirements: Trie is not empty. Result: Search for all the words with the given prefix. 7. vector OutputSE(length) Requirements: Trie is not empty. Result: Search for all the words equal and smaller than the given length