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 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 trying to add though is the following additional functionality: if the user inputs a 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.

My logic would be to somehow remove the last letter of the unavailable prefix search (in this case 'q') and verify if abse is a node within my trie (which it is and thus the program can output the 3 most similar entries in my Trie).

#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(); } } } } }; int main(){ Trie* t = new Trie(); fstream dictionaryfile; dictionaryfile.open("Dictionary.txt",ios::in); 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) /* Call a recommendation search function which recommends the top 3 most similar entries within the Trie*/ cout<<"No suggestions available. "; else{ string recommended_string; // modify this a bit to pass the root of the trie and the recommended_string t->auto_recommendation(t->root, searchQuery, recommended_string); } return 0; }