Каков наиболее эффективный алгоритм сопоставления строк подстановочных знаков? Я прошу только об идее, нет необходимости предоставлять фактический код.
Я думаю, что такой алгоритм может быть построен с отсортированными массивами суффиксов, что может привести к производительности O (log (n)).
Правильно ли я?
Отредактировано:
Я имею в виду такие шаблоны, как "A*B", "*sip*" или "A?B", где star означает любое количество символов и знак вопроса означает единственный символ.
Существует бумага, охватывающая самые быстрые варианты здесь http://swtch.com/~rsc/regexp/regexp1.html в частности, позволяет избежать наивных алгоритмов, которые становятся патологически медленными при использовании длинных шаблонов.
Он охватывает общие регулярные выражения, но вы можете ограничить свою реализацию подмножеством, которое вам нужно.
Hm, я думаю, что здесь будут применяться обычные правила сопоставления шаблонов. Обычно, поскольку у вас есть поток данных и короткие шаблоны, вам не нужно будет внедрять что-то более эффективное, чем линейное. Тем не менее, чем дольше получается шаблон, тем больше места для оптимизации.
Какой шаблон вы имеете в виду? односимвольный подстановочный знак (например, . в регулярном выражении) или групповой символ с несколькими символами (например, .*)? Существуют ли ограничения? Какова ожидаемая длина шаблона, и есть ли у вас случайный или последовательный доступ к проверяемым данным?
Я искал простой алгоритм сопоставления подстановочных знаков, который выполняется в полиномиальное время. Например. этот простой, но не работает в полиномиальное время, когда шаблон содержит много звезд (*): 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;
}
};
Если ваш шаблон может содержать только * 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;
}
Производительность зависит не только от длины строки поиска, но и от числа (и типа) подстановочных знаков в строке запроса. Если вам разрешено использовать *, который соответствует любому количеству символов, вплоть до всего документа и может содержать любое количество звезд, это ограничит доступ к тому, что можно получить.
Если вы можете определить совпадение некоторой строки foo в O (f (n)) времени, тогда запрос foo_0*foo_1*foo_2*...*foo_m будет принимать время O (m * f (n)), где m - число * подстановочные знаки.
В зависимости от подстановочного "языка" я (возможно) просто напишу компилятор wildcard- > regexp и использую (обычно предоставляемый) механизм regexp для фактического соответствия. Это немного лениво, но если там не будет проблемы с производительностью, это будет достаточно быстро.
Вы можете преобразовать ваш шаблонный запрос в регулярное выражение и использовать его для соответствия; RE всегда может быть преобразовано в DFA (дискретный конечный автомат), и они эффективны (время линии) и небольшая константа.
O (n log m) корректно. См. http://www.cs.bris.ac.uk/Publications/Papers/2000602.pdf
Надеюсь, что это поможет...