Overview

Auto completion has a large number of applications in the present day. It is one of the perfect examples of the applications of data structures in solving various problems. It requires the usage of trees in order to predict the next number that could be given by the user. It holds great significance as ,today it is present in almost all the web browsers, e-mail programmes, search engines, in source code editors, file query tools and in word processors. An Auto Completion programme contains a root node with multiple branches having various nodes. Each leaf node is linked to a file or file having a collection of words that are arranged according to the alphabet which given as input in the node. The programme can be implemented by using different programming languages such as ‘c++’, ‘c#’, ‘J query’,

Windows based autocompletion provides real time suggestions whereas console-based applications can show suggestions of the word that the user can enter. Both the programmes carry the same code which is used to bring up the suggestions. This programme can also be made by first making the tree with the help of given words in the file. Once a tree is created finally all the words that are present in the file can be easily predicted by the programme

Design

First we create a tree by using the words available in the file for searching purpose. For this the words are imported from the file and each letter of the word are converted into their ASCII value which later are used to build the tree. Consider some words of the English language like: ace, ant, an, app etc.Now let’s suppose the word ace is taken into consideration. The word ‘ace’ is first (broken down into three parts) divided into individual letters.We know that the ASCII value of alphabets ranges from 65 to 90, where 65 represents ‘A’ .So we subtract the ASCII value of ‘A’ from a digit such that it returns ‘1’.Similarly ‘3’ will be returned for ‘C’ and so on. Hence, the value formed will be 1, 3 & 5 which are stored first in array.Now, a binary tree is created from the number obtained (i.e. 1, 3 & 5). Where the root node initially contains null value at the start of the programme. And ‘1’, ‘3’ &’5’ makes the three child nodes in the tree.

Now the second word present in the file is taken into account i.e. ‘And’. Here the numbers obtained would be ‘1’, ‘14’& ‘4’. There for the programme will first check the root node if it is not null, then the value of the first letter is compared with the child node, if the first node is found like in this case 1 then, the letters ‘n’ would become child node of ‘A’ or ‘1’ and ‘4’ or‘d’ would become the child node of ‘14’.

Also if while analysing a new word root node is not null and the first letters value suppose 2 is not present in the child node of root node or another child node then it is created.Similarly, in this way by analysing all the words available in the file we make a tree.When a user types few letter the word is traced in the binary tree, suppose the first three child nodes are matched then, the programme would print all the words that could be formed using those three words i.e. it can print all the words that have those three child nodes in the tree.Here instead of storing the final value in the leaf node the path of the tree from the root node to leaf node itself represents a word.

Solution

Step 1: Construct a tree structure. This trees root node will have multiple child node .And a Boolean variable 'isWordEnd' is set as True.

Step 2: A function called get root is constructed which makes a new node when called and also sets the 'isWordEnd' bool value as false. Thus stating that the node is not the leaf node.

Step 3: All the children of this new node in the tree are initialised to null. The get root function would return the address of the new node created of data type tree.

Step 4: An insert function is created which takes in two values one as root address of datatype tree and a constant string character.

Step 5: Inside the insert function a crawler is build. The function of the crawler is that it moves along the node looking for null value. It is used to print output als0.

Step 6: Crawler moves along the node creating new nodes in the tree until the "isWordEnd" variable becomes true. Once the 'isWordEnd' variable becomes true it marks the node as the leaf node

Step 7: The tree nodes created are assigned numbers such that a node having number 1 represents alphabet 'A' of any word.

Step 8: A search function is created which returns a Boolean variable. It takes two variables one containing variable address And other as constant string.

Step 9: Nodes in the tree are made using this bool function.

Step 10: In bool function, take length of string and construct a tree with child nodes Of that length with the help of the crawler.

Step 11: At the end of the word the crawler should return crawl not equals to null.

Step 12: A suggest function is made to give the output of the suitable words.

Step 13: The function takes a root value of data type tree and a constant string.

Step 14: The crawler is initialised with the address of root node. Up to the word length for which the loop is runned.

Step 15: As the crawler moves though the nodes created. It analysis the tree up to the nodes that are matched with the users input words. And then prints the complete Path i.e. form root node to the leaf node thus creating the possible word.

Step16: A function named addtofile is created .Opened with the help of this function and read the words in it.

Step 17: A while loop is made inside the function addtofile. It runs each time for a word and converts its letters to lowercase and then ASCII value.

Step 18: The ASCII value obtained is subtracted with 96. So that all the alphabets can be represented using number 1 to 26.

Step 19: Make a menu driven programme, such that user can add, search or delete words from the file.

Step 20: Switch function is used to create the menu driven programme.