Suffix tree implementation in Java

Question

I was trying to solve the problem where given a larger string and an array/list of smaller string, we need to make the determination whether the larger string contains each of the smaller strings. I realized one way to do it would be to create a suffix tree for the larger string and then look for each of the smaller strings within the suffix tree.

My SuffixTree is essentially a Node which contains a value and a Map of <Character,Node> for its children.

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class SuffixTree{
 class Node{
   private final char currentValue;
   private Map<Character,Node> children;
   Node(){
     this.currentValue = '*';
     this.children = new HashMap<Character,Node>();
   }    
   Node(char currentValue){
     this.currentValue = currentValue;
     this.children = new HashMap<Character,Node>();
   }       

   char getValue(){
     return this.currentValue;
   }

   void addChild(Node c){
    this.children.put(c.getValue(),c);
   }

   boolean hasChild(Node c){
    return this.children.containsKey(c.getValue());
   }  

   Node getChild(Node c){
     return this.children.get(c.getValue());
   }

  public String toString(){
    char currentValue = this.getValue();
    StringBuffer keys = new StringBuffer();
    for(char key:this.children.keySet()){
      keys.append("Current key:"+key+"\n");
    }
     return "Current value:"+currentValue+"\n"+
        "Keys:"+keys.toString(); 
   }
  }  

  private Node root;

  private void log(Object l){
     System.out.println(l);
  }
  /*
   * Helper method that initializes the suffix tree
   */
  private Node createSuffixTree(String source,Node root){
    for(int i=0;i<source.length();i++){
      Node parent = new Node(source.charAt(i));
      if(root.hasChild(parent)){
        parent = root.getChild(parent);
      }
      Node current = parent;            
      for(int j=i+1;j<source.length();j++){
        Node temp = new Node(source.charAt(j));
    if(current.hasChild(temp)){
      temp = current.getChild(temp);
    }else{
      current.addChild(temp);
    }
        current = temp; 
      }
      root.addChild(parent);    
    }
    return root;         
  }

  /*
   Creates the suffix tree from the given string
   */
  public SuffixTree(String source){
    this.root = createSuffixTree(source,new Node());
  }   

  void printMap(Map<Character,Node> map){
     for(char c:map.keySet()){
      System.out.println("Current node has child"+c);
    }
  }  

  boolean search(String target){
    Map<Character,Node> rootChildren = this.root.children;
   for(char c:target.toCharArray()){
      if(rootChildren.containsKey(c)){
        rootChildren = rootChildren.get(c).children;
      }else{
        return false;
      }
    }
    return true;
  }

   public static void main(String[] args){
    SuffixTree sTree = new SuffixTree("bananas");
    List<String> input = new ArrayList<String>(){{
                 add("ba");
                 add("ban");
                 add("ana");
                 add("anas");
                 add("nan");
                 add("anans");
                 add("ananas");
                 add("n");
                 add("s");
                 add("as");
                 add("naab");
                 add("baan");
                 add("aan");
                }};
    for(String i:input){
      String exists = "exists";
      if(!sTree.search(i)){
        exists = "doesn't exist";
      }
      System.out.println("Input:"+i+" "+exists);
    }
   }
}

Answer 1

Let's break down your algorithm for a moment:

1. get a String to analyze ("bananas").
2. do a 'nested' loop (i,j) to find every possible sub-word in it
3. for each sub-word, inject it in to the possible node tree 1 character at a time.

With that tree, you can then compare matching values to see if they exist in the tree. To see if they exist, you:

1. loop over each character in the search word
2. for each character, you check whether a Node exists matching the respective character a the respective level.
3. if any character is impossible, you return false. If all characters are possible, you return true.

Problems

1. the name - it is not a "Suffix" Tree, it is an "Infix" tree. It does not match only suffixes.
2. the overhead - The HashMap instances and the Character and Node classes, are a problem from a memory perspective. Sure, the count of these instances will be relatively small, but, for "bananas", you are creating about.... 28 HashMaps? Each HashMap has a significant memory footprint. It is expensive.

Advantages

1. the perceived advantage here is that you have discrete places where the data exists in a tree. You can check for infixes starting from any character in the base word, at the same time.

Alternatives

There are two alternatives I recommend, the differences between them will depend on the number of letters in the input word. The one solution has a runtime performance of \$O(1)\$, but a memory consumption of \$O(n^2)\$. The other has a runtime performance of \$O(n \log n)\$ and a memory consumption of \$O(n)\$. Note that your solution has a runtime performance of \$O(n)\$ and a memory size of \$O(n^2)\$.

