7
\$\begingroup\$

I need to develop a dictionary program so I used a trie data structure to implement it. I have created a array of object with size of 26 - so each object of class Dict will have 26 sub objects like a child.

This program takes no input from user for now. I gave my input in main function. but it will print all the words in the trie.

This program works fine. Is this program somewhat efficient? do I have to replace the fixed sized array of object of class Dict with any other technique?

public class Dict {
        boolean isWord;
        Dict obj[];
        Dict()
        {
            obj=new Dict[26]; // as there are 26 letters in english
            isWord=false;
        }
        Dict insertWord(Dict Node,String str, int it) // used to insert a word into trie
        {
            if(it<str.length())
            {
            int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.
            if(Node.obj[Linkno]==null)
            {
                Node.obj[Linkno]=new Dict();
            }
            insertWord(Node.obj[Linkno],str,it+1);
            }
            else
            {
                Node.isWord=true;
            }
            return Node;
        }
        void displayAll(Dict Node,String str) // used to display all the words in the trie
        {
            for(int i=0;i<26;i++)
            {
                if(Node.obj[i]!=null)
                {
                    if(Node.obj[i].isWord==true)
                        System.out.println(str+((char)(i+97)));
                    displayAll(Node.obj[i],(str+((char)(i+97))));
                }
            }
        }
        public static void main(String ar[])
        {
            Dict root=new Dict();
            root.insertWord(root,"trasaction",0);
            root.insertWord(root,"transformation",0);
            root.insertWord(root,"transmission",0);
            root.insertWord(root,"trance",0);
            root.insertWord(root,"trap",0);
            root.displayAll(root,"");
        }
    }
\$\endgroup\$
2
\$\begingroup\$

Do I have to replace the fixed sized array of object of class Dict with any other technique?

I suggest making the size a constant, like this:

public static int ALPHABET_SIZE = 26:

And then you may use:

obj = new Dict[ALPHABET_SIZE];

As you can see, the comment now becomes redundant and we can remove it, and it is always a good thing, as comments may become obsolete or wrong.

The same applies to:

int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.

Make a constant:

LOWER_A_ASCII_VAL = 97;

Get rid of repetition

Looking at:

    root.insertWord(root,"trasaction",0);
    root.insertWord(root,"transformation",0);
    root.insertWord(root,"transmission",0);
    root.insertWord(root,"trance",0);
    root.insertWord(root,"trap",0);

What if you want to add 10 more words? The code will become very long and repetitive, instead use a foreach loop:

for (String word : {"transaction", "transformation", ...} ) {
    root.insertWord(root, word, 0);
}

Miscellanous

  • Wrong indent hurts readibility, fix it in:

        if(it<str.length())
        {
        int Linkno=((int)(str.charAt(it)))-97; //97 is the ascii value of 'a'.
        if(Node.obj[Linkno]==null)
        {
            Node.obj[Linkno]=new Dict();
        }
        insertWord(Node.obj[Linkno],str,it+1);
        }
    
  • Always use braces to prevent bugs in :

            if(Node.obj[i].isWord==true) {
                System.out.println(str+((char)(i+97)));
            }
    
  • Avoid general names like obj and think about a more precise name.

\$\endgroup\$
2
\$\begingroup\$

Some thoughts:

  1. Your use of the default access level is probably incorrect. Public, private, and sometimes protected make much more sense. In particular, if this class is not to be used outside of its package, you can make the whole class default scope and let the methods be public. If it is to be used outside its package, everything should be public.
  2. In java, all variables should start with a lowercase letter except constants. You should also try to pick more descriptive names. There's no real cost to spelling out what a variable holds.
  3. Your use of comments is not ideal. Most of what you have should either belong to the the javadoc for the relevant method or it should be obvious based on a better variable name.
  4. You're not using standard java brace locations. They belong on the same line.
  5. .isWord==true should just be .isWord. You don't need to compare boolean variables to true or false.
  6. Helper methods would clean up your API by not forcing clients to pass in the node, 0 and "" with every call.
  7. It would be a better separation of concerns if your Dict class only found the words and didn't output them. Let the caller handle that part. It greatly increases the reusability of the class.
  8. This may be a bug - insertWord() is always returning the same node that was passed in. Why bother?
  9. The add prefix is more commonly used in the standard API than insert. I would rename insertWord() to addWord().

Putting it all together, if I were writing this class, it would look more like this.

import java.util.ArrayList;
import java.util.List;

public final class Dict {
    private static final int ALPHABET_SIZE = 26;
    private static final int LOWERCASE_A_ASCII_VALUE = 97;

    private boolean isWord;
    private final Dict children[] = new Dict[ALPHABET_SIZE];

    public Dict() {
        super();
    }

    public void addWord(final String word) {
        this.addWord(this, word.toCharArray(), 0);
    }

    private void addWord(final Dict node, final char[] letters, final int currentLetterIndex) {
        if (currentLetterIndex == letters.length) {
            node.isWord = true;
            return;
        }

        final int linkno = indexForCharacter(letters[currentLetterIndex]);
        if (node.children[linkno] == null) {
            node.children[linkno] = new Dict();
        }
        this.addWord(node.children[linkno], letters, currentLetterIndex + 1);
    }

    public List<String> findWords() {
        final List<String> words = new ArrayList<String>();
        this.findWords(this, words, "");
        return words;
    }

    private void findWords(final Dict node, final List<String> words, final String wordCandidate) {
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (node.children[i] == null) {
                continue;
            }
            if (node.children[i].isWord) {
                words.add(wordCandidate + characterForIndex(i));
            }
            this.findWords(node.children[i], words, wordCandidate + characterForIndex(i));
        }
    }

    private static int indexForCharacter(final char character) {
        return character - LOWERCASE_A_ASCII_VALUE;
    }

    private static char characterForIndex(final int index) {
        return (char) (index + LOWERCASE_A_ASCII_VALUE);
    }
}

You could also use substring() with addWord() rather than passing the whole word and current index around. That's somewhat less efficient, but arguably cleaner to look at. If you wanted to go that route, the addWord() methods would look like

public void addWord(final String word) {
    this.addWord(this, word);
}

private void addWord(final Dict node, final String remainingCharacters) {
    if (remainingCharacters.isEmpty()) {
        node.isWord = true;
        return;
    }

    final int linkno = indexForCharacter(remainingCharacters.charAt(0));
    if (node.children[linkno] == null) {
        node.children[linkno] = new Dict();
    }
    this.addWord(node.children[linkno], remainingCharacters.substring(1));
}

Finally, the use of in-out variables (where a parameter has its contents modified by the method it gets passed into) is discouraged in public APIs. I did this with the findWords() method for a minor performance boost. It would be more correct but ever-so-slightly less performant to write them as follows. In hindsight, this is what should have been in the original proposal, with the more performant version as the "you might need to do ".

public List<String> findWords(final Dict node) {
    return this.findWords(node, "");
}

private List<String> findWords(final Dict node, final String wordCandidate) {
    final List<String> words = new ArrayList<String>();
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node.children[i] == null) {
            continue;
        }
        if (node.children[i].isWord) {
            words.add(wordCandidate + characterForIndex(i));
        }
        words.addAll(this.findWords(node.children[i], wordCandidate + characterForIndex(i)));
    }
    return words;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.