BNDM.java
/*
* BNDM.java
*
* Created on 21.10.2003
*
* eaio: StringSearch - high-performance pattern matching algorithms in Java
* Copyright (c) 2003, 2004 Johann Burkard (jb@eaio.com) http://eaio.com
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*
*/
package libsidutils.stringsearch;
/**
* 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 <em>Proceedings of the 9th Annual Symposium on Combinatorial
* Pattern Matching, 1998</em>). <br>
* <br>
* This is one of the fastest algorithms, but it does not beat the
* com.eaio.stringsearch.BoyerMooreHorspoolRaita and the
* com.eaio.stringsearch.BoyerMooreHorspool algorithms. <br>
* <br>
*
* <pre>
* Preprocessing: O(m) time
*
* Searching : O(n/m) (best case)
* O(n log|∑| m / m) (average)
* O(mn) (worst case)
* </pre>
*
* <a href="http://www.dcc.uchile.cl/~gnavarro/ps/cpm98.ps.gz"> http://www.
* dcc.uchile.cl/~gnavarro/ps/cpm98.ps.gz </a><br>
* <a href="http://www-igm.univ-mlv.fr/~raffinot/ftp/cpm98.ps.gz"> http://
* www-igm.univ-mlv.fr/~raffinot/ftp/cpm98.ps.gz </a><br>
* <a href="http://citeseer.nj.nec.com/navarro98bitparallel.html"> http://
* citeseer.nj.nec.com/navarro98bitparallel.html </a><br>
*
* @author <a href="mailto:jb@eaio.de">Johann Burkard</a>
* @version 1.2
*/
public class BNDM extends StringSearch {
/**
* Constructor for BNDM. Note that it is not required to create multiple
* instances.
*/
public BNDM() {
}
/**
* Pre-processing of the pattern. The pattern may not exceed 32 bytes in length.
* If it does, <b>only its first 32 bytes are processed,</b> which might lead to
* unexpected results. Returns an <code>int</code> array.
* <p>
* com.eaio.stringsearch.StringSearch#processBytes(byte[])
*/
@Override
public Object processBytes(byte[] pattern) {
int end = Math.min(pattern.length, 32);
int[] b = new int[256];
int j = 1;
for (int i = end - 1; i >= 0; --i, j <<= 1) {
b[index(pattern[i])] |= j;
}
return b;
}
/**
* Pre-processing of the pattern. The pattern may not exceed 32 bytes in length.
* If it does, <b>only its first 32 bytes are processed,</b> which might lead to
* unexpected results. Returns a {@link CharIntMap}.
* <p>
* com.eaio.stringsearch.StringSearch#processChars(char[])
*/
@Override
public Object processChars(char[] pattern) {
int end = Math.min(pattern.length, 32);
CharIntMap b = createCharIntMap(pattern);
int j = 1;
for (int i = end - 1; i >= 0; --i, j <<= 1) {
b.set(pattern[i], b.get(pattern[i]) | j);
}
return b;
}
/**
* com.eaio.stringsearch.StringSearch#searchBytes(byte[], int, int, byte[],
* java.lang.Object)
*/
@Override
public int searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed) {
/* comment:start */
return javaSearchBytes(text, textStart, textEnd, pattern, processed);
}
private int javaSearchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed) {
/* comment:end */
int[] b = (int[]) processed;
int d, j, pos, last;
pos = textStart;
while (pos <= textEnd - pattern.length) {
j = pattern.length - 1;
last = pattern.length;
d = -1;
while (d != 0) {
d &= b[index(text[pos + j])];
if (d != 0) {
if (j == 0) {
return pos;
}
last = j;
}
--j;
d <<= 1;
}
pos += last;
}
return -1;
}
/**
* com.eaio.stringsearch.StringSearch#searchChars(char[], int, int, char[],
* Object)
*/
@Override
public int searchChars(char[] text, int textStart, int textEnd, char[] pattern, Object processed) {
CharIntMap b = (CharIntMap) processed;
int d, j, pos, last;
pos = textStart;
while (pos <= textEnd - pattern.length) {
j = pattern.length - 1;
last = pattern.length;
d = -1;
while (d != 0) {
d &= b.get(text[pos + j]);
if (d != 0) {
if (j == 0) {
return pos;
}
last = j;
}
--j;
d <<= 1;
}
pos += last;
}
return -1;
}
}