What does that mean? It means the one alternative will have slitgtly worse performance than yours for larger inputs, but will take much less space. The other alternative will be much faster than yours for larger inputs, and will take about the same proportion of space. Each alternative has merits over yours.

In your solution, with \$n\$ being the number of letters in the input word ("bananas"), your runtime performance requires you scanning the Node tree for as many as n nodes (one for each letter), which makes your check performance proportional to the number of characters in the input word. The number of nodes you have is proportional to the square of the number of input letters, so if you double the number of letters, you quadruple the number of nodes.

The two alternatives I suggest are different, in that the one alternative will have an \$O(n \log n)\$ search performance but an \$O(n)\$ memory performance. Because of the way the data is stored, though, for smaller input strings ("bananas" is small), it will likely be much faster though, than yours.

The other solution is much faster (essentially constant time - \$O(1)\$ ), but has a higher memory cost - about the same as your code.

Fastest - and Largest

The fastest solution is to take all possible substrings from the input and put them in a HashSet. The input processing is simple:

Set<String> infixes = new HashSet<>();
for (int i = 0; i < input.length; i++) {
    for (j = i + 1; j < input.length; j++) {
        infixes.add(input.substring(i,j));
    }
}

Now, there's a single HashSet (which under the covers is a HashMap), and it contains all substrings. Searching for those substrings is a case of computing the hashCode of the search value, and it will find the value "fast"...

return infixes.contains(search);

That algorithm stores potentially a lot of strings, but the search is lightning fast.

The way this code works, is by taking the input string, and splitting it in all possible ways. For example, from "fubar" you will get:

f fu fub fuba fubar u ub uba ubar b ba bar a ar r

Put those all in the set, and every possible infix "search" word is recorded. The HashSet makes the search effectively an O(1) operation.

Fastish - and Smallish

The second alternative will slow down (very slightly) as the input words get larger, but the memory footprint will be relatively small.

First, create an Array of words.... each word being a suffix:

String[] suffixes = new String[input.length];
for (int i = 0; i < input.length; i++) {
    suffixes[i] = input.substring(i);
}

Then, sort it....

Arrays.sort(suffixes);

That array is pretty small in comparison to your alternatives....

Now, using that, you can quickly find (in \$O(n \log n)\$ time) whether a search string is a suffix:

int ip = Arrays.binarySearch(suffixes, search);
if (ip >= 0) {
    // exact match to a suffix
    return true;
}
// no exact match, but, maybe the place the value would
// belong is a longer version of our search term....
ip = -ip - 1;

return ip < suffixes.length && suffixes[ip].startsWith(search);

This algorithm works in part by relying on the lexical (alphabetical) sorting of any suffix of the input word. Again, using "fubar", the code creates all 5 suffixes:

fubar ubar bar ar r

It then sorts them alphabetically:

ar
bar
fubar
r
ubar

Now, if you want to find a search string that is a complete suffix (like "bar"), then the binary search will find it no problem, and return true. But, what if you want tos earch for an "infix", or a not-complete suffix, for example, "ba"? Well, "ba" would normally fit alphabetically between "ar" and "bar". The Arrays.binarySearch will return the 'insertion point' of -2. The -2 indicates that there was not an exact match, but if we want to insert the value in the array, we would insert it before the element at - ip - 1, or, since the ip is -2, at - (-2) - 1, or before position 1.

Note though, that because of the alphabetic order, if the search term is an infix, it is by definition, a prefix of a suffix ;-), and if it is a prefix of a suffix, the suffix it is a prefix of is alphabetically immediately after it. So, if the search term matches the start of the insertion-point value, then the search term is an infix of the original word.

That's all just a complicated way of saying: if the search term is an exact match of a suffix, it is a match, or, if it matches the beginning of the suffix alphabetically after it, it is a match.

Either way, you can locate that match with the binary search, and test the insertion point.

Code

public class SearchNLogN {

    private final String[] suffixes;

    public SearchNLogN(String input) {
        suffixes = new String[input.length()];
        for (int i = 0; i < suffixes.length; i++) {
            suffixes[i] = input.substring(i);
        }
        Arrays.sort(suffixes);
    }

