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

Question

我需要构建某种字典，其中还包含每个单词在该语言中出现的单词频率。通常，这将使用 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";
        });

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

有什么建议吗？

Answer 1

按照您的想法，一个 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.)