com.jaxfront.core.util.stringSearch
Class ShiftOrMismatches

java.lang.Object
  extended by com.jaxfront.core.util.stringSearch.StringSearch
      extended by com.jaxfront.core.util.stringSearch.MismatchSearch
          extended by com.jaxfront.core.util.stringSearch.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 / ⌈ log2 (k + 1) ⌉.

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


This algorithm is slower than com.eaio.stringsearch.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)
 

Version:
1.2
Author:
Johann Burkard
See Also:
processBytes(byte[], int), processChars(char[], int), com.eaio.stringsearch.ShiftOr

Constructor Summary
ShiftOrMismatches()
          Constructor for ShiftOrMismatches.
 
Method Summary
 java.lang.Object processBytes(byte[] pattern, int k)
          Pre-processes the pattern, allowing k errors.
 java.lang.Object processChars(char[] pattern, int k)
          Pre-processes a char array, allowing k errors.
 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 com.jaxfront.core.util.stringSearch.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 com.jaxfront.core.util.stringSearch.StringSearch
equals, getAllOccurences, hashCode, 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
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)
Description copied from class: MismatchSearch
Pre-processes the pattern, allowing k errors.

Specified by:
processBytes in class MismatchSearch
Parameters:
pattern - the byte array containing the pattern, may not be null
k - the editing distance
Returns:
an Object
Throws:
java.lang.IllegalArgumentException - if the pattern length is larger than 31 / ⌈ log2 (k + 1) ⌉
See Also:
com.eaio.stringsearch.MismatchSearch#processBytes(byte[], int)

processChars

public java.lang.Object processChars(char[] pattern,
                                     int k)
Description copied from class: MismatchSearch
Pre-processes a char array, allowing k errors.

Specified by:
processChars in class MismatchSearch
Parameters:
pattern - a char array containing the pattern, may not be null
k - the editing distance
Returns:
an Object
Throws:
java.lang.IllegalArgumentException - if the pattern length is larger than 31 / ⌈ log2 (k + 1) ⌉
See Also:
com.eaio.stringsearch.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:
com.eaio.stringsearch.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:
com.eaio.stringsearch.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:
com.eaio.stringsearch.StringSearch#usesNative()