edu.illinois.cs.cogcomp.core.algorithms

Class TreeGrep<T>

java.lang.Object

edu.illinois.cs.cogcomp.core.algorithms.TreeGrep<T>

public class TreeGrep<T>
extends Object

Search trees for a fixed pattern.

Usage:

Suppose tree is some tree and we wish to find all instances of pattern in it.

 TreeGrep<String> grepper = new TreeGrep<String>(pattern);
 if (grepper.matches(tree)) {
     List<TreeGrepMatch<String>> matches = grepper.getMatches();
     for (TreeGrepMatch<String> match : matches) {
         // do something with the match
     }
 }

 

Refer the documentation of TreeGrepMatch for details about how to use it the match object. This class does not yet support regular expression searches for trees like tregex or tgrep. Moreover, the current implementation can be improved by using something like the Boyer-Moore algorithm for both vertical and horizontal search.

Author:

Vivek Srikumar

See Also:

TreeGrepMatch

Field Summary

Fields

Modifier and Type	Field and Description
static String	endOfChildrenString
protected List<TreeGrepMatch<T>>	matchesList
static String	startOfChildrenString

Constructor Summary

Constructors

Constructor and Description
TreeGrep(Tree<T> pattern)

Method Summary

Modifier and Type	Method and Description
protected boolean	doesLabelMatchPatternLabel(T treeLabel, T patternLabel)
protected List<TreeGrepMatch<T>>	doesNodeMatchPattern(Tree<T> tree, Tree<T> currentPattern, List<TreeGrepMatch<T>> nodeMatches)
boolean	doesThisTreeMatch(Tree<T> tree) Checks if the tree that is passed as a parameter matches the pattern.
List<TreeGrepMatch<T>>	getMatches() Gets a list of matches for the pattern in the most recently searched tree.
Tree<T>	getPattern()
boolean	matches(Tree<T> tree) This checks whether any subtrees of tree match the pattern.
protected List<TreeGrepMatch<T>>	mergeChildrenMatches(List<List<TreeGrepMatch<T>>> childrenMatches, List<TreeGrepMatch<T>> currentNodeMatches)
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

endOfChildrenString

public static String endOfChildrenString

startOfChildrenString

public static String startOfChildrenString

matchesList

protected List<TreeGrepMatch<T>> matchesList

Constructor Detail

TreeGrep

public TreeGrep(Tree<T> pattern)

Method Detail

matches

public boolean matches(Tree<T> tree)

This checks whether any subtrees of tree match the pattern.

Note: Each subtree might have multiple matches within it that match the pattern. For example, if the pattern is

(VP (NP NN ))

and the tree has

(VP (NP NN) (NP NN))

then, this function will only return the (VP...) subtree, and does not indicate that there are two matches within that subtree, both rooted at the VP.

doesThisTreeMatch

public boolean doesThisTreeMatch(Tree<T> tree)

Checks if the tree that is passed as a parameter matches the pattern. This is different from matches(Tree) because it does not recursively check interior nodes for matches.

getMatches

public List<TreeGrepMatch<T>> getMatches()

Gets a list of matches for the pattern in the most recently searched tree.

Returns:

A list of TreeGrepMatch objects. See the general documentation of this class for a sample usage.

doesLabelMatchPatternLabel

protected boolean doesLabelMatchPatternLabel(T treeLabel,
                                             T patternLabel)

doesNodeMatchPattern

protected List<TreeGrepMatch<T>> doesNodeMatchPattern(Tree<T> tree,
                                                      Tree<T> currentPattern,
                                                      List<TreeGrepMatch<T>> nodeMatches)

mergeChildrenMatches

protected List<TreeGrepMatch<T>> mergeChildrenMatches(List<List<TreeGrepMatch<T>>> childrenMatches,
                                                      List<TreeGrepMatch<T>> currentNodeMatches)

toString

public String toString()

Overrides:

toString in class Object

getPattern

public Tree<T> getPattern()

Returns:

the pattern