Package libsidutils.stringsearch
Klasse BNDM
java.lang.Object
libsidutils.stringsearch.StringSearch
libsidutils.stringsearch.BNDM
- Bekannte direkte Unterklassen:
BNDMWildcards
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 com.eaio.stringsearch.BoyerMooreHorspoolRaita and the com.eaio.stringsearch.BoyerMooreHorspool algorithms.
http:// www-igm.univ-mlv.fr/~raffinot/ftp/cpm98.ps.gz
http:// citeseer.nj.nec.com/navarro98bitparallel.html
This is one of the fastest algorithms, but it does not beat the com.eaio.stringsearch.BoyerMooreHorspoolRaita and the com.eaio.stringsearch.BoyerMooreHorspool algorithms.
Preprocessing: O(m) time
Searching : O(n/m) (best case)
O(n log|∑| m / m) (average)
O(mn) (worst case)
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
- Version:
- 1.2
- Autor:
- Johann Burkard
-
Konstruktorübersicht
Konstruktoren -
Methodenübersicht
Modifizierer und TypMethodeBeschreibungprivate intjavaSearchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed) processBytes(byte[] pattern) Pre-processing of the pattern.processChars(char[] pattern) Pre-processing of the pattern.intsearchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed) com.eaio.stringsearch.StringSearch#searchBytes(byte[], int, int, byte[], java.lang.Object)intsearchChars(char[] text, int textStart, int textEnd, char[] pattern, Object processed) com.eaio.stringsearch.StringSearch#searchChars(char[], int, int, char[], Object)Von Klasse geerbte Methoden libsidutils.stringsearch.StringSearch
createCharIntMap, createCharIntMap, equals, hashCode, index, searchBytes, searchBytes, searchBytes, searchBytes, searchBytes, searchChars, searchChars, searchChars, searchChars, searchChars, toString, toStringBuffer
-
Konstruktordetails
-
BNDM
public BNDM()Constructor for BNDM. Note that it is not required to create multiple instances.
-
-
Methodendetails
-
processBytes
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 anintarray. com.eaio.stringsearch.StringSearch#processBytes(byte[])- Angegeben von:
processBytesin KlasseStringSearch- Parameter:
pattern- thebytearray containing the pattern, may not benull- Gibt zurück:
- an Object
-
processChars
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 aCharIntMap. com.eaio.stringsearch.StringSearch#processChars(char[])- Angegeben von:
processCharsin KlasseStringSearch- Parameter:
pattern- achararray containing the pattern, may not benull- Gibt zurück:
- an Object
-
searchBytes
com.eaio.stringsearch.StringSearch#searchBytes(byte[], int, int, byte[], java.lang.Object)- Angegeben von:
searchBytesin KlasseStringSearch- Parameter:
text- text thebytearray containing the text, may not benulltextStart- 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 benullprocessed- an Object as returned fromStringSearch.processBytes(byte[]), may not benull- Gibt zurück:
- the position in the text or -1 if the pattern was not found
- Siehe auch:
-
javaSearchBytes
private int javaSearchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed) -
searchChars
com.eaio.stringsearch.StringSearch#searchChars(char[], int, int, char[], Object)- Angegeben von:
searchCharsin KlasseStringSearch- Parameter:
text- the String containing the text, may not benulltextStart- 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 benullprocessed- an Object as returned fromStringSearch.processChars(char[]), may not benull- Gibt zurück:
- the position in the text or -1 if the pattern was not found
-