正则表达式内存耗尽异常解决方案 2009-03-15 10:01
前面碰到的正则表达式匹配时，产生的内存耗尽异常，大概提到两种方案，一种是给匹配建立线程，超时时把它杀死。另一种则从其根源上看，即正则表达式产生内存耗尽异常的原因是，由于匹配是个np完全问题，为了避免无限执行下去，所以实现中一般对匹配中达到的状态进行了计数，当状态达到了一定数目则抛出这个异常。
究其原因是因为匹配表达式中出现了太多的.*,导致匹配的可能性大大增加，出现的回溯次数增多，对于web页面的匹配，我们结合一下，提出如下匹配方式，即把原来的一次匹配，改成多层匹配，即首先利用上层匹配，缩小匹配的文本，然后再在已经满足上层匹配的文本中进行下层的匹配。
比如(?<=<li class=g>).*?<.*?><a.*?href="(.*?)"[^>]*?>(.*?)</a>(.*?)<br>.*?<cite>(.*?)</CITE>.*?(?=</a></span>)
我们则拆成下面两个匹配过程：
(?<=<li class=g>)(.*?)(?=</a></span>)
.*?<.*?><a.*?href="(.*?)"[^>]*?>(.*?)</a>(.*?)<br>.*?<cite>(.*?)</CITE>.*?
具体实现，我们则将原来的正则表达式，改成多个的组合，两个正则式之间用token char隔离。
注意：
1.由于我们采用了空格作为分割正则表达式的标志，因此必须把正则表达式本身含有的空格全部使用\s替代。因此必须注意保证config.xml里的正则表达式与这里所采用的处理方式相一致。
2.正则表达式中，不要出现不成对的<,因为后面我们要利用<>去除标签内的文字。
3.有时候虽然在正则匹配测试工具里匹配成功，但是在程序中也可能依然错误，原因就是，在我们程序中对正则式中空格的特殊性的使用造成的。
现在的实现实际上是递归实现：实际上我们在递归时采用的是what[0].也就意味着实际上我们用上层匹配的结果作为下层的范围。实际上如果我们修改成what[1]将允许我们使用更加复杂的筛选.比如我们(?<=<li
recurseSearch(regex_exprs,web_text,set,what[0].first,what[0].second,level+1);
/*
完成正则表达式的多层匹配，上一层的匹配结果作为下一层的输入串，继续进行匹配，层层过滤。
参数如下：
regex_exprs-代表所有各层正则表达式的集合
web_text-要处理的网页文本
set-保存结果的集合
start-待处理的文本的起始处
end- 待处理的文本的结束处
level-控制结束，及当前处理那个正则表达式的层数，从1开始计数。
*/
void HtmlParser::recurseSearch(vector<boost::regex> ®ex_exprs,WebText &web_text,ResultSet &set,str_const_iterator start,str_const_iterator end,int level){
//int index = web_text.start_index;
boost::smatch what;
boost::regex expression = regex_exprs[level-1];
while( boost::regex_search(start, end, what, expression) )
{
//如果是最终的那个正则表达式 ,则开始搞结果
if(level == regex_exprs.size()){
Result elem(web_text.source.getName());
int sub_count = (int)what.size();
for(int i = 1 ; i < sub_count ; i++ ){
std::string msg(what[i].first, what[i].second);
elem.setBySubNumber(msg,(RES_CONTENT_TYPE)i);
}
//注意我们这里修改了 web_text.start_index的值，用它来给结果在网页中的索引赋值。
elem.setIndexInSource(web_text.start_index);
web_text.start_index++;
elem.deleteBrace();
set.addResult(elem);
}
else{
recurseSearch(regex_exprs,web_text,set,what[0].first,what[0].second,level+1);
}
start = what[0].second;
}
}
/*
利用正则表达式，从网页中抽取每条搜索结果,具体则通过调用 HtmlParser::recurseSearch实现
并将结果直接保存到 ResultSet中
使用时，由 ResultSet调用，同时本身回调ResultSet里的addResult方法，添加搜索结果
*/
void HtmlParser::webParse(WebText &web_text,ResultSet &set){
try{
debug_log("HtmlParser::webParse:download web:" ,web_text.text);
string web_regex = web_text.getRegex();
vector<boost::regex> regex_exprs;
/*
注意，如果选择'!',则只能处理一个正则式的情况，无法处理多层正则的情况。
所以如果想恢复原来的模式，只需要把这里的string_token()的第二个参数改成'!',
同时保证config.xml里的正则表达式只有一个即可。
*/
vector<string> regex_tokens = string_token(web_regex,' ');
for(int i = 0 ; i < regex_tokens.size(); i++){
boost::regex expression(regex_tokens[i],boost::regex::perl|boost::regex::icase);
regex_exprs.push_back(expression);
}
str_const_iterator start = web_text.text.begin();
str_const_iterator end = web_text.text.end();
recurseSearch(regex_exprs,web_text,set,start,end,1);
}
catch(boost::regex_error e){
string exception_str = string("exception:expression is not a valid regular expression: \"") + e.what() + "\"";
debug_log(web_text.getSiteName()+"-HtmlParser::webParse:",exception_str);
cout<< exception_str <<endl;
}
catch(std::runtime_error e){
string exception_str = string("exception:expression runtime_error: \"") + e.what() + "\"";
debug_log(web_text.getSiteName()+"HtmlParser::webParse:",exception_str);
cout<< exception_str <<endl;
}
catch(std::bad_alloc e){
string exception_str = string("exception:expression bad_alloc: \"") + e.what() + "\"";
debug_log(web_text.getSiteName()+"HtmlParser::webParse:",exception_str);
cout<< exception_str <<endl;
}
}
以前的实现如下：
/*
void HtmlParser::webParse(WebText &web_text,ResultSet &set){
try{
string web_regex = web_text.getRegex();
boost::regex expression(web_regex,boost::regex::perl|boost::regex::icase);
boost::smatch what;
str_const_iterator start = web_text.text.begin();
str_const_iterator end = web_text.text.end();
debug_log("HtmlParser::webParse:download web:" ,web_text.text);
int index = web_text.start_index;
while( boost::regex_search(start, end, what, expression) )
{
Result elem(web_text.source.getName());
//std::cout<< "Have：" ;
int sub_count = (int)what.size();
for(int i = 1 ; i < sub_count ; i++ ){
std::string msg(what[i].first, what[i].second);
//std::cout<< msg.c_str() << std::endl;
elem.setBySubNumber(msg,(RES_CONTENT_TYPE)i);
}
start = what[0].second;
elem.setIndexInSource(index);
index++;
elem.deleteBrace();
set.addResult(elem);
}
}
catch(boost::regex_error e){
string exception_str = string("exception:expression is not a valid regular expression: \"") + e.what() + "\"";
debug_log(web_text.getSiteName()+"-HtmlParser::webParse:",exception_str);
cout<< exception_str <<endl;
}
catch(std::runtime_error e){
string exception_str = string("exception:expression runtime_error: \"") + e.what() + "\"";
debug_log(web_text.getSiteName()+"HtmlParser::webParse:",exception_str);
cout<< exception_str <<endl;
}
catch(std::bad_alloc e){
string exception_str = string("exception:expression bad_alloc: \"") + e.what() + "\"";
debug_log(web_text.getSiteName()+"HtmlParser::webParse:",exception_str);
cout<< exception_str <<endl;
}
}
*/
