org.jscience.linguistics.search
Class BoyerMooreHorspoolRaita

java.lang.Object
  extended by org.jscience.linguistics.search.StringSearch
      extended by org.jscience.linguistics.search.BoyerMooreHorspool
          extended by org.jscience.linguistics.search.BoyerMooreHorspoolRaita

public class BoyerMooreHorspoolRaita
extends BoyerMooreHorspool

An implementation of Raita's enhancement to the Boyer-Moore-Horspool String searching algorithm. See "Tuning the Boyer-Moore-Horspool string searching algorithm" (appeared in Software - Practice & Experience, 22(10):879-884).

This algorithm is slightly faster than the BoyerMooreHorspool algorithm for the searchChars and searchString methods. It's searchBytes methods are slightly slower.

 Preprocessing: O(m + ∑) time
 

Processing : O(mn) worst case

See Also:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol22/issue10/spe787tr.pdf


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
BoyerMooreHorspoolRaita()
          Constructor for BoyerMooreHorspoolRaita.
 
Method Summary
 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.BoyerMooreHorspool
processBytes, processChars
 
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

BoyerMooreHorspoolRaita

public BoyerMooreHorspoolRaita()
Constructor for BoyerMooreHorspoolRaita. Note that it is not required to create multiple instances.

Method Detail

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.

Overrides:
searchBytes in class BoyerMooreHorspool
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.

Overrides:
searchChars in class BoyerMooreHorspool
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)