|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.jaxfront.core.util.stringSearch.StringSearch
com.jaxfront.core.util.stringSearch.ShiftOr
public class ShiftOr
An implementation of the Shift-Or algorithm by Ricardo Baeza-Yates and
Gaston Gonnet as outlined in "A New Approach to Text Searching" (appeared in
Proceedings of the 12th International Conference on Research and
Development in Datum Retrieval). The Shift-Or algorithm is a
bit-parallel algorithm.
The Shift-Or algorithm is not the fastest and by itself slower than String's
indexOf
method. It's usefulness comes from it's ability to
support character classes and searching with errors at the same speed.
It's searchChars(char[], int, int, char[], Object)
method is
extremely slow in the Sun Java Virtual Machines. If possible, the
searchBytes(byte[], int, int, byte[], Object)
methods should be
preferred. Because the main loop is also used by the
com.eaio.stringsearch.ShiftOrWildcards
class, the implementation
cannot skip forward until the first character matches (as in the original
algorithm).
This implementation currently limited to at most 31 characters because Java
has no unsigned int
type. An implementation that used
long
has proved to take twice the amount of time.
Preprocessing: O(n + ∑) time Searching : O(mn / log n) (worst case and average)
com.eaio.stringsearch.ShiftOrWildcards
,
com.eaio.stringsearch.ShiftOrClasses
,
com.eaio.stringsearch.ShiftOrMismatches
Constructor Summary | |
---|---|
ShiftOr()
Constructor for ShiftOr. |
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 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, usesNative, usesReflection |
Methods inherited from class java.lang.Object |
---|
getClass, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public ShiftOr()
Method Detail |
---|
public java.lang.Object processBytes(byte[] pattern)
int
array.
processBytes
in class StringSearch
pattern
- the byte
array containing the pattern, may not
be null
com.eaio.stringsearch.StringSearch#processBytes(byte[])
public java.lang.Object processChars(char[] pattern)
CharIntMap
.
processChars
in class StringSearch
char[]
- the pattern
StringSearch.processChars(char[])
public int searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, java.lang.Object processed)
StringSearch
searchBytes
in class StringSearch
text
- text the byte
array containing the text, may
not be null
textStart
- at which position in the text the comparing should starttextEnd
- at which position in the text comparing should stoppattern
- the pattern to search for, may not be null
processed
- an Object as returned from StringSearch.processBytes(byte[])
, may
not be null
com.eaio.stringsearch.StringSearch#searchBytes(byte[], int, int,
byte[], java.lang.Object)
public int searchChars(char[] text, int textStart, int textEnd, char[] pattern, java.lang.Object processed)
StringSearch
searchChars
in class StringSearch
text
- the String containing the text, may not be null
textStart
- at which position in the text the comparing should starttextEnd
- at which position in the text comparing should stoppattern
- 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
com.eaio.stringsearch.StringSearch#searchChars(char[], int, int,
char[], Object)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |