Wildcard-String-Übereinstimmung

Question

Was ist der effizienteste Wildcard-String-Matching-Algorithmus? Ich frage nur nach einer Idee, es ist nicht notwendig, tatsächlichen Code zur Verfügung zu stellen.

Ich denke, dass solcher Algorithmus mit sortierten Suffix-Arrays gebaut werden kann, die eine Leistung von O (log (n)) ergeben kann.

Bin ich richtig?

Edited:

ich meine Muster wie "A*B", "*sip*" oder "A?B" wo Stern bedeutet eine beliebige Anzahl von Symbolen und Fragezeichen bedeutet einzelnes Symbol.

Answer 1

Hm, ich denke, dass normale Mustervergleichsregeln hier gelten würden. Da Sie einen Datenstrom und kurze Muster haben, müssen Sie normalerweise nicht etwas effizienteres als lineares implementieren. Je länger das Muster jedoch wird, desto mehr Raum ist für die Optimierung vorhanden.

Welche Art von Wildcard haben Sie im Sinn? ein Ein-Zeichen-Platzhalter (z. B. . in Regex) oder ein Mehrfachzeichen-Platzhalter (z. B. .*)? Gibt es Einschränkungen? Was ist die erwartete Musterlänge, und haben Sie zufälligen oder seriellen Zugriff auf die zu überprüfenden Daten?

Answer 2

Die Leistung hängt nicht nur von der Länge der zu suchenden Zeichenfolge, sondern auch von der Anzahl (und dem Typ) der Platzhalter in der Abfragezeichenfolge ab. Wenn Sie eine * verwenden dürfen, die einer beliebigen Anzahl von Zeichen entspricht, bis einschließlich des gesamten Dokuments, und Sie können eine beliebige Anzahl von Sternen haben, werden dadurch einige Grenzen gesetzt, was zu bekommen ist.

Wenn Sie ein Spiel einige Zeichenfolge foo in O bestimmen kann (f (n)) Zeit, dann die Abfrage foo_0*foo_1*foo_2*...*foo_m nehmen O (m * f (n)) Zeit, wobei m die Anzahl der * Platzhalter ist.

Answer 3

Abhängig von der Wildcard "Sprache", würde ich (wahrscheinlich) einfach einen Wildcard-> Regexp-Compiler schreiben und die (häufig zur Verfügung gestellte) Regexp-Engine verwenden, um den tatsächlichen Abgleich durchzuführen. Es ist ein bisschen faul, aber wenn es kein tatsächliches Leistungsproblem gibt, wäre es schnell genug.

Answer 4

Sie können Ihre Platzhalterabfrage in einen regulären Ausdruck konvertieren und diesen zum Abgleich verwenden; ein RE kann immer in einen DFA (diskreter endlicher Automat) umgewandelt werden, und diese sind effizient (Lineairzeit) und eine kleine Konstante.

Answer 5

Es ist ein Papier Abdecken der schnellsten Möglichkeiten hier http://swtch.com/~rsc/regexp/regexp1.html insbesondere ermöglicht es Ihnen, naiven Algorithmen zu vermeiden, die pathologisch langsam werden, wenn lange Muster verwendet werden.

Es deckt allgemeine reguläre Ausdrücke ab, aber Sie können Ihre Implementierung auf die von Ihnen benötigte Untergruppe beschränken.

Answer 6

O (n log m) ist korrekt. Siehe http://www.cs.bris.ac.uk/Publications/Papers/2000602.pdf

Hope this helps ...

Answer 7

Ich war auf der Suche nach einem einfachen Wildcard-Matching-Algorithmus, der in Polynomialzeit läuft. Z.B. dieser ist einfach, aber läuft nicht in polynomieller Zeit, wenn das Muster viele Sterne enthält (*): http://www.codeproject.com/Articles/188256/A-Simple-Wildcard-Matching-Function Unten ist der Code, der dynamische Programmierung verwendet, um die Zeitkomplexität auf O (n * m) zu reduzieren, wobei n die Länge ist des Textes und m ist die Länge des Musters.

#include <string> 
#include <vector> 
#include <algorithm> 
using namespace std; 

const int UNKNOWN = -1; 
const int NOMATCH = 0; 
const int MATCHES = 1; 

class Wildcard { 
    string _text; 
    string _pattern; 
    vector<vector<int>> _mf; 
    int F(int n, int m) { 
     if (_mf[n][m] >= 0) return _mf[n][m]; 
     if (n == 0 && m == 0) { 
      _mf[n][m] = MATCHES; 
      return _mf[n][m]; 
     } 
     if (n > 0 && m == 0) { 
      _mf[n][m] = NOMATCH; 
      return _mf[n][m]; 
     } 
     // m > 0 
     int ans = NOMATCH; 
     if (_pattern[m - 1] == '*') { 
      ans = max(ans, F(n, m-1)); 
      if (n > 0) { 
       ans = max(ans, F(n - 1, m)); 
      } 
     } 
     if (n > 0) { 
      if (_pattern[m - 1] == '?' || _pattern[m - 1] == _text[n - 1]) { 
       ans = max(ans, F(n - 1, m - 1)); 
      } 
     } 
     _mf[n][m] = ans; 
     return _mf[n][m]; 
    } 
public: 
    bool match(string text, string pattern) { 
     _text = text; 
     _pattern = pattern; 
     _mf.clear(); 
     for (int i = 0; i <= _text.size(); i++) { 
      _mf.push_back(vector<int>()); 
      for (int j = 0; j <= _pattern.size(); j++) { 
       _mf[i].push_back(UNKNOWN); // not calculated 
      } 
     } 
     int ans = F(_text.size(), _pattern.size()); 
     return ans == MATCHES; 
    } 
}; 

Answer 8

Wenn Ihr Muster nur * Wildcards enthalten kann, dann ist die triviale Implementierung ist so schnell wie möglich. In diesem Fall müssen Sie nur einmal nach jeder Karte suchen (Karte = Segment zwischen den Sternen). Hier

ist eine Implementierung (unterstützt nur * Wildcards):

#include <cstddef> 
#include <cstring> 
#include <algorithm> 
#include <string> 
#include <vector> 
#include <iostream> 

using namespace std; 

class wildcard_pattern { 
public: 
    explicit wildcard_pattern(const string& text); 

    bool match(const char* begin, const char* end) const; 

    bool match(const char* c_str) const; 

private: 
    string m_text; 

    struct card { 
     size_t m_offset, m_size; 
     card(size_t begin, size_t end); 
    }; 

    // Must contain at least one card. The first, and the last card 
    // may be empty strings. All other cards must be non-empty. If 
    // there is exactly one card, the pattern matches a string if, and 
    // only if the string is equal to the card. Otherwise, the first 
    // card must be a prefix of the string, and the last card must be 
    // a suffix. 
    vector<card> m_cards; 
}; 


wildcard_pattern::wildcard_pattern(const string& text): 
    m_text(text) 
{ 
    size_t pos = m_text.find('*'); 
    if (pos == string::npos) { 
     m_cards.push_back(card(0, m_text.size())); 
     return; 
    } 
    m_cards.push_back(card(0, pos)); 
    ++pos; 
    for (;;) { 
     size_t pos_2 = m_text.find('*', pos); 
     if (pos_2 == string::npos) 
      break; 
     if (pos_2 != pos) 
      m_cards.push_back(card(pos, pos_2)); 
     pos = pos_2 + 1; 
    } 
    m_cards.push_back(card(pos, m_text.size())); 
} 

bool wildcard_pattern::match(const char* begin, const char* end) const 
{ 
    const char* begin_2 = begin; 
    const char* end_2 = end; 

    size_t num_cards = m_cards.size(); 
    typedef string::const_iterator str_iter; 

    // Check anchored prefix card 
    { 
     const card& card = m_cards.front(); 
     if (size_t(end_2 - begin_2) < card.m_size) 
      return false; 
     str_iter card_begin = m_text.begin() + card.m_offset; 
     if (!equal(begin_2, begin_2 + card.m_size, card_begin)) 
      return false; 
     begin_2 += card.m_size; 
    } 

    if (num_cards == 1) 
     return begin_2 == end_2; 

    // Check anchored suffix card 
    { 
     const card& card = m_cards.back(); 
     if (size_t(end_2 - begin_2) < card.m_size) 
      return false; 
     str_iter card_begin = m_text.begin() + card.m_offset; 
     if (!equal(end_2 - card.m_size, end_2, card_begin)) 
      return false; 
     end_2 -= card.m_size; 
    } 

    // Check unanchored infix cards 
    for (size_t i = 1; i != num_cards-1; ++i) { 
     const card& card = m_cards[i]; 
     str_iter card_begin = m_text.begin() + card.m_offset; 
     str_iter card_end = card_begin + card.m_size; 
     begin_2 = search(begin_2, end_2, card_begin, card_end); 
     if (begin_2 == end_2) 
      return false; 
     begin_2 += card.m_size; 
    } 

    return true; 
} 

inline bool wildcard_pattern::match(const char* c_str) const 
{ 
    const char* begin = c_str; 
    const char* end = begin + strlen(c_str); 
    return match(begin, end); 
} 

inline wildcard_pattern::card::card(size_t begin, size_t end) 
{ 
    m_offset = begin; 
    m_size = end - begin; 
} 


int main(int, const char* argv[]) 
{ 
    wildcard_pattern pat(argv[1]); 
    cout << pat.match(argv[2]) << endl; 
}