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

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