提升字符串匹配 DFA

Question

给定一个字符串，我必须测试它是否以一组已知的后缀结尾。现在，由于后缀不是很小，文档中的每个单词都必须根据已知后缀列表进行检查。单词和后缀中的每个字符都是char32_t。作为天真的迭代匹配将是昂贵的。尽管大多数后缀不是子后缀或另一个后缀的前缀，但它们中的大多数是由一小部分字符构成的。大多数支票将是未命中而不是命中。

所以我想建一个DFA的后缀来尽量减少miss的成本。我可以手动解析 unicode 代码点并使用 boost-graph 创建 DFA。但是是否有任何现有的库可以为我构建它？

包含所有后缀的巨大正则表达式是否会比 DFA 更便宜，因为正则表达式搜索也以类似的方式构建用于匹配的 DFA？但是我想知道命中时匹配的是哪个后缀。在正则表达式的情况下，我需要执行另一个线性搜索来获得它（我无法标记正则表达式的内部 DFA 的顶点）。我还需要 unicode 正则表达式。我猜将所有后缀都放在 | 中会像线性搜索一样昂贵。我想我需要检查常见字符并相应地创建具有 lookahed 和 lookbacks 的正则表达式。这不是我手动构建 DFA 需要面对的同样困难吗？

我正在使用 utf-32 进行随机访问。但是，如果我可以轻松解决它，切换到 utf-8 不是问题。我将从右到左反转字符串和模式。

Answer 1

你考虑过Spirit吗？当然，您没有指定如何在上下文中检测后缀（最后是否需要它们，是否需要前面的语法等），但您可以这样做：

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

它构建了一个Trie，非常有效。它可以解析任何类型的输入迭代器（如果您愿意，也可以包括流）。只需为上下文要求添加一些魔法约束，例如 end-of-input:

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

如果您甚至希望 return 字符串的文本值，只需这样做：

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()};
}

Spirit 给你留下了很多自由，让你充满智慧，动态 add/remove 符号，例如将 no_case 与 Trie 等一起使用

完整演示

使用 X3 (c++14)

Live On Coliru

#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)

灵气版

文字端口：Live On Coliru

仅 C++11 版本：Live On Coliru

以及真正复古编程体验的 C++03 版本：Live On Coliru

提升字符串匹配 DFA

boost string matching DFA

c++

regex

boost

unicode

dfa

完整演示

灵气版