повысить соответствие строки DFA

Question

повысить соответствие строки DFA

Учитывая строку, я должен проверить, заканчивается ли это известным набором суффиксов. Теперь суффиксы не очень малы, и каждое слово в документе должно быть проверено на соответствие этому списку известных суффиксов. Каждый символ в слове и суффиксе char32_t, В качестве наивного итеративного сопоставления будет дорого. Хотя большинство суффиксов не являются суб-суффиксом или префиксом другого суффикса, большинство из них состоит из небольшого набора символов. Большинство проверок будет скорее промахом, чем попаданием.

Поэтому я хочу построить DFA из суффиксов, чтобы минимизировать стоимость мисс. Я могу вручную проанализировать кодовые точки Unicode и создать DFA, используя boost-graph, Но есть ли какая-нибудь существующая библиотека, которая построит это для меня?

Будет ли огромное регулярное выражение, содержащее все суффиксы, дешевле, чем DFA, потому что поиск по регулярному выражению также создает DFA для сопоставления аналогичным образом? Но я хочу знать, какой суффикс был найден при попадании. В случае с регулярным выражением мне нужно выполнить еще один линейный поиск, чтобы получить это (я не могу пометить вершины внутреннего DFA регулярного выражения). Также мне нужно unicode регулярное выражение. Просто положить все суффиксы с | будет так же дорого, как линейный поиск, я думаю. Я думаю, что мне нужно проверить общие символы и создать регулярное выражение соответственно с lookahed и lookbacks. Разве это не та же сложность, с которой мне приходится сталкиваться при создании DFA вручную?

я использую utf-32 для произвольного доступа. Однако не проблема переключиться на utf-8, если я могу легко решить эту проблему. Я переверну строку и образец справа налево.

4

boost c++dfa regex unicode

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Рассматривали ли вы Дух? Конечно, вы не указали, как вы обнаруживаете суффиксы в контексте (требуются ли они в конце, требуется ли перед ним некоторая грамматика и т. Д.), Но вы могли бы сделать что-то вроде этого:

    x3::symbols<Char> sym;
sym += "foo", "bar", "qux";

Он строит Trie, что довольно эффективно. Он может анализировать любой тип входного итератора (включая потоки, если вы так склонны). Просто добавьте немного магического ограничения для контекстных требований, таких как конец входного текста:

bool has_suffix(string_view sv) {
return parse(sv.cbegin(), sv.cend(), x3::seek[suffix >> x3::eoi]);
}

Если вы даже хотите вернуть текстовое значение строки, просто сделайте это:

string_view get_suffix(string_view sv) {
boost::iterator_range<string_view::const_iterator> output;
parse(sv.cbegin(), sv.cend(), x3::seek[x3::raw[suffix >> x3::eoi]], output);
return {output.begin(), output.size()};
}

Дух оставляет вам большую свободу, чтобы окружать его умом, динамически добавлять / удалять символы, например, использование no_case с Три и т. д.

Полная демонстрация

Использование X3 (c ++ 14)

Жить на Колиру

#include <boost/spirit/home/x3.hpp>
#include <string_view>
#include <cstdint>

namespace Demo {
using Char = char32_t;
using string_view = std::basic_string_view<Char>;

namespace x3 = boost::spirit::x3;

static auto const suffix = [] {
x3::symbols<Char> sym;
sym += "foo", "bar", "qux";

return sym; // x3::no_case[sym];
}();

bool has_suffix(string_view sv) {
return parse(sv.cbegin(), sv.cend(), x3::seek[suffix >> x3::eoi]);
}

string_view get_suffix(string_view sv) {
boost::iterator_range<string_view::const_iterator> output;
parse(sv.cbegin(), sv.cend(), x3::seek[x3::raw[suffix >> x3::eoi]], output);
return {output.begin(), output.size()};
}
}

#include <iostream>
#include <iomanip>

int main() {
using namespace Demo;

auto widen = [](string_view sv) { return std::wstring(sv.begin(), sv.end()); };
std::wcout << std::boolalpha;

for (string_view testcase : { U"nope", U"lolbar you betqux" }) {
std::wcout
<< widen(testcase)
<< L" -> " << has_suffix(testcase)
<< L" (" << widen(get_suffix(testcase))
<< L")\n";
}
}

Печать

nope -> false ()
lolbar you betqux -> true (qux)

Версия Spirit Qi

Буквальный порт: Жить на Колиру

Версия только для C ++ 11: Жить на Колиру

И версия C ++ 03 для действительно ретро-программирования: Жить на Колиру

1