Klasse BNDM

Bekannte direkte Unterklassen:
BNDMWildcards

public class BNDM extends 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 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.

 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
  • Konstruktordetails

    • BNDM

      public BNDM()
      Constructor for BNDM. Note that it is not required to create multiple instances.
  • Methodendetails

    • processBytes

      public Object processBytes(byte[] pattern)
      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 an int array. com.eaio.stringsearch.StringSearch#processBytes(byte[])
      Angegeben von:
      processBytes in Klasse StringSearch
      Parameter:
      pattern - the byte array containing the pattern, may not be null
      Gibt zurück:
      an Object
    • processChars

      public Object processChars(char[] pattern)
      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 a CharIntMap. com.eaio.stringsearch.StringSearch#processChars(char[])
      Angegeben von:
      processChars in Klasse StringSearch
      Parameter:
      pattern - a char array containing the pattern, may not be null
      Gibt zurück:
      an Object
    • searchBytes

      public int searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed)
      com.eaio.stringsearch.StringSearch#searchBytes(byte[], int, int, byte[], java.lang.Object)
      Angegeben von:
      searchBytes in Klasse StringSearch
      Parameter:
      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 StringSearch.processBytes(byte[]), may not be null
      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

      public int searchChars(char[] text, int textStart, int textEnd, char[] pattern, Object processed)
      com.eaio.stringsearch.StringSearch#searchChars(char[], int, int, char[], Object)
      Angegeben von:
      searchChars in Klasse StringSearch
      Parameter:
      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 StringSearch.processChars(char[]), may not be null
      Gibt zurück:
      the position in the text or -1 if the pattern was not found