High-Speed-String-Matching-Algorithmen

Question

Ich bin im Grunde Benchmark einige High-Speed-String-Matching-Algorithmen, stieß ich auf ein paar.

1. rückwärts nicht-determinis DAWG (gerichtetes azyklisches Wortgraphen) Matching-Algorithmus von Gonzalo Navarro und Mathieu Raffinot. Siehe "Ein Bit-Parallel-Ansatz zu Suffix Automata: Fast Erweiterte String Matching"

2. Horspool die verbesserte Version des Boyer-Moore String Suchalgorithmus. Siehe "Praktische schnelle Suche in strings"

3. Umschalt-Oder-Algorithmus mit Mismatches

4. KMP

Gibt es andere bessere High-Speed-String-Matching-Algorithmen ich versuchen kann?

Edit: Es gibt einen weiteren thread in ähnlichen Linien, die auch gute Referenzen hat

Answer 1

können Sie auch versuchen,

• Z Algorithm: In gewisser Weise sogar sauberere als KMP
• Aho Corasick: Trie basiert und ursprünglich für fgrep verwendet
• Rabin Karp: Hash basiert

Answer 2

Zwei-Wege-String-Matching ist meines Wissens der beste Allzweckalgorithmus für String-Matching. Es hat eine lineare Worst-Case-Komplexität, verwendet konstanten Speicherplatz und führt nicht zu viel mehr als nötig zurück. Und die Theorie dahinter ist sehr nett.

Wenn Sie wissen, dass Ihre Benutzer keine Idioten sind, gewinnt naives, für Ihre Architektur optimiertes String-Matching für kurze "Nadeln", während eine Boyer-Moore-Variante das sublineare Ding für lange "Nadeln" beginnt. Der naive String-Matching hat jedoch einen quadratischen Worst-Case, und Boyer-Moore kann alle Zeichen in der Eingabe untersuchen. Die zusätzlichen Tabellen, die zum Behandeln von Fehlanpassungen benötigt werden, tragen tatsächlich eine überraschend schwerwiegende Strafe gegenüber dem Zwei-Wege-Zeichenfolgenabgleich.

Answer 3

import java.util.Scanner; 

public class StringMatch { 

static int temp,i=0,j=0; static boolean flag=true,matcher=false; 

    static String str=null,mstr=null;static char astr[],amstr[]; 

     static void getter(){ 
     Scanner sc = new Scanner(System.in); 
     str = sc.nextLine(); 
     //String str="today is Monday"; 
     astr=str.toCharArray(); 
     mstr = sc.nextLine(); 
     //String mstr="is"; 
     amstr=mstr.toCharArray(); 
    } 
    static void stringMatch(){ 
     while(i<astr.length){ 
      if(astr[i]==amstr[j]){ 
      while((j!=amstr.length)&&flag){temp=i; 
       if(astr[i]!=amstr[j]) {flag=false;matcher=false;} 
       else{matcher=true;} 
       i++;j++; 
       //System.out.println(i+"\t"+j); 
      }if(matcher==true)break;i=temp;}i++;j=0;flag=true; 

     } 
     if(matcher==true) {System.out.println("true");} 
     else {System.out.println("false");} 
    } 
    public static void main(String[] args) { 

    StringMatch.getter(); 
    StringMatch.stringMatch(); 

    } 
}