c – 提升字符串匹配DFA

概述给定一个字符串,我必须测试是否以一组已知的后缀结束.现在因为后缀不是很小,所以必须根据已知后缀列表检查文档中的每个单词.单词和后缀中的每个字符都是char32_t.由于天真的迭代匹配将是昂贵的.虽然大多数后缀不是子后缀或另一个后缀的前缀,但大多数后缀都是用一小组字符构造的.大多数支票都是错过而不是打击. 所以我想建立一个后缀的DFA来最小化错过的成本.我可以手动解析unicode代码点并使用boo 给定一个字符串,我必须测试是否以一组已知的后缀结束.现在因为后缀不是很小,所以必须根据已知后缀列表检查文档中的每个单词.单词和后缀中的每个字符都是char32_t.由于天真的迭代匹配将是昂贵的.虽然大多数后缀不是子后缀或另一个后缀的前缀,但大多数后缀都是用一小组字符构造的.大多数支票都是错过而不是打击.

所以我想建立一个后缀的DFA来最小化错过的成本.我可以手动解析unicode代码点并使用boost-graph创建DFA.但是,是否有任何现有的库可以为我构建？

包含所有后缀的巨大正则表达式是否会比DFA更便宜,因为正则表达式搜索还会以类似的方式构建DFA以进行匹配？但我想知道哪个后缀匹配时有匹配.在正则表达式的情况下,我需要执行另一个线性搜索来获得它(我不能标记正则表达式的内部DFA的顶点).我还需要unicode正则表达式.只需将所有后缀加上|我估计它将像线性搜索一样昂贵.我想我需要检查常见字符并使用lookahed和lookbacks相应地创建正则表达式.难道不是我需要面对手动构建DFA的难度吗？

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

解决方法 你考虑过Spirit吗？当然你没有在上下文中指定你如何检测后缀(你最后是否需要它们,你需要一些语法吗？)但是你可以这样做：

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(),x3::seek[x3::raw[suffix >> x3::eoi]],output);    return {output.begin(),output.size()};}

精神让你有很大的自由来围绕智能,动态添加/删除符号,例如与TrIE等使用no_case

完整的演示

使用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","qux";        return sym; // x3::no_case[sym];    }();    bool has_suffix(string_vIEw sv) {        return parse(sv.cbegin(),x3::seek[suffix >> x3::eoi]);    }    string_vIEw get_suffix(string_vIEw sv) {        boost::iterator_range<string_vIEw::const_iterator> output;        parse(sv.cbegin(),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

总结

以上是内存溢出为你收集整理的c – 提升字符串匹配DFA全部内容，希望文章能够帮你解决c – 提升字符串匹配DFA所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。