    public boolean search(final String search) {
        int ip = Arrays.binarySearch(suffixes, search);
        if (ip >= 0) {
            return true;
        }
        ip = -ip - 1;
        return ip < suffixes.length && suffixes[ip].startsWith(search);
    }

}

and

import java.util.HashSet;
import java.util.Set;

public class SearchO1 {

    private final Set<String> infixes = new HashSet<>();

    public SearchO1(String input) {
        for (int i = 0; i < input.length(); i++) {
            for (int j = i + 1; j <= input.length(); j++) {
                infixes.add(input.substring(i, j));
            }
        }
    }

    public boolean search(String search) {
        return infixes.contains(search);
    }

}

Results

Running the two code chunks above, as well as your code chunk, for a number of iunput values ("foo", "bananas", and "supercali......"), with a number of test values (including the input value itself), and then benchmarking the results (using Microbench ), I get:

Your code: small, medium, large (microseconds) - 0.24, 0.5, 1.2

Task SuffixTree -> foo: (Unit: MICROSECONDS)
  Count    :     10000      Average  :    0.5620
  Fastest  :    0.2390      Slowest  : 1044.6770
  95Pctile :    0.7730      99Pctile :    1.2420
  TimeBlock : 1.480 0.471 0.326 0.271 0.257 0.254 0.263 0.249 0.252 1.804
  Histogram :  8781   855   302    11     1    44     2     1     1     0     0     1     1

Task SuffixTree -> bananas: (Unit: MICROSECONDS)
  Count    :     10000      Average  :    0.9490
  Fastest  :    0.5020      Slowest  : 1107.9860
  95Pctile :    1.7720      99Pctile :    2.7260
  TimeBlock : 2.734 0.848 0.670 0.635 0.532 0.635 0.635 0.612 1.638 0.561
  Histogram :  8790   870   268    13    12    41     0     5     0     0     0     1

Task SuffixTree -> supercalifragilisticexpialidocious if you like the sounds of that it must be quite atrocious.: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   1.8380
  Fastest  :   1.2400      Slowest  :  96.8740
  95Pctile :   3.8860      99Pctile :   5.9270
  TimeBlock : 5.778 1.999 1.392 1.321 1.300 1.337 1.315 1.276 1.301 1.371
  Histogram :  8782  1082    51    44    24    16     1

Search O1: small, medium, large (microseconds) - 0.18, 0.25, 0.21

Task SearchO1 -> foo: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.7840
  Fastest  :   0.1810      Slowest  :  75.3810
  95Pctile :   1.9970      99Pctile :   2.5670
  TimeBlock : 2.212 2.002 1.980 0.255 0.236 0.250 0.236 0.228 0.225 0.226
  Histogram :  6978     3     3  2944    46    12    13     0     1

Task SearchO1 -> bananas: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.9330
  Fastest  :   0.2510      Slowest  :  36.0610
  95Pctile :   2.2400      99Pctile :   3.1790
  TimeBlock : 2.429 2.231 2.284 0.367 0.343 0.356 0.346 0.340 0.318 0.316
  Histogram :  6969     3   243  2735    19    28     1     2

Task SearchO1 -> supercalifragilisticexpialidocious if you like the sounds of that it must be quite atrocious.: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.8450
  Fastest  :   0.2190      Slowest  :  21.3880
  95Pctile :   2.1300      99Pctile :   2.6750
  TimeBlock : 2.208 2.120 2.104 0.309 0.290 0.297 0.291 0.279 0.279 0.276
  Histogram :  6966    13    29  2955    23    13     1

Search NlogN: small, medium, large (microseconds) - 0.24, 0.33, 0.60

Task SearchNLogN -> foo: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.5180
  Fastest  :   0.2430      Slowest  :  66.9210
  95Pctile :   1.0680      99Pctile :   2.2020
  TimeBlock : 1.430 0.350 0.252 0.357 0.504 0.504 0.550 0.531 0.392 0.312
  Histogram :  5928  3500   389   128    20    29     4     1     1

Task SearchNLogN -> bananas: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.6610
  Fastest  :   0.3340      Slowest  :  44.2550
  95Pctile :   1.2930      99Pctile :   2.5630
  TimeBlock : 1.671 0.429 0.350 0.497 0.678 0.675 0.705 0.688 0.542 0.384
  Histogram :  6812  2758   342    48    25     9     5     1

