Cadena comodín coincidente

Question

¿Cuál es el algoritmo de coincidencia de cadena comodín más eficiente? Solo estoy preguntando sobre una idea, no es necesario proporcionar un código real.

Estoy pensando que dicho algoritmo se puede construir con matrices de sufijo ordenadas, que pueden producir el rendimiento de O (log (n)).

¿Es correcto?

Editado:

me refiero a patrones como "A*B", "*sip*" o "A?B", donde la estrella significa cualquier número de símbolos y signo de interrogación significa solo símbolo.

Answer 1

Hm, creo que las reglas de coincidencia de patrones normales se aplicarían aquí. Por lo general, dado que tiene una secuencia de datos y patrones cortos, no necesitaría implementar algo más eficiente que lineal. Sin embargo, cuanto más largo sea el patrón, más espacio habrá para la optimización.

¿Qué tipo de comodín tienes en mente? un comodín de un carácter (por ejemplo, . en expresiones regulares), o un comodín de caracteres múltiples (por ejemplo, .*)? ¿Hay limitaciones? ¿Cuál es la duración esperada del patrón y tiene acceso aleatorio o en serie a los datos que se verificarán?

Answer 2

El rendimiento no solo dependerá de la longitud de la cadena para buscar sino también del número (y tipo) de comodines en la cadena de consulta. Si tiene permiso para usar un * que coincida con cualquier número de caracteres, hasta e incluyendo el documento completo, y puede tener cualquier número de estrellas, esto limitará lo que se puede obtener.

Si puede determinar un partido de alguna cadena foo en O (f (n)), entonces la consulta foo_0*foo_1*foo_2*...*foo_m tomará un tiempo O (m * f (n)), donde m es el número de * comodines.

Answer 3

Dependiendo del "idioma" del comodín, probablemente (simplemente) escribiría un compilador regexp comodín-> y usaría el motor regexp (comúnmente provisto) para hacer la coincidencia real. Es un poco vago, pero a menos que haya un problema de rendimiento real haciéndolo de esa manera, sería lo suficientemente rápido.

Answer 4

Puede convertir su consulta comodín en una expresión regular y usar eso para que coincida; un RE siempre se puede transformar en un DFA (autómata finito discreto) y esos son eficientes (tiempo de lineair) y una pequeña constante.

Answer 5

No es un papel que cubre las opciones más rápidas aquí http://swtch.com/~rsc/regexp/regexp1.html en particular, permite a evitar algoritmos ingenuos que se convierten en patológicamente lento cuando se utilizan patrones de largo.

Cubre expresiones regulares genéricas, pero puede limitar su implementación al subconjunto que necesita.

Answer 6

O (n log m) es correcto. Ver http://www.cs.bris.ac.uk/Publications/Papers/2000602.pdf

Espero que esto ayude ...

Answer 7

que estaba buscando un simple algoritmo de coincidencia de comodines que se ejecuta en tiempo polinómico. P.ej. este es simple, pero no se ejecuta en tiempo polinomial cuando el patrón contiene muchas estrellas (*): http://www.codeproject.com/Articles/188256/A-Simple-Wildcard-Matching-Function A continuación se muestra el código que usa programación dinámica para reducir la complejidad de tiempo a O (n * m) donde n es la longitud del texto y m es la longitud del patrón.

#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

Si su patrón puede contener sólo * comodines, entonces la aplicación trivial es lo más rápido posible. Lo más importante a tener en cuenta en este caso, es que solo necesita buscar cada tarjeta una vez (tarjeta = segmento entre estrellas).

Aquí es una aplicación (sólo apoyar * comodines):

#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; 
}