I coded the following Trie data structure in C++ in order to allow me to import any dictionary text file filled with a single word per line (a sample dictionary file that I'm working with can be found at http://txt.do/1pht5). The program allows me to obtain a autocomplete search recommendation based on any valid prefix search (i.e. user inputs prefix abse and receives the following autocomplete recommendations based on http://txt.do/1pht5 dictionary: absence, absences, absense, absent, and absentee)

What I'm needing help is with a provide_suggestion() functionality where if the user inputs an invalid prefix search that is not within the Trie, it will recommend the top 3 most similar entries in the Trie. I.E. User prefix search is abseq which is not part of the dictionary txt file but absence, absences, absense are, which should be suggested.

#include #define alphabet_size 128 using namespace std; class TrieNode { public: TrieNode* children[alphabet_size]; bool endofLeaf; TrieNode(){ for(int i = 0; i < alphabet_size; i++) children[i] = NULL; endofLeaf = false; } }; class Trie { public: TrieNode* root; Trie() {root = new TrieNode();} void Dict_insert(string word){ TrieNode* temp = root; for(int i = 0; i < word.length(); i++){ if(temp->children[word[i]] == NULL){ temp->children[word[i]] = new TrieNode(); } temp = temp->children[word[i]]; } temp->endofLeaf = true; } bool search (string word){ TrieNode* tmp = root; for(int i = 0; i < word.size(); i++) { if(tmp->children[word[i]] == NULL){ return false; } tmp = tmp->children[word[i]]; } return tmp; } void auto_recommendation(TrieNode* autorec ,string word, string recommended_string){ if(autorec->endofLeaf == true) cout << recommended_string << endl; if(recommended_string.length() < word.length() ){ recommended_string.push_back(word[recommended_string.length()]); if(autorec->children[word[recommended_string.length()-1]] != NULL){ auto_recommendation(autorec->children[word[recommended_string.length()-1]], word, recommended_string); } } else { for(int i = 0; i < alphabet_size; i++){ if(autorec->children[i] != NULL){ recommended_string.push_back((char)i); auto_recommendation(autorec->children[i], word, recommended_string); recommended_string.pop_back(); } } } } void provide_suggestion(string word){ //CODE HERE } }; int main(){ Trie* t = new Trie(); fstream dictionaryfile; dictionaryfile.open("Dictionary.txt",ios::in); //assume I have some dictionary.txt file if (dictionaryfile.is_open()){ string DictEntry; while(getline(dictionaryfile, DictEntry)){ t->Dict_insert(DictEntry); } dictionaryfile.close(); } string searchQuery; cout << "Type in a search: " << endl; getline(cin,searchQuery); cout << "Did you mean:" << endl; t->search(searchQuery); if (t->search(searchQuery) == false) //NEED HELP AROUND THIS PART with utilizing void provide_suggestion() function cout<" is not a valid search. Here are the 3 most similar entries to your search:"; /*Call provide_suggestion function or modify my 'auto_recommendation' function in order for the program to recommend the top 3 most similar entries within the Trie*/ else{ string recommended_string; t->auto_recommendation(t->root, searchQuery, recommended_string); } return 0; }