c – 在字典中查找单词模式,高性能

发布时间：2020-12-16 07:02:47 所属栏目：百科来源：网络整理

导读：我需要构建某种字典,此外还包含每个单词出现在语言中的单词频率.通常,这将使用std :: unordered_map实现吗？现在这里有一个问题……我想找到符合正则表达式的所有单词及其频率,性能是我最关心的问题. 我不认为我能够避免迭代一系列元素并逐个元素检查它们是

我需要构建某种字典,此外还包含每个单词出现在语言中的单词频率.通常,这将使用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'],[]    // 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作为索引
int的向量. (如果没有匹配则返回-1.)

通过这种方式,搜索时间相对于线性是线性的
输入的长度.无论表达的数量多少
你想要匹配. (我的RegularExpression课程是
设计超过20年前,用于生成编译器
前端.大约15年前,我将其重新设计为处理UTF-8
输入.)

多年来,代码可以在网上找到,但我没有目前有一个网页,所以除非有人保持旧的复制,它不是.我很乐意把它发给你,但是警告说图书馆已经维持了一段时间,所以用现代的方式编译可能并不容易编译器. (它最初用预标准C编写,并且仍然包含许多解决方法来编译它像Sun CC 4.x这样的东西.)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!