草庐IT

c++ - 在字典中查找单词模式，高性能

coder 2024-02-25 原文

我需要构建某种字典，其中还包含每个单词在该语言中出现的单词频率。通常，这将使用 std::unordered_map 来实现，对吧？现在问题来了……我想找到所有符合某些正则表达式的单词及其频率，而性能是我最关心的问题。

我不认为我将能够避免迭代一系列元素并逐元素检查它们是否与模式匹配。因此，我认为使用一对 vector 而不是 map 可能更聪明:

using namespace std;
typedef vector<pair<string, double>> Dictionary
vector<Dictionary::const_iterator> index;
Dictionary dict;
...
for_each(index['d'], index['e'], DoSomething);

这将使我能够有效地遍历所有以“d”开头的单词。当然，这只有在我已经知道我的正则表达式的第一个字母时才有用，而我认为通常情况并非如此。此外，如果我已经毫无疑问地知道整个单词并且只想查找它的频率，我将不得不遍历整个部分直到找到它。一张 map 可以让我更快地查找它。例如。在寻找“鹿”这个词时

Dictionary::const_iterator it = 
    find_if(index['d'], index['e'], []    // Lambda
        (pair<string, double> const &pr)
        {
           return pr.first == "deer";
        });

根本不是最优的!一种解决方案可能是针对不同情况使用字典的不同实现，即使内存不是大问题，这似乎是一种愚蠢的解决方法。

有什么建议吗？

最佳答案

按照您的想法，一个 std::vector<std::pair<boost::regex, int> >可能会是 最有效率；您反复尝试找到匹配项。

一个更好的解决方案，如果你愿意做这项工作，会 是实现您自己的正则表达式类，没有 捕获(大多数正则表达式中的 (...) 运算符)。 没有捕获，转换常规是相当容易的 表达式到纯 DFA，和可以或常规 表达式，每个正则表达式返回不同的 接受代码。 (这是我自己的正则表达式类的方式 作品。对于大多数应用程序，它几乎没有那么灵活 Boost 的那个，因为它不支持捕获。但确实如此 允许这样的事情:

RegularExpression t1( expr1", 0 );
RegularExpression t2( expr2", 1 );
//  ...
RegularExpression t = t1 | t2 /* | t3 | t4 | ... */ ;

匹配时，expr1匹配返回0，expr2匹配返回1 火柴等；然后，您可以使用匹配 ID 作为索引 一个整数 vector 。 (如果没有匹配则返回 -1。)

这样做，搜索时间是线性的 输入的长度。不管表达多少 你正在尝试匹配。 (我的 RegularExpression 类是 20 多年前设计的，用于生成编译器 前端。大约 15 年前，我重做了它来处理 UTF-8 作为 输入。)

多年来，代码都可以在网上找到，但我没有 目前有一个网页，所以除非有人保留了一个旧的 复制，它不是。我很乐意把它寄给你，但是 警告图书馆有一段时间没有维护了，所以 用现代语言编译它可能不是一件容易的事 编译器。 (它最初是用准标准 C++ 编写的，并且 仍然包含一些变通方法来让它编译 像 Sun CC 4.x.)

关于c++ - 在字典中查找单词模式，高性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13931537/

单词ampsectioncodec++regexdictionarymapunordered-map

有关c++ - 在字典中查找单词模式，高性能的更多相关文章

  1. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  4. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  5. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  6. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  7. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  8. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  9. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  10. ruby - 正则表达式将非英文字母匹配为非单词字符 - 2

    @raw_array[i]=~/[\W]/非常简单的正则表达式。当我用一些非拉丁字母(具体来说是俄语)尝试时，条件是错误的。我能用它做什么？ 最佳答案 @raw_array[i]=~/[\p{L}]/使用西里尔字符进行测试。引用:http://www.regular-expressions.info/unicode.html#prop 关于ruby-正则表达式将非英文字母匹配为非单词字符，我们在StackOverflow上找到一个类似的问题： https://

随机推荐