Task SearchNLogN -> supercalifragilisticexpialidocious if you like the sounds of that it must be quite atrocious.: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   1.1370
  Fastest  :   0.6030      Slowest  :  46.9750
  95Pctile :   1.9280      99Pctile :   4.7460
  TimeBlock : 2.719 0.737 0.628 0.887 1.187 1.194 1.204 1.216 0.924 0.679
  Histogram :  8380  1266   256    57    34     6     1

Answer 2

If you really want I could make a review of your solution, but to me it looks overly complicated for the task.

If aim is to check whether larger string contains each shorter string from a list, why do not simply use String's class built-in contains() method?

public class StringUtil {

    public static void main(String[] args){
        String input = "bananas";
        List<String> substrings = new ArrayList<String>(){{
                 add("ba");
                 add("ban");
                 add("ana");
                 add("anas");
                 add("nan");
                 add("anans");
                 add("ananas");
                 add("n");
                 add("s");
                 add("as");
                 add("naab");
                 add("baan");
                 add("aan");
                }};
        if(StringUtil.containsAllSubstrings(input, substrings)) {
            System.out.println("Input: \"" + input + "\" contains all substrings.");
        } else {
            System.out.println("Input: \"" + input + "\" does not contain all substrings.");
        }
    }

    public static Boolean containsAllSubstrings( String input, List<String> substrings) {
        for(String substring : substrings) {
            if(!input.contains(substring)) {
                return false;
            }
        }
        return true;
    }
}

Answer 3

There is a lot of fat to be trimmed, mainly due to the ineffective Node inner class. This solution is functionally equivalent:

import java.util.HashMap;

public class SuffixTree {
    private static class Node extends HashMap<Character, Node> {
        /**
         * Follows a link to get a child node.  If no such link
         * exists, then create and attach an empty child node.
         */
        Node getOrPut(char c) {
            Node child = this.get(c);
            if (child == null) {
                this.put(c, child = new Node());
            }
            return child;
        }
    }

    private Node root;

    /**
     * Creates the suffix tree from the given string.
     */
    public SuffixTree(CharSequence source) {
        this.root = new Node();
        for (int i = 0; i < source.length(); i++) {
            Node n = this.root.getOrPut(source.charAt(i));
            for (int j = i + 1; j < source.length(); j++) {
                n = n.getOrPut(source.charAt(j));
            }
        }
    }

    public boolean contains(CharSequence target) {
        Node n = this.root;
        for (int i = 0; i < target.length(); i++) {
            n = n.get(target.charAt(i));
            if (n == null) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        SuffixTree sTree = new SuffixTree("bananas");
        String[] input = new String[] {
            "ba",
            "ban",
            "ana",
            "anas",
            "nan",
            "anans",
            "ananas",
            "n",
            "s",
            "as",
            "naab",
            "baan",
            "aan",
        };
        for (String s : input) {
            String exists = sTree.contains(s) ? "exists" : "doesn't exist";
            System.out.printf("Input: %s %s\n", s, exists);
        }
    }
}

Remarks:

1. Node should be a static inner class, since it doesn't need to refer to the SuffixTree to which it belongs. Inner classes should be static whenever possible.
2. I don't find that the addChild(), hasChild(), and getChild() methods add much value beyond the put(), containsKey(), and get() methods of Map. In particular, hasChild(Node c) and getChild(Node c) are silly, since you have to first construct a node to look up a node. Once you fix that inefficiency, you'll find that the currentValue field is worthless.
3. Once you discard the currentValue field, then Node just is a HashMap. I've added a convenience method getOrPut() to simplify the suffix tree creation process.
4. I don't see any point to having a createSuffixTree() helper function. Why not just put that code in the SuffixTree constructor?
5. For generality, you can accept any CharSequence, not just String.
6. The search() method needs to be public, otherwise there is no point to your class. Since it returns a boolean, I would rename it to contains(), so that the code that calls it reads more smoothly.
7. In main(), populating the input list using a static initializer block of an anonymous inner class that subclasses ArrayList is overkill. Here, just a String[] array will do. If you really needed an ArrayList, then use Arrays.asList("ba", "ban", … ).

8. This is better written as a ternary expression:

   String exists = "exists";
   if(!sTree.search(i)){
     exists = "doesn't exist";
   }
   

9. Your indentation is inconsistent.
10. The comment on the SuffixTree constructor looks like JavaDoc, but isn't. If you write a comment at all, then make it valid JavaDoc.