Question

Please provide assistance to fix the segmentation fault error I am receiving and solve the following problem I am working on:

My goal is to build a Trie data structure in C++ that can do the following:

- Capable to insert any given dictionary .txt file filled with a single word per line (i.e. file includes ant, bat, car, desk, etc.) into the Trie. A sample dictionary file that I'm working with can be found at http://txt.do/1pht5

- Prompts the user to input some prefix search and provides an autocomplete suggestion (i.e. file includes bat, bar, bass, and user inputs ba which should suggest bat, bar, bass, etc.)

- Lastly, 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 input is baq which is not part of the dictionary txt file but bat, bar, bass are which should be suggested)

I have been able to write the following code so far but I'm having difficulties in fixing the segmentation error and making it run.

#include<bits/stdc++.h>
#define alphabet_size 26
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]-'a'] == NULL){
                    temp->children[word[i]-'a'] = new TrieNode(); 
                }
                temp = temp->children[word[i]-'a'];        
            }
            temp->endofLeaf = true;
        }

        bool search (string word){
            TrieNode* tmp = root;
            for(int i = 0; i < word.size(); i++)
            {
                if(tmp->children[word[i]-'a'] == NULL){
                    return false;
                }
                tmp = tmp->children[word[i]-'a'];
            }
            return tmp;
        }

        void auto_recommendation(string word){
            TrieNode* autorec = root;
            if(autorec->endofLeaf == true)
                cout << word << endl;
            for(int i = 0; i < alphabet_size; i++){
                if(autorec->children[i] != NULL){ 
                    word.push_back((char)i); 
                    auto_recommendation(word); 
                    word.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 << "/nDid you mean: \n" << 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<<"Did you mean:\n";
        //cout top 3 most similar entries within the Trie
    else
        t->auto_recommendation(searchQuery);
    return 0;
}

Answer 1

Hi,

You are getting seg fault because you are not using alid null-terminated C-style string.

dictionaryfile.open("Dictionary.txt\n",ios::in); // use \n you will not get seg fault

I am attaching code for reference and my compiled code and runnig code.

#include<bits/stdc++.h>
#define alphabet_size 26
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]-'a'] == NULL){
                                        temp->children[word[i]-'a'] = new TrieNode();
                                }
                                temp = temp->children[word[i]-'a'];
                        }
                        temp->endofLeaf = true;
                }

                bool search (string word){
                        TrieNode* tmp = root;
                        for(int i = 0; i < word.size(); i++)
                        {
                                if(tmp->children[word[i]-'a'] == NULL){
                                        return false;
                                }
                                tmp = tmp->children[word[i]-'a'];
                        }
                        return tmp;
                }

                void auto_recommendation(string word){
                        TrieNode* autorec = root;
                        if(autorec->endofLeaf == true)
                                cout << word << endl;
                        for(int i = 0; i < alphabet_size; i++){
                                if(autorec->children[i] != NULL){
                                        word.push_back((char)i);
                                        auto_recommendation(word);
                                        word.pop_back();
                                }
                        }
                }
};

int main(){
        Trie* t = new Trie();
        ifstream dictionaryfile;
        dictionaryfile.open("Dictionary.txt\n",ios::iun);
        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 << "/nDid you mean: \n" << 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<<"Did you mean:\n";
        //cout top 3 most similar entries within the Trie
        //    else
        //            t->auto_recommendation(searchQuery);
        //                return 0;
                        }