Package org.apache.nutch.util

Class TrieStringMatcher

java.lang.Object

org.apache.nutch.util.TrieStringMatcher

Direct Known Subclasses:

PrefixStringMatcher, SuffixStringMatcher

public abstract class TrieStringMatcher
extends Object

TrieStringMatcher is a base class for simple tree-based string matching. This class is thread-safe during string matching but not when adding strings to the trie.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	TrieStringMatcher.TrieNode	Node class for the character tree.

Field Summary

Fields

Modifier and Type	Field	Description
protected TrieStringMatcher.TrieNode	root

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	TrieStringMatcher()

Method Summary

Modifier and Type	Method	Description
protected void	addPatternBackward(String s)	Adds any necessary nodes to the trie so that the given String can be decoded in reverse and the first character is represented by a terminal node.
protected void	addPatternForward(String s)	Adds any necessary nodes to the trie so that the given String can be decoded and the last character is represented by a terminal node.
abstract String	longestMatch(String input)	Returns the longest substring of input that is matched by a pattern in the trie, or null if no match exists.
protected TrieStringMatcher.TrieNode	matchChar(TrieStringMatcher.TrieNode node, String s, int idx)	Get the next TrieStringMatcher.TrieNode visited, given that you are at node, and that the next character in the input is the idx'th character of s.
abstract boolean	matches(String input)	Returns true if the given String is matched by a pattern in the trie
abstract String	shortestMatch(String input)	Returns the shortest substring of input that is matched by a pattern in the trie, or null if no match exists.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected TrieStringMatcher.TrieNode root

Constructor Detail

TrieStringMatcher

protected TrieStringMatcher()

Method Detail

matchChar

protected final TrieStringMatcher.TrieNode matchChar(TrieStringMatcher.TrieNode node,
                                                     String s,
                                                     int idx)

Get the next TrieStringMatcher.TrieNode visited, given that you are at node, and that the next character in the input is the idx'th character of s. Can return null.

Parameters:

node - Input TrieStringMatcher.TrieNode containing child nodes

s - String to match character at indexed position

idx - Indexed position in input string

Returns:

child TrieStringMatcher.TrieNode

See Also:

TrieStringMatcher.TrieNode.getChild(char)

addPatternForward

protected final void addPatternForward(String s)

Adds any necessary nodes to the trie so that the given String can be decoded and the last character is represented by a terminal node. Zero-length Strings are ignored.

Parameters:

s - String to be decoded.

addPatternBackward

protected final void addPatternBackward(String s)

Adds any necessary nodes to the trie so that the given String can be decoded in reverse and the first character is represented by a terminal node. Zero-length Strings are ignored.

Parameters:

s - String to be decoded.

matches

public abstract boolean matches(String input)

Returns true if the given String is matched by a pattern in the trie

Parameters:

input - A String to be matched by a pattern

Returns:

true if there is a match, flase otherwise

shortestMatch

public abstract String shortestMatch(String input)

Returns the shortest substring of input that is matched by a pattern in the trie, or null if no match exists.

Parameters:

input - A String to be matched by a pattern

Returns:

shortest string match or null if no match is made

longestMatch

public abstract String longestMatch(String input)

Returns the longest substring of input that is matched by a pattern in the trie, or null if no match exists.

Parameters:

input - A String to be matched by a pattern

Returns:

longest string match or null if no match is made