org.jscience.linguistics.search
Class ShiftOrMismatches

java.lang.Object
  org.jscience.linguistics.search.StringSearch
      org.jscience.linguistics.search.MismatchSearch
          org.jscience.linguistics.search.ShiftOrMismatches

public class ShiftOrMismatches
extends MismatchSearch

An implementation of the Shift-Or algorithm with mismatches. Note that the pattern length may not be larger than 31 / ⌈ log₂ (k + 1) ⌉.

Editing distance (k)	Maximum pattern length
0	31
1	15
2-3	10
4-5	7

This algorithm is slower than ShiftOr. In future versions of this library, faster alternatives are likely to be added.

 Preprocessing: O(3n + ∑) time
 

 Searching    : O(mn / log n) (worst case and average)
 

See Also:

processBytes(byte[],int), processChars(char[],int), ShiftOr

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

ShiftOrMismatches()
Constructor for ShiftOrMismatches.

Method Summary

java.lang.Object	processBytes(byte[] pattern, int k) DOCUMENT ME!
java.lang.Object	processChars(char[] pattern, int k) DOCUMENT ME!
int[]	searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, java.lang.Object processed, int k) 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, int k) Finder for the given pattern in the text, starting at textStart and comparing to at most textEnd, allowing k errors.
boolean	usesNative() This algorithm is currently not using the native library.

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

processBytes, processChars, processString, searchBytes, searchBytes, searchBytes, searchBytes, searchBytes, searchBytes, searchChars, searchChars, searchChars, searchChars, searchChars, searchChars, searchString, searchString, searchString, searchString, searchString, searchString

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, usesReflection

Methods inherited from class java.lang.Object

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

Constructor Detail

ShiftOrMismatches

public ShiftOrMismatches()

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

Method Detail

processBytes

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

DOCUMENT ME!

Specified by:

processBytes in class MismatchSearch

Parameters:

pattern - DOCUMENT ME!

k - DOCUMENT ME!

Returns:

DOCUMENT ME!

Throws:

java.lang.IllegalArgumentException - if the pattern length is larger than 31 / ⌈ log₂ (k + 1) ⌉

See Also:

MismatchSearch.processBytes(byte[], int)

processChars

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

DOCUMENT ME!

Specified by:

processChars in class MismatchSearch

Parameters:

pattern - DOCUMENT ME!

k - DOCUMENT ME!

Returns:

DOCUMENT ME!

Throws:

java.lang.IllegalArgumentException - if the pattern length is larger than 31 / ⌈ log₂ (k + 1) ⌉

See Also:

MismatchSearch.processChars(char[], int)

searchBytes

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

Description copied from class: MismatchSearch

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 MismatchSearch

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 MismatchSearch.processBytes(byte[], int), may not be null

k - the editing distance

Returns:

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

See Also:

MismatchSearch.searchBytes(byte[], int,int,byte[],Object,int)

searchChars

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

Description copied from class: MismatchSearch

Finder for the given pattern in the text, starting at textStart and comparing to at most textEnd, allowing k errors.

Specified by:

searchChars in class MismatchSearch

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 MismatchSearch.processChars(char[], int) or MismatchSearch.processString(String,int), may not be null

k - the maximum number of mismatches (the editing distance)

Returns:

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

See Also:

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

usesNative

public boolean usesNative()

This algorithm is currently not using the native library. This method therefore always returns false.

Overrides:

usesNative in class StringSearch

Returns:

true or false

See Also:

StringSearch.usesNative()