Project 5: Word Autocomplete use BFS with a FIFO queue to find all the words in the order that they are enqueued

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Project 5: Word Autocomplete Search start code is provided

 

Project 5: Word Autocomplete Search

Due: Monday 12/08/2021 at 11:59PM

General Guidelines:

The APIs given below describe the required methods in each class that will be tested. You may need additional methods or classes that will not be directly tested but may be necessary to complete the assignment. Keep in mind that anything that does not need to be public should generally be kept private (instance variables, helper methods, etc.).

 

Unless otherwise stated in this handout, you are welcome (and encouraged) to add to/alter the provided java files as well as create new java files as needed.

 

Note on Academic Dishonesty:

Please note that it is considered academic dishonesty to read anyone else’s solution code to this problem, whether it is another student’s code, code from a textbook, or something you found online. You MUST do your own work! You are allowed to use resources to help you, but those resources should not be code, so be careful what you look up online! We are going to be strict if we find any implementation similar to any implementations on the internet. 

 

Note on implementation details:

 

Note that even if your solution passes all test cases, if a visual inspection of your code shows that you did not follow the guidelines in the project, you will receive a 0.

 

Note on grading and provided tests:

The provided tests are to help you as you implement the project. The Vocareum tests will be similar but not exactly the same. Keep in mind that the points you see when you run the local tests are only an indicator of how you are doing. The final grade will be determined by your results on Vocareum.

 

Introduction:

Autocomplete is a feature wherein an application predicts the rest of a word based on what the user is typing. It is commonly used in search engines, source code editors, and database query tools. In this project, you will implement a word autocomplete search engine by using compressed trie and BFS. Your goal is to correctly build the trie and also answer the query in an output file. 

 

Before writing the project, you should first try to read TrieTest.java to see how your solutions are going to test be testing. Basically, we will check the correctness of your output files by comparing yours with the expected output. Note that we will use buildTrie and autoComplete methods in Trie class to run test cases, do not change the signature of these functions. You may add additional classes/methods/variables to help you accomplish the required functionality. Two examples (sample input & expected output) have been provided inside the ‘files’ folder within the main project directory. 

 

Input Format:

 

The input file will be a word list. The first line of the input file is the query which is the string that a user already typed in the prompt in your search engine. From the second line to the end of file, you will be given all the words that should be used to build the trie structure. Note that the first word is a query, which should not be inserted into the compressed trie. 

 

For example, in input1.txt, 

the first word seg is your query, 

From the second line sea

 

 

segmentationfault

segment

segmental

segmentation

segv

 

are what should be built in the compressed trie. 

 

You may assume that there is only one word each line. You may assume that the words will be unique and only contain lowercase alphabetic characters. 

 

Implementation:

 

A compressed trie should be built with the word lists given in the input file. The words should be inserted into the trie. There are several cases to consider when inserting a word. You can refer to the insert() operation on this site:  http://theoryofprogramming.com/2016/11/15/compressed-trie-tree/. Each node has at most 26 children. The precedence of a node’s children should be sorted in lexicographical order. 

 

A search method should also be implemented in order to answer the query, i.e. provide the auto-complete recommendations to the query string. If the string we want to search does not exist, nothing should be printed in the output file. For example, searching for “owl” when the trie only has the word “crow”. Otherwise, the string we want to search for either exists as a prefix or is fully matched. For example, searching for “face” when the words “face”, “facebook”, and “facetime” are present in the trie must include all three of them in the query results. 

input0.txt

face

face

facebook

facetime

 

It is required to use BFS with a FIFO queue to find all the words in the order that they are enqueued. Furthermore, you will need to include the depth of the word after each word you found in your output files. 

 

In the example input0.txt, your output file should look like this:

    face 1

    facebook 2

    facetime 2

 

Detailed explanation: Build trie: The first word in input is “face”, so “face” is inserted as a child of the root. Then the second word is “facebook”, you should insert it by adding a new node-- “book” under “face”. Now face has 1 child. Then you insert “facetime” by adding a new node “time”. Since the children's list should be in lexicographical order, you arrange the children's list of “face” as [“book”, “face”]. Then the trie is done.

 

Now search for the query “face”. You look for children of the root. It has only one child, “face”. And it matches the query, luckily. So you enqueue “face” on a queue. The first word you found is “face” because you are using BFS. Then, you dequeue “face”. And enqueue all the children of “face” so “book” and “time” are enqueued. These are two more words you found. Then you dequeue “book”. It has no child. Then you dequeue “time”. It has no child. The queue is now empty, so you finish searching. 

Root is of depth 0, so “face” is of depth 1. Similarly, “facebook” and “facetime” both have depth 2. 

 

Take a look at the given test cases for more examples. 

 

Submission:

 

What you must submit: The following classes are provided. You should not change the method signatures for the required methods, but you may add to these classes as necessary.

 

Trie.java

TrieNode.java

You have 10 submissions. 

 

Grading & Testing:

 

Due to the high demand for more flexible grading, there is partial grading. 

 

Test 1

 

50 points

 

Test 2

 

50 points

 

Total

 

100 points

 

You are provided with test cases, and you may create your own tests as necessary. The tests provided are similar to the tests used for grading.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of