You have all experienced how when you are typing a text message the application will provide potential words that complete what you are typing (and sometimes insist on completing them incorrectly). You will write a Python program that is capable of generating a likely set of completion words given the start of a word as input to the program.

In order to be able to make these suggestions, your program will first need to analyze a large amount of text (like a book) to get an idea of what words occur how often in regular text. Once this analysis is made, then it will be possible to do a quick lookup into a data structure described below to generate the potential words.

Step 1 - Text file analysis

Ask the user for the name of a file that contains the text to analyze. Open the file and read the lines of text. Break each line into words, stripping out all of the special symbols. For each word that you find that is longer than one character, do the following. First, add the word to a dictionary of words you have seen so far. The values in this dictionary should be a count of how many times each word has occurred in the text file. Second, add the word into a data structure that is keeping track of word information for the completion process. This data structure has 3 basic parts. The top level part is a list that will have as many elements in it as the number of characters in the longest word seen so far. Each element in this list will be a dictionary which is indexed by the 26 letters of the alphabet. The value for each entry in the dictionary will be a set of words. A word is added into this structure as follows. The word is first added to the set contained in the dictionary corresponding to slot 0 in the list, indexed by the key of the first letter in the word. Then, the second letter of the word is used to index into the dictionary corresponding to slot 1 in the list to add the word to that set. This continues for the remaining letters in the word. So this means that the word "help" would be added to the set of words that have an h as their first letter, the set having e as the second letter, the set for l as the third letter, and then p as the fourth letter.

Step 2 - Word completion

With these two structures of information constructed based on the input file, it is time to do word completion. Within a loop that can continue as long as the user wants, ask to read the starting portion of a word. You then must determine the set of all possible words you have seen that begin with this string of characters. This set of words can be computed by intersecting a group of sets extracted from the data structure. These sets are found by indexing into the dictionary corresponding to the character value of each position in the string. You can intersect all of these sets together two at a time to get your result. So if the string "he" was typed in, you would intersect the set of words that have h as their first letter with the set of words that have e as their second letter. This gives the set of words that start with "he".

Next you must rank the possible set of words based on how often they were found in the text, assuming that words that occur often are more likely to occur again. For each word in the final set of possibilities, extract the occurrence count from the other dictionary you constructed. Then sort the words based on these values. Print out the top five candidate words (or fewer if less than five exist) with a percentage of how likely each word is the proper completion of the string given. To compute percentages, first total up all of the occurrences of the words in the set, then divide the count for each by this amount.

Submission

Submit your commented source code. Acquire a few large text files to test your program. Plain text files of books are a good suggestion, like the War & Peace file we used in class. Things like Project Gutenberg are a good source for these. Submit some sample output from your program using one of these files.