技术专题

正则表达式内存耗尽异常解决方案

2009年3月15日 阅读(219)

前面碰到的正则表达式匹配时,产生的内存耗尽异常,大概提到两种方案,一种是给匹配建立线程,超时时把它杀死。另一种则从其根源上看,即正则表达式产生内存耗尽异常的原因是,由于匹配是个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> &regex_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;
   }
    }
    */
   

 

You Might Also Like