HyperSQL Database 2.7.4 · org.hsqldb.lib.KMPSearchAlgorithm

Implements the Knuth-Morris-Pratt string search algorithm for searching streams or arrays of octets or characters.

This algorithm is a good choice for searching large, forward-only access streams for repeated search using pre-processed small to medium-sized patterns.

This is because in addition to the facts that it:

does not require pre-processing the searched data (only the pattern)
scans strictly left-to-right
does not need to perform back tracking
does not need to employ reverse scan order
does not need to perform effectively random access lookups against the searched data or pattern

it also has:

a very simple, highly predictable behavior
an O(n) complexity once the a search pattern is preprocessed
an O(m) complexity for pre-processing search patterns
a worst case performance characteristic of only 2n
an average case performance characteristic that is deemed to be 2-3 times better than the naive search algorithm employed by String#indexOf(java.lang.String, int).

Note that the Boyer-Moore algorithm is generally considered to be the better practical, all-round exact sub-string search algorithm, but due to its reverse pattern scan order, performance considerations dictate that it requires more space and that is somewhat more complex to implement efficiently for searching forward-only access streams.

In particular, its higher average performance is biased toward larger search patterns, due to its ability to skip ahead further and with fewer tests under reverse pattern scan. But when searching forward-only access streams, overall performance considerations require the use a circular buffer of the same size as the search pattern to hold data from the searched stream as it is being compared in reverse order to the search pattern. Hence, Boyer-Moore requires at minimum twice the memory required by Knuth-Morris-Pratt to search for the same pattern and that factor has the greatest impact precisely on the same class of patterns (larger) for which it is most outperforms Knuth-Morris-Pratt.

Access	Constructor and Description
private	KMPSearchAlgorithm()

Method Summary

Modifier and Type	Method and Description
public static int[]	Returns: the table computed from the octet pattern. computeTable(final byte[] for which to compute the table. pattern) computes the table used to optimize octet pattern search
public static int[]	Returns: the table computed from the character pattern. computeTable(final char[] for which to compute the table. pattern) computes the table used to optimize octet pattern search
public static int[]	Returns: the table computed from the String pattern. computeTable(final String for which to compute the table. pattern) computes the table used to optimize octet pattern search
public static long	Returns: zero-based offset of first match; -1 if `inputStream == null \|\| pattern == null` or no match found, ; zero (0) if `pattern.length == 0`. search(final InputStream in which to search inputStream, final byte[] for which to search pattern, int[] computed from the pattern that optimizes the search. If null, automatically computed. table) Searches the given octet stream for the given octet pattern returning the zero-based offset from the initial stream position at which the first match is detected.
public static long	Returns: zero-based offset of first match; -1 if `reader == null \|\| pattern == null` or no match found, ; zero (0) if `pattern.length == 0`. search(final Reader in which to search reader, final char[] for which to search pattern, int[] computed from the pattern that optimizes the search If null, automatically computed. table) Searches the given character stream for the given character pattern returning the zero-based offset from the initial stream position at which the first match is detected.
public static long	Returns: zero-based offset of first match; -1 if `reader == null \|\| pattern == null` or no match found, ; zero (0) if `pattern.length() == 0`. search(final Reader in which to search reader, final String for which to search pattern, int[] computed from the pattern that optimizes the search If null, automatically computed. table) Searches the given character stream for the given character pattern returning the zero-based offset from the initial stream position at which the first match is detected.
public static int	Returns: zero-based offset of first match; -1 if `source == null \|\| pattern == null` or no match found, ; start if `pattern.length == 0 and start <= source.length`. search(final byte[] array in which to search source, final byte[] to be matched pattern, int[] computed from the pattern that optimizes the search If null, automatically computed. table, final int position in source at which to start the search start) Searches the given octet string for the given octet pattern returning the zero-based offset from given start position at which the first match is detected.
public static int	Returns: zero-based offset of first match; -1 if `source == null \|\| pattern == null` or no match found, ; start if `pattern.length == 0 and start <= source.length`. search(final char[] array in which to search source, final char[] to be matched pattern, int[] computed from the pattern that optimizes the search If null, automatically computed. table, final int position in source at which to start the search start) Searches the given character array for the given character pattern returning the zero-based offset from given start position at which the first match is detected.
public static int	Returns: zero-based offset of first match; -1 if `source == null \|\| pattern == null` or no match found, ; start if `pattern.length == 0 and start <= source.length`. search(final String array to be searched source, final String to be matched pattern, int[] computed from the pattern that optimizes the search table, final int position in source at which to start the search start) Searches the given String object for the given character pattern returning the zero-based offset from given start position at which the first match is detected.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Constructor Detail

KMPSearchAlgorithm	back to summary
private KMPSearchAlgorithm()

Method Detail

computeTable back to summary

computeTable	back to summary
public static int[] computeTable(final byte[] pattern) computes the table used to optimize octet pattern search Parameters pattern:byte[] for which to compute the table. Returns:int[] the table computed from the octet pattern. Exceptions IllegalArgumentException: if `pattern == null \|\| pattern.length < 2`.

public static int[] computeTable(final byte[] pattern)

computes the table used to optimize octet pattern search

Parameters

pattern:byte[]: for which to compute the table.

Returns:int[]

the table computed from the octet pattern.

Exceptions

IllegalArgumentException:: if pattern == null || pattern.length < 2.

computeTable back to summary

computeTable	back to summary
public static int[] computeTable(final char[] pattern) computes the table used to optimize octet pattern search Parameters pattern:char[] for which to compute the table. Returns:int[] the table computed from the character pattern. Exceptions IllegalArgumentException: if `pattern == null \|\| pattern.length < 2`.

public static int[] computeTable(final char[] pattern)

computes the table used to optimize octet pattern search

Parameters

pattern:char[]: for which to compute the table.

Returns:int[]

the table computed from the character pattern.

Exceptions

IllegalArgumentException:: if pattern == null || pattern.length < 2.

computeTable back to summary

computeTable	back to summary
public static int[] computeTable(final String pattern) computes the table used to optimize octet pattern search Parameters pattern:String for which to compute the table. Returns:int[] the table computed from the String pattern. Exceptions IllegalArgumentException: if `pattern == null \|\| pattern.length < 2`.

public static int[] computeTable(final String pattern)

computes the table used to optimize octet pattern search

Parameters

pattern:String: for which to compute the table.

Returns:int[]

the table computed from the String pattern.

Exceptions

IllegalArgumentException:: if pattern == null || pattern.length < 2.

search back to summary

search	back to summary
public static long search(final InputStream inputStream, final byte[] pattern, int[] table) throws IOException Searches the given octet stream for the given octet pattern returning the zero-based offset from the initial stream position at which the first match is detected. Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time. Parameters inputStream:InputStream in which to search pattern:byte[] for which to search table:int[] computed from the pattern that optimizes the search. If null, automatically computed. Returns:long zero-based offset of first match; -1 if `inputStream == null \|\| pattern == null` or no match found, ; zero (0) if `pattern.length == 0`. Exceptions IOException: when an error occurs accessing the input stream.

public static long search(final InputStream inputStream, final byte[] pattern, int[] table) throws IOException

Searches the given octet stream for the given octet pattern returning the zero-based offset from the initial stream position at which the first match is detected.

Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time.

Parameters

inputStream:InputStream: in which to search
pattern:byte[]: for which to search
table:int[]: computed from the pattern that optimizes the search. If null, automatically computed.

Returns:long

zero-based offset of first match; -1 if inputStream == null || pattern == null or no match found, ; zero (0) if pattern.length == 0.

Exceptions

IOException:: when an error occurs accessing the input stream.

search back to summary

search	back to summary
public static long search(final Reader reader, final char[] pattern, int[] table) throws IOException Searches the given character stream for the given character pattern returning the zero-based offset from the initial stream position at which the first match is detected. Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time. Parameters reader:Reader in which to search pattern:char[] for which to search table:int[] computed from the pattern that optimizes the search If null, automatically computed. Returns:long zero-based offset of first match; -1 if `reader == null \|\| pattern == null` or no match found, ; zero (0) if `pattern.length == 0`. Annotations @SuppressWarnings:NestedAssignment, AssignmentToMethodParameter Exceptions IOException: when an error occurs accessing the input stream.

public static long search(final Reader reader, final char[] pattern, int[] table) throws IOException

Searches the given character stream for the given character pattern returning the zero-based offset from the initial stream position at which the first match is detected.

Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time.

Parameters

reader:Reader: in which to search
pattern:char[]: for which to search
table:int[]: computed from the pattern that optimizes the search If null, automatically computed.

Returns:long

zero-based offset of first match; -1 if reader == null || pattern == null or no match found, ; zero (0) if pattern.length == 0.

Annotations

@SuppressWarnings:NestedAssignment, AssignmentToMethodParameter

Exceptions

IOException:: when an error occurs accessing the input stream.

search back to summary

search	back to summary
public static long search(final Reader reader, final String pattern, int[] table) throws IOException Searches the given character stream for the given character pattern returning the zero-based offset from the initial stream position at which the first match is detected. Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time. Parameters reader:Reader in which to search pattern:String for which to search table:int[] computed from the pattern that optimizes the search If null, automatically computed. Returns:long zero-based offset of first match; -1 if `reader == null \|\| pattern == null` or no match found, ; zero (0) if `pattern.length() == 0`. Annotations @SuppressWarnings:NestedAssignment, AssignmentToMethodParameter Exceptions IOException: when an error occurs accessing the input stream.

public static long search(final Reader reader, final String pattern, int[] table) throws IOException

Searches the given character stream for the given character pattern returning the zero-based offset from the initial stream position at which the first match is detected.

Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time.

Parameters

reader:Reader: in which to search
pattern:String: for which to search
table:int[]: computed from the pattern that optimizes the search If null, automatically computed.

Returns:long

zero-based offset of first match; -1 if reader == null || pattern == null or no match found, ; zero (0) if pattern.length() == 0.

Annotations

@SuppressWarnings:NestedAssignment, AssignmentToMethodParameter

Exceptions

IOException:: when an error occurs accessing the input stream.

search back to summary

search	back to summary
public static int search(final byte[] source, final byte[] pattern, int[] table, final int start) Searches the given octet string for the given octet pattern returning the zero-based offset from given start position at which the first match is detected. Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time. Parameters source:byte[] array in which to search pattern:byte[] to be matched table:int[] computed from the pattern that optimizes the search If null, automatically computed. start:int position in source at which to start the search Returns:int zero-based offset of first match; -1 if `source == null \|\| pattern == null` or no match found, ; start if `pattern.length == 0 and start <= source.length`.

public static int search(final byte[] source, final byte[] pattern, int[] table, final int start)

Searches the given octet string for the given octet pattern returning the zero-based offset from given start position at which the first match is detected.

Note that the signature includes a slot for the table so that searches for a pattern can be performed multiple times without incurring the overhead of computing the table each time.

Parameters

source:byte[]: array in which to search
pattern:byte[]: to be matched
table:int[]: computed from the pattern that optimizes the search If null, automatically computed.
start:int: position in source at which to start the search

Returns:int

zero-based offset of first match; -1 if source == null || pattern == null or no match found, ; start if pattern.length == 0 and start <= source.length.

search back to summary

search	back to summary
public static int search(final char[] source, final char[] pattern, int[] table, final int start) Searches the given character array for the given character pattern returning the zero-based offset from given start position at which the first match is detected. Parameters source:char[] array in which to search pattern:char[] to be matched table:int[] computed from the pattern that optimizes the search If null, automatically computed. start:int position in source at which to start the search Returns:int zero-based offset of first match; -1 if `source == null \|\| pattern == null` or no match found, ; start if `pattern.length == 0 and start <= source.length`.

public static int search(final char[] source, final char[] pattern, int[] table, final int start)

Searches the given character array for the given character pattern returning the zero-based offset from given start position at which the first match is detected.

Parameters

source:char[]: array in which to search
pattern:char[]: to be matched
table:int[]: computed from the pattern that optimizes the search If null, automatically computed.
start:int: position in source at which to start the search

Returns:int

zero-based offset of first match; -1 if source == null || pattern == null or no match found, ; start if pattern.length == 0 and start <= source.length.

search back to summary

search	back to summary
public static int search(final String source, final String pattern, int[] table, final int start) Searches the given String object for the given character pattern returning the zero-based offset from given start position at which the first match is detected. Parameters source:String array to be searched pattern:String to be matched table:int[] computed from the pattern that optimizes the search start:int position in source at which to start the search Returns:int zero-based offset of first match; -1 if `source == null \|\| pattern == null` or no match found, ; start if `pattern.length == 0 and start <= source.length`.

public static int search(final String source, final String pattern, int[] table, final int start)

Searches the given String object for the given character pattern returning the zero-based offset from given start position at which the first match is detected.

Parameters

source:String: array to be searched
pattern:String: to be matched
table:int[]: computed from the pattern that optimizes the search
start:int: position in source at which to start the search

Returns:int

zero-based offset of first match; -1 if source == null || pattern == null or no match found, ; start if pattern.length == 0 and start <= source.length.

public Class KMPSearchAlgorithm

Constructor Summary

Method Summary

Constructor Detail

Method Detail