org.jscience.linguistics.search
Class BNDM

java.lang.Object
  org.jscience.linguistics.search.StringSearch
      org.jscience.linguistics.search.BNDM

Direct Known Subclasses:

BNDMWildcards

public class BNDM
extends StringSearch

An implementation of the Backwards Non-deterministic Dawg (Directed acyclic word graph) Matching algorithm by Gonzalo Navarro and Mathieu Raffinot. See "A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching" (appeared in Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching, 1998).

This is one of the fastest algorithms, but it does not beat the BoyerMooreHorspoolRaita and the BoyerMooreHorspool algorithms.

Preprocessing: O(m) time
Searching    : O(n/m) (best case)
                O(n log|∑| m / m) (average)
                O(mn) (worst case)

See Also:

http://www.dcc.uchile.cl/~gnavarro/ps/cpm98.ps.gz , http://www-igm.univ-mlv.fr/~raffinot/ftp/cpm98.ps.gz , http://citeseer.nj.nec.com/navarro98bitparallel.html

Nested Class Summary

Nested classes/interfaces inherited from class org.jscience.linguistics.search.StringSearch

StringSearch.Dispatch, StringSearch.ReflectionDispatch

Field Summary

Fields inherited from class org.jscience.linguistics.search.StringSearch

activeDispatch, useNative

Constructor Summary

BNDM()
Constructor for BNDM.

Method Summary

java.lang.Object	processBytes(byte[] pattern) Pre-processing of the pattern.
java.lang.Object	processChars(char[] pattern) Pre-processing of the pattern.
int	searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, java.lang.Object processed) Returns the position in the text at which the pattern was found.
int	searchChars(char[] text, int textStart, int textEnd, char[] pattern, java.lang.Object processed) Returns the index of the pattern in the text using the pre-processed Object.

Methods inherited from class org.jscience.linguistics.search.StringSearch

createCharIntMap, createCharIntMap, equals, hashCode, index, processString, searchBytes, searchBytes, searchBytes, searchBytes, searchBytes, searchChars, searchChars, searchChars, searchChars, searchChars, searchString, searchString, searchString, searchString, searchString, searchString, toString, toStringBuffer, usesNative, usesReflection

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

BNDM

public BNDM()

Constructor for BNDM. Note that it is not required to create multiple instances.

Method Detail

processBytes

public java.lang.Object processBytes(byte[] pattern)

Pre-processing of the pattern. The pattern may not exceed 32 bytes in length. If it does, only it's first 32 bytes are processed which might lead to unexpected results. Returns an int array.

Specified by:

processBytes in class StringSearch

Parameters:

pattern - the byte array containing the pattern, may not be null

Returns:

an Object

See Also:

StringSearch.processBytes(byte[])

processChars

public java.lang.Object processChars(char[] pattern)

Pre-processing of the pattern. The pattern may not exceed 32 bytes in length. If it does, only it's first 32 bytes are processed which might lead to unexpected results. Returns a CharIntMap.

Specified by:

processChars in class StringSearch

Parameters:

pattern - a char array containing the pattern, may not be null

Returns:

an Object

See Also:

StringSearch.processChars(char[])

searchBytes

public int searchBytes(byte[] text,
                       int textStart,
                       int textEnd,
                       byte[] pattern,
                       java.lang.Object processed)

Description copied from class: StringSearch

Returns the position in the text at which the pattern was found. Returns -1 if the pattern was not found.

Specified by:

searchBytes in class StringSearch

Parameters:

text - text the byte array containing the text, may not be null

textStart - at which position in the text the comparing should start

textEnd - at which position in the text comparing should stop

pattern - the pattern to search for, may not be null

processed - an Object as returned from StringSearch.processBytes(byte[]), may not be null

Returns:

the position in the text or -1 if the pattern was not found

See Also:

StringSearch.searchBytes(byte[], int,int,byte[],java.lang.Object)

searchChars

public int searchChars(char[] text,
                       int textStart,
                       int textEnd,
                       char[] pattern,
                       java.lang.Object processed)

Description copied from class: StringSearch

Returns the index of the pattern in the text using the pre-processed Object. Returns -1 if the pattern was not found.

Specified by:

searchChars in class StringSearch

Parameters:

text - the String containing the text, may not be null

textStart - at which position in the text the comparing should start

textEnd - at which position in the text comparing should stop

pattern - the pattern to search for, may not be null

processed - an Object as returned from StringSearch.processChars(char[]) or StringSearch.processString(String), may not be null

Returns:

the position in the text or -1 if the pattern was not found

See Also:

StringSearch.searchChars(char[], int,int,char[],Object)