Class SuggestTree

java.lang.Object
com.vividsolutions.jump.util.SuggestTree
public class SuggestTree extends Object
An autocomplete data structure that enables you to quickly look up the top k terms with a given prefix in a set of weighted terms. The structure is based on a compressed trie of the terms (implemented as a randomized ternary search tree) in which each node holds a weight-ordered list of the k highest-weighted terms in its subtree.

Note that this implementation is not synchronized. If multiple threads access a Suggest Tree concurrently, and at least one of the threads modifies the tree, it must be synchronized externally.

  • Constructor Details

    • SuggestTree

      public SuggestTree(int k)
      Creates a Suggest Tree with the specified k-value.
      Parameters:
      k - the maximum number of autocomplete suggestions to return for a given prefix
      Throws:
      IllegalArgumentException - if the specified k-value is less than 1

  • Method Details

    • getAutocompleteSuggestions

      public SuggestTree.Node getAutocompleteSuggestions(String prefix)
      Returns the k highest-weighted terms in the tree that start with the specified prefix, or null if there is no such term.
      Parameters:
      prefix - the prefix for which to return autocomplete suggestions
      Returns:
      the k highest-weighted terms in the tree that start with the specified prefix, or null if there is no such term
      Throws:
      IllegalArgumentException - if the specified prefix is an empty string
      NullPointerException - if the specified prefix is null

    • getEntry

      public SuggestTree.Entry getEntry(String term)
      Returns the tree entry for the specified term, or null if there is no such entry.
      Parameters:
      term - the term for which to return the corresponding tree entry
      Returns:
      the tree entry for the specified term, or null if there is no such entry
      Throws:
      IllegalArgumentException - if the specified term is an empty string
      NullPointerException - if the specified term is null

    • iterator

      public SuggestTree.Iterator iterator()
      Returns an iterator over the terms in the tree.
      Returns:
      an iterator over the terms in the tree

    • size

      public int size()
      Returns the number of terms in the tree.
      Returns:
      the number of terms in the tree

    • put

      public void put(String term, int weight)
      Inserts the specified term with the specified weight into the tree, or reweights the term if it is already present.
      Parameters:
      term - the term to be inserted or reweighted
      weight - the weight to be assigned to the term
      Throws:
      IllegalArgumentException - if the specified term is an empty string or much too long (longer than 32767 characters)
      NullPointerException - if the specified term is null

    • remove

      public void remove(String term)
      Removes the specified term from the tree.
      Parameters:
      term - the term to be removed
      Throws:
      IllegalArgumentException - if the specified term is an empty string
      NullPointerException - if the specified term is null