11
\$\begingroup\$

I was working on a task to implement auto suggest from an array of couple of thousands of strings.

Of course, the first and the easiest implementable was to go through each element and do a[i].startWith(query). Technically the time complexity of this algorithm then would be \$O(n+(q*m))\$. Here, n equals the number of elements in the array, q equals the number of total matches and m equals the number of characters in the query (I am not sure how accurate I am here).

Regardless, I have created a following Trie which at every node keeps track of every child that has a word ending there.

For example, if the query is "can" then with only three traversal the tree will return cancel, cancer, can and cancellation because the node 'n' will have connections to all the sub trees that has a word ending!

I would really like to hear some comments on this.

package utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *
 * @author Sapan
 */
public class Trie {

    private Map<Character, Trie> children;
    private String word = null;
    private Set<Trie> connections;
    static int count = 0;

    public Trie() {
        this.children = new HashMap<>();
        connections = new HashSet<>();
    }
    /*
     * Builds a Trie with given query
     */

    public void add(String word) {
        if (word == null || "".equals(word.trim())) {
            throw new IllegalArgumentException("Query can not be empty or null");
        }
        Trie t = this;
        for (Character c : word.toCharArray()) { //for every character in query do the following....
            //add character to the current instance and get the child instance right after adding the current char
            if (!t.children.containsKey(c)) {
                t.children.put(c, new Trie());
            }
            t = t.children.get(c);
        }
        t.word = word;
    }

    public Set search(String word) {
        count = 0;
        Trie current = this;
        Set<Trie> matches = new HashSet();
        for (Character c : word.toCharArray()) {
            ++count;
            current = current.children.get(c);
            if (current == null){
                return matches;
            }
        }
        //System.out.println(current);
        if (current == null) {
            return matches;
        }

        matches = current.connections;

        return matches;
    }
    public Set build() {
        //matches = new HashSet<>();
        ++count;
        for (Character c : this.children.keySet()) {
            this.connections.addAll(this.children.get(c).build());
        }
         if (this.word != null && this.word.length() > 0) {
             this.connections.add(this);
        }
         if (this.children.keySet().isEmpty()) {// we are at the leaf node
            this.connections.add(this);
        }
        return this.connections;
    }


    public static void main(String[] args) {
        Trie t = new Trie();
        t.add("can");
        t.add("kangaroo");
        t.add("roo");
        t.add("rash");
        t.add("ram");
        t.add("rat");
        t.add("kansas");
        t.add("banana");
        t.add("ban");
        t.add("cancel");
        t.add("cancer");
        t.add("add");
        t.add("addition");
        t.add("sub");
        t.add("subtraction");
        t.add("ape");
        t.add("apple");
       // t.build();
        t.build();
        System.out.println(t);
        System.out.println(t.count+"----");
        //System.out.println(t);
       // List<Trie> l = t.search("ap");

        //System.out.println(l);
       // for (char c = 'a'; c <= 'z'; c++) {
           Set<Trie> l = t.search("ca");
           System.out.println(t.count);
            System.out.println("words starting from ca ");
            for (Trie trie : l) {
                System.out.println(trie.word);
            }
    }
}
\$\endgroup\$
8
\$\begingroup\$
  1. Eclipse says that the second null check in the search method is dead code:

    if (current == null) {
        return matches;
    }
    

    Furthermore, it could be refactored to the following:

    public Set<Trie> search(final String word) {
        count = 0;
        Trie current = this;
        for (final Character c: word.toCharArray()) {
            ++count;
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptySet();
            }
        }
        return current.connections;
    }
    
  2. You should specify the return types:

    public Set<Trie> search(final String word) { ... }
    public Set<Trie> build() {... }
    

    instead of

    public Set search(final String word) { ... }
    public Set build() {... }
    
  3. Consider using

    I've found them more readable.

  4. If I'm right you could iterate over the values directly in the build method:

    for (final Trie childTrie: children.values()) {
        connections.addAll(childTrie.build());
    }
    
  5. I'd separate the builder logic from the Trie class. Currently clients can easily misuse this class:

    t.build();
    t.add("can2");
    

    (Effective Java, 2nd Edition, Item 2: Consider a builder when faced with many constructor parameters)

  6. connections does not seem a good name. It took some time to figure out that this set contains the descendant Trie objects which has a word. I might call it descendantsWithWord. Furthermore, it could contain only the words (strings), not the Trie objects, so it could be simply Set<String> descendantWords.

  7. The static count field does not smells well. It is used for two different purposes. I'd create a createdTrieObjects field:

    private int createdTrieObjects = 1;
    

    and increment it in the add method:

    t.children.put(c, new Trie());
    createdTrieObjects++;
    

    On the other hand, in the search method you could return a SearchResult object which contains the search depth (it's the count currently) and the result strings:

    public class SearchResult {
    
        private final Set<String> words;
        private final int searchDepth;
    
        ...
    
    }
    

    It contains only a set of string instead of the Set<Trie> collection. I think clients should not know about the internal Trie objects. If you don't need the search depth return with Set<String> only:

    public Set<String> search(final String wordStart) {
        Trie current = this;
        for (final Character c: wordStart.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptySet();
            }
        }
        return Collections.unmodifiableSet(current.descendantWords);
    }
    

    Please note the Collections.unmodifiableSet call. It prohibits malicious clients to modify the Trie's internal structure. (Effective Java, 2nd Edition, Item 39: Make defensive copies when needed)

  8. You could eliminate the build method and the word field if you fill the descendantWords in the add method:

     public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        Trie current = this;
        descendantWords.add(word);
        for (final Character c: word.toCharArray()) {
            if (!current.children.containsKey(c)) {
                current.children.put(c, new Trie());
                createdTrieObjects++;
            }
            current = current.children.get(c);
            current.descendantWords.add(word);
        }
    }
    

Some small notes about the edit:

  1. Instead of the checked IllegalAccessException I'd throw runtime IllegalStateException. It's rather a programming error if a client tries to add new element to a built trie. (Effective Java, 2nd Edition, Item 58: Use checked exceptions for recoverable conditions and runtime exceptions for programming errors)

  2. About the s variable in the search method: Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method, declare them where they are first used. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

  3. You could copy the descendantsWithWord set with the HashSet's constructor instead of the for loop in the search method:

    return new HashSet<String>(current.descendantWords);
    
  4. The isBuilt flag should be at the beginning of the class with the other fields.

Here is the refactored version:

import java.util.Collections;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang3.StringUtils;

import static com.google.common.base.Preconditions.*;

public class Trie {

    private final Map<Character, Trie> children = new HashMap<Character, Trie>();
    private final Set<String> descendantWords = new HashSet<String>();

    public Trie() {
    }

    public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        Trie current = this;
        descendantWords.add(word);
        for (final Character c: word.toCharArray()) {
            if (!current.children.containsKey(c)) {
                current.children.put(c, new Trie());
            }
            current = current.children.get(c);
            current.descendantWords.add(word);
        }
    }

    public Set<String> search(final String wordStart) {
        checkNotNull(wordStart, "wordStart cannot be null");
        Trie current = this;
        for (final Character c: wordStart.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptySet();
            }
        }
        return Collections.unmodifiableSet(current.descendantWords);
    }
}

Edit for the comment:

In your original implementation there is a set (descendantsWithWord) in every node which refers to Trie objects. In this answer there is a set (descendantWords) in every level which refers to String objects.

The size of the sets are the same, Strings (as well as other objects, like Tries) are on the heap, the set contains only references to objects, so it does not count if they are Strings, Tries or other Objects, there is no difference in memory consumption and there is no duplication. The only difference is the method where the trie builds the set and the generic type of the set (references in the set).

I'm not too familiar with tries and articles on the Wikipedia do not mention that trie nodes should or should not store each descendants (not just references to the nodes of the next level), so I'm not sure that this is "officially" a trie or not.

Anyway, if I'm right you need fast search, so memory consumption looks is secondary here. Precalculating and storing the result in a cache (i.e. descendantWords) seems a better solution that traversing a subtree and building strings from characters on every search request as you did it too.

Furthermore, I'd consider using a Map<String, Set<String>> structure:

c,      [can, cancel, cancer]
ca,     [can, cancel, cancer]
can,    [can, cancel, cancer]
canc,   [cancel, cancer]
cance,  [cancel, cancer]
cancel, [cancel]
cancer, [cancel]
...

It's very similar to the trie above since (1) the trie's nodes are the same as the keys in this map and (2) the values of the map are the same as the descendantWords set in the trie. An advantage could be a simpler implementation, especially with a Multimap from Guava:

public class AutoSuggestCache {

    private final SetMultimap<String, String> words = HashMultimap.create();

    public AutoSuggestCache() {
    }

    public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        for (int endIndex = 0; endIndex < word.length(); endIndex++) {
            final String wordStart = word.substring(0, endIndex);
            words.put(wordStart, word);
        }
    }

    public Set<String> search(final String wordStart) {
        checkNotNull(wordStart, "wordStart cannot be null");
        return Collections.unmodifiableSet(words.get(wordStart));
    }
}
\$\endgroup\$
  • \$\begingroup\$ The count variable was just for testing only, I got rid of it.. But I really wonder that in your 7th point why do we use SearchResult object rather then just letting the Search method return Set<String>? Do you think the changed Search method will not be enough? \$\endgroup\$ – Grrrrr Sep 25 '12 at 15:08
  • \$\begingroup\$ @Grrrrr: I've created the SearchResult object only because of the count variable. If you don't need it you could return with Set<String>. Check the update, please. \$\endgroup\$ – palacsint Sep 25 '12 at 17:43
  • \$\begingroup\$ Adding the words to the list while calling the "add" method also occurred to me but I thought that this way there will be an extra copy of the every word at every level! Is it not better to keep a reference to the node? (I am not sure if I am being too abstract here!) \$\endgroup\$ – Grrrrr Oct 1 '12 at 21:43
  • \$\begingroup\$ @Grrrrr: Check the edit please. :) \$\endgroup\$ – palacsint Oct 2 '12 at 21:56

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.