4

我需要建立某种字典，另外还包含每个单词在语言中出现的单词频率。通常，这将使用 std::unordered_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”开头的单词。当然，这只有在我已经知道我的正则表达式的第一个字母时才有帮助，而我认为这通常不是这种情况。另外，如果我已经毫无疑问地知道整个单词并且只想查找它的频率，我将不得不遍历整个部分，直到找到它。地图可以让我更快地查找它。例如，在寻找“鹿”这个词时

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

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

有什么建议么？

4

2 回答 2

1

按照您的想法， an 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 作为 int 向量的索引。（如果没有匹配则返回 -1。）

通过这种方式，搜索时间与输入的长度成线性关系。无论您尝试匹配多少个表达式。（我的 RegularExpression 类是 20 多年前设计的，用于生成编译器前端。大约 15 年前，我重做了它来处理 UTF-8 作为输入。）

多年来，代码都可以在网上找到，但我目前没有网页，所以除非有人保留了旧副本，否则没有。我很乐意将其发送给您，但请注意，该库已经有一段时间没有维护了，因此使用现代编译器对其进行编译可能并非易事。（它最初是用准标准 C++ 编写的，并且仍然包含许多变通方法以使其能够与 Sun CC 4.x 之类的东西一起编译。）

于 2012-12-18T11:37:28.520 回答
0

您最好的选择是使用有限的 Satae 传感器，例如http://www.ims.uni-stuttgart.de/projekte/gramotron/SOFTWARE/SFST.html。

正如您所说，该地图将占用大量空间。

您可以将传感器视为一个大的正则表达式（正则表达式是一个编译的自动机）。

于 2012-12-18T11:16:46.840 回答