Совпадение подстановочных строк

Каков наиболее эффективный алгоритм сопоставления строк подстановочных знаков? Я прошу только об идее, нет необходимости предоставлять фактический код.

Я думаю, что такой алгоритм может быть построен с отсортированными массивами суффиксов, что может привести к производительности O (log (n)).

Правильно ли я?

Отредактировано:

Я имею в виду такие шаблоны, как "A*B", "*sip*" или "A?B", где star означает любое количество символов и знак вопроса означает единственный символ.

Ответы

Ответ 1

Существует бумага, охватывающая самые быстрые варианты здесь http://swtch.com/~rsc/regexp/regexp1.html в частности, позволяет избежать наивных алгоритмов, которые становятся патологически медленными при использовании длинных шаблонов.

Он охватывает общие регулярные выражения, но вы можете ограничить свою реализацию подмножеством, которое вам нужно.

Ответ 2

Hm, я думаю, что здесь будут применяться обычные правила сопоставления шаблонов. Обычно, поскольку у вас есть поток данных и короткие шаблоны, вам не нужно будет внедрять что-то более эффективное, чем линейное. Тем не менее, чем дольше получается шаблон, тем больше места для оптимизации.

Какой шаблон вы имеете в виду? односимвольный подстановочный знак (например, . в регулярном выражении) или групповой символ с несколькими символами (например, .*)? Существуют ли ограничения? Какова ожидаемая длина шаблона, и есть ли у вас случайный или последовательный доступ к проверяемым данным?

Ответ 3

Я искал простой алгоритм сопоставления подстановочных знаков, который выполняется в полиномиальное время. Например. этот простой, но не работает в полиномиальное время, когда шаблон содержит много звезд (*): http://www.codeproject.com/Articles/188256/A-Simple-Wildcard-Matching-Function Ниже приведен код, который использует динамическое программирование для уменьшения сложности времени до O (n * m), где n - длина текста, а m - длина шаблона.

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

Ответ 4

Если ваш шаблон может содержать только * wild cards, то тривиальная реализация выполняется как можно быстрее. Главное, чтобы реализовать в этом случае, состоит в том, что вам нужно искать каждую карту только один раз (карта = сегмент между звездами).

Вот реализация (поддерживающая только * wild cards):

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

Ответ 5

Производительность зависит не только от длины строки поиска, но и от числа (и типа) подстановочных знаков в строке запроса. Если вам разрешено использовать *, который соответствует любому количеству символов, вплоть до всего документа и может содержать любое количество звезд, это ограничит доступ к тому, что можно получить.

Если вы можете определить совпадение некоторой строки foo в O (f (n)) времени, тогда запрос foo_0*foo_1*foo_2*...*foo_m будет принимать время O (m * f (n)), где m - число * подстановочные знаки.

Ответ 6

В зависимости от подстановочного "языка" я (возможно) просто напишу компилятор wildcard- > regexp и использую (обычно предоставляемый) механизм regexp для фактического соответствия. Это немного лениво, но если там не будет проблемы с производительностью, это будет достаточно быстро.

Ответ 7

Вы можете преобразовать ваш шаблонный запрос в регулярное выражение и использовать его для соответствия; RE всегда может быть преобразовано в DFA (дискретный конечный автомат), и они эффективны (время линии) и небольшая константа.