task.cykparser.hpp

Go to the documentation of this file.

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use these files except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Copyright 2012 - Gonzalo Iglesias, Adrià de Gispert, William Byrne

#ifndef CYKPARSER_HPP
#define CYKPARSER_HPP

#define CYK_RETURN_FAILURE 0

namespace ucam {
namespace hifst {

template <class Data>
class CYKParserTask : public ucam::util::TaskInterface<Data> {

  //Private variables are shown here. Private methods go after public methods
 private:

  unsigned finalresult_;

  unsigned hrmh_;

  unordered_map <std::string, unsigned> hmax_;
  unordered_map <std::string, unsigned> hmin_;

  unsigned nnt_;

  CYKdata cykdata_;

  Data *d_;

 public:

  CYKParserTask ( const ucam::util::RegistryPO& rg ) :
    d_ ( NULL ),
    finalresult_ ( CYK_RETURN_FAILURE ),
    hrmh_ ( rg.get<unsigned> ( HifstConstants::kCykparserHrmaxheight ) ),
    hmax_ ( rg.getPairMappedStringUInt ( HifstConstants::kCykparserHmax ) ),
    hmin_ ( rg.getPairMappedStringUInt ( HifstConstants::kCykparserHmin ) ) {
    cykdata_.nt_exceptions_maxspan = rg.getSetString (
                                       HifstConstants::kCykparserNtexceptionsmaxspan);
    LDEBUG ( "Constructor done!" );
  };

  bool run ( Data& d ) {
    d.cykdata = &cykdata_;
    d_ = &d;
    const GrammarData& gd = *d_->grammar;
    cykparser_rulebpcoordinates_t coord;
    cykdata_.freeMemory();
    grammar_categories_t& categories = cykdata_.categories;
    categories = gd.categories;
    grammar_inversecategories_t& vcat = cykdata_.vcat;
    vcat = gd.vcat;
    unsigned& nnt = cykdata_.nnt;
    nnt = categories.size();
    cykparser_sentence_t& sentence = cykdata_.sentence;
    sentence.clear();
    USER_CHECK ( cykdata_.categories["S"] == 1, "Mandatory to use S as first guy" );
    USER_CHECK ( cykdata_.vcat[1] == "S",
                 "Mandatory to have an S as the first non-terminal guy" );
    std::vector<std::string> aux;
    boost::algorithm::split ( aux, d.sentence,
                              boost::algorithm::is_any_of ( " " ) );
    for ( unsigned k = 0; k < aux.size(); ++k ) {
      sentence.push_back ( ucam::util::toNumber<unsigned> ( aux[k] ) );
      if ( categories.find ( aux[k] ) == categories.end() ) {
        categories[aux[k]] = k + nnt + 1;
        cykdata_.cykgrid.Add ( k + nnt + 1, k, 0, sentence[k] );
      } else {
        cykdata_.cykgrid.Add ( categories[aux[k]], k, 0, sentence[k] );
      }
      vcat[k + nnt + 1] = aux[k];
    }
    USER_CHECK ( vcat[1] == "S",
                 "S must be the top guy in the non-terminal hierarchy" );
    USER_CHECK ( categories["S"] == 1,
                 "S must be the top guy in the non-terminal hierarchy (2)" );
    USER_CHECK ( aux.size() == sentence.size(),
                 "sentence not properly initialized?" );
    d_->stats->setTimeStart ("cyk");
    LDEBUG ( "Now start stage 1: Initialize Bottom row of the chart" );
    fillBottomChart(); 
    LDEBUG ( "Start stage 2: fill bottom-up the chart" );
    fillChart();      
    d_->stats->setTimeEnd ("cyk");
    finalresult_ = cykdata_.cykgrid ( cykdata_.categories["S"], 0,
                                      sentence.size() - 1 ).size();
    if ( finalresult_ > 0 ) {
      LINFO ( "CYK success:" << finalresult_ << " parse trees" );
    } else {
      LINFO ( "CYK failed!" );
    }
    d.cykdata->storeRuleCounts ( d.stats->rulecounts );
    d.stats->numcats = d.cykdata->vcat.size();
    LINFO ( "Number of rules applied:" << d.stats->rulecounts.size() );
    cykdata_.success = finalresult_;
    return false;
  };

  ~CYKParserTask ( void ) {
    hmin_.clear();
    hmax_.clear();
  };

  const CYKdata *getcykdata() {
    return &cykdata_;
  };

  int getFinalResult() {
    return finalresult_;
  };

 private:

  void examineRule ( unsigned x, unsigned ymax, unsigned rule_idx,
                     unsigned rule_pos, cykparser_rulebpcoordinates_t coord ) {
    cykparser_ruledependencies_t& rd = cykdata_.rd;
    cykparser_rulebpcoordinates_t coord2;
    SentenceSpecificGrammarData& ssgd = *d_->ssgd;
    std::string cat =     ssgd.getRHSSource ( rule_idx, rule_pos );
    getFilteredNonTerminal ( cat );
    unsigned regla_tam = ssgd.getRHSSourceSize ( rule_idx );
    int x2;
    unsigned z = ( cykdata_.categories[cat] == 0 ) ? 0 : 1;
    for ( unsigned n = 0; n < ymax; n++ ) {
      if ( cykdata_.cykgrid ( cykdata_.categories[cat], x, n ).size() > 0 ) {
        coord2 = coord; //copy coord, we will need to reuse later.
        coord2.push_back ( cykdata_.categories[cat] );
        coord2.push_back ( x );
        coord2.push_back ( n );
        if ( rule_pos == regla_tam - 1 ) { //last element of the rule
          if ( n == ymax -
               1 ) { //We are in the diagonal, therefore span is complete -- full span verified.
            rd.push_back ( coord2 );
            //                    LDEBUG("span completely verified!, n="<<n<<",ymax="<<ymax);
          } else {
            //                    LDEBUG("span not verified, rule not valid, n="<<n<<",ymax="<<ymax);
          }
        } else {
          if ( ymax > 1 ) {
            x2 = n + x + 1; //next x.
            //This element verified, now look next one.
            examineRule ( x2, ymax - n - 1, rule_idx, rule_pos + 1, coord2 );
          }
        }
      }
      z = 0;
    }
    return;
  };

  void insertMonoRHSRules ( unsigned x, unsigned y ) {
    cykparser_rulebpcoordinates_t coord;
    grammar_categories_t& categories = cykdata_.categories;
    grammar_inversecategories_t& vcat = cykdata_.vcat;
    unsigned& nnt = cykdata_.nnt; //number of non-terminals
    SentenceSpecificGrammarData& ssgd = *d_->ssgd;
    ssgrammar_listofrules_t rules;
    for ( unsigned cc = nnt; cc > 1;
          --cc ) { // cc>1 as for 1 there will be no rule with cc lower.
      if ( cykdata_.cykgrid ( cc, x, y ).size() > 0 ) {
        LDEBUG ( vcat[cc] << "," << x << "," << y << ":" <<
                 "Searching for rules with only one element" );
        if ( ssgd.rulesWithRhsSpan1[x].find ( vcat[cc] ) !=
             ssgd.rulesWithRhsSpan1[x].end() )
          rules = ssgd.rulesWithRhsSpan1[x][vcat[cc]];
        else rules.clear();
        LDEBUG ( "Found: " << rules.size() );
        for ( unsigned jpts = 0; jpts < rules.size(); ++jpts ) {
          unsigned& idx = rules[jpts];
          unsigned head = categories[ssgd.getLHS ( idx )];
          //          if ( head <= cykdata_.numberTopNonTerminals && x > 0 ) continue;
          //if not listed as exception, then discard
          if ( y >= hrmh_ &&
               cykdata_.nt_exceptions_maxspan.find ( ssgd.getLHS ( idx ) ) ==
               cykdata_.nt_exceptions_maxspan.end() ) continue;
          if ( head >= cc ) {
            LWARN ( ssgd.getLHS ( idx ) << "," << x << "," << y << ":" <<
                    "Potentially nasty looping rule (filtering): " << ssgd.getRule ( idx ) );
            continue;
          }
          LDEBUG ( ssgd.getLHS ( idx ) << "," << x << "," << y << ":" << "Accepted: " <<
                   ssgd.getRule ( idx )  << ", original rule_id=" << ssgd.getIdx (
                     idx ) << ",vs" << idx );
          cykdata_.cykgrid.Add ( head, x, y, idx );
          coord.clear();
          coord.push_back ( cc );
          coord.push_back ( x );
          coord.push_back ( y );
          cykdata_.bp.Add ( head, x, y, coord );
        }
      }
    }
  };

  void fillBottomChart() {
    grammar_categories_t& categories = cykdata_.categories;
    cykparser_sentence_t& sentence = cykdata_.sentence;
    //    const GrammarData &gd = *d_->grammar;
    SentenceSpecificGrammarData& ssgd = *d_->ssgd;
    ssgrammar_listofrules_t rules;
    for ( unsigned x = 0; x < sentence.size(); ++x ) {
      std::string cat = ucam::util::toString ( sentence[x] );
      if ( ssgd.rulesWithRhsSpan1[x].find ( cat ) !=
           ssgd.rulesWithRhsSpan1[x].end() ) {
        rules = ssgd.rulesWithRhsSpan1[x][cat]; //In this case it should be identical...
      } else {
        LDEBUG ( "No rules to process" );
        rules.clear();
      }
      for ( unsigned p = 0; p < rules.size(); ++p ) {
        unsigned& idx = rules[p];
        LDEBUG ( ssgd.getLHS ( idx ) << "," << x << ",0:" << "Accepted: " <<
                 ssgd.getRule ( idx ) << ", original rule_id=" << ssgd.getIdx (
                   idx ) << ",vs" << idx );
        cykdata_.cykgrid.Add ( categories[ssgd.getLHS ( idx )], x, 0, idx );
        cykparser_rulebpcoordinates_t cdi;
        cdi.push_back ( categories[cat] );
        cdi.push_back ( x );
        cdi.push_back ( 0 ); //pointing to the word itself.
        cykdata_.bp.Add ( categories[ssgd.getLHS ( idx )], x, 0, cdi );
      }
      insertMonoRHSRules ( x, 0 );
    }
  };

  void fillChart() {
    grammar_categories_t& categories = cykdata_.categories;
    grammar_inversecategories_t&  vcat = cykdata_.vcat;
    cykparser_sentence_t&  sentence = cykdata_.sentence;
    unsigned& nnt = cykdata_.nnt;
    unordered_map<std::string, cykparser_ruledependencies_t  > minicache;
    cykparser_ruledependencies_t&  rd = cykdata_.rd;
    cykparser_rulebpcoordinates_t coord;
    const GrammarData& gd = *d_->grammar;
    SentenceSpecificGrammarData& ssgd = *d_->ssgd;
    ssgrammar_listofrules_t rules;
    for ( unsigned y = 1; y < sentence.size(); ++y ) {
      for ( unsigned x = 0; x < sentence.size() - y; ++x ) {
        for ( unsigned n = 0; n < y; n++ ) {
          //just an alias.
          unsigned& x1 = x;
          unsigned y1 = n;
          unsigned x2 = y1 + x1 + 1;
          for ( unsigned cc = 1; cc <= nnt + sentence.size();
                ++cc ) { //Only in this case we have to make sure it exists.
            std::string cat = vcat[cc];
            // prevent non terminals other than the top nonterminals (e.g. S) to have a span greater or equal to hrmaxheight
            if ( cykdata_.cykgrid ( cc, x1, y1 ).size() == 0 ) continue;
            //Keep caching at the same position for identical rules with different translations
            minicache.clear();
            rules = ssgd.rulesWithRhsSpan2OrMore[x][cat];
            LDEBUG ( vcat[cc] << "," << x << "," << y << ":" << " Obtained " << ucam::util::toString (
                       rules.size() ) << " rules." );
            for ( unsigned i = 0; i < rules.size(); i++ ) {
              unsigned idx = rules[i];
              LDEBUG ( vcat[cc] << "," << x << "," << y << ":" << "Testing rule idx=" << idx
                       << ",value=" << ssgd.getRule ( idx )  << "; Iteration=" << i );
              if ( ssgd.getRHSSourceSize ( idx ) > y + 1 ) {
                LDEBUG ( vcat[cc] << "," << x << "," << y << ":" <<
                         "Rejected (rule minimum span too big): " << ssgd.getRule ( idx ) );
                continue;
              }
              if (y >= hrmh_ ) {
                if (cykdata_.nt_exceptions_maxspan.find (ssgd.getLHS ( idx ) ) ==
                    cykdata_.nt_exceptions_maxspan.end() ) {
                  LDEBUG ( vcat[cc] << "," << x << "," << y << ":" <<
                           "Rejected (Default Maximum span reached hrmaxheight): " << ssgd.getRule (
                             idx ) );
                  LDEBUG ( "Note: hrmaxheight=" << hrmh_ <<
                           " has been reached, only nonterminals listed as exceptions (--cykparser.ntexceptionsmaxspan are allowed!" );
                  continue;
                }
              }
              if ( hmax_.find ( ssgd.getLHS ( idx ) ) != hmax_.end() )
                if ( y > hmax_[ssgd.getLHS ( idx )] ) {
                  LDEBUG ( vcat[cc] << "," << x << "," << y << ":" << "Rejected (hmax): " <<
                           ssgd.getRule ( idx ) );
                  continue;
                }
              if ( hmin_.find ( ssgd.getLHS ( idx ) ) != hmin_.end() )
                if ( y < hmin_[ssgd.getLHS ( idx )] ) {
                  LDEBUG ( vcat[cc] << "," << x << "," << y << ":" << "Rejected (hmin): " <<
                           ssgd.getRule ( idx ) );
                  continue;
                }
              std::string rhs = ssgd.getRHSSource ( idx );
              rd.clear();
              unordered_map<std::string, cykparser_ruledependencies_t > ::iterator itx =
                minicache.find ( rhs );
              if ( itx != minicache.end() ) {
                rd = itx->second; 
              } else {
                coord.clear();
                coord.push_back ( cc );
                coord.push_back ( x1 );
                coord.push_back ( y1 );
                examineRule ( x2 - 0, y - ( x2 - x1 - 1 ), idx, 1, coord );
                minicache[rhs] = rd; 
              }
              if ( rd.size() == 0 ) {
                LDEBUG ( vcat[cc] << "," << x << "," << y << "(/" << n << "):" << "Rejected " <<
                         ssgd.getRule ( idx ) << ", for: " << ssgd.getLHS ( idx ) << "," << x << "," <<
                         y );
                continue;
              }
              LDEBUG ( vcat[cc] << "," << x << "," << y << "(/" << n << "):" << "Accepted: "
                       << ssgd.getRule ( idx )  << ", for: " << ssgd.getLHS ( idx ) << "," << x << ","
                       << y << ", original rule_id=" << ssgd.getIdx ( idx ) << ",vs" << idx );
              for ( unsigned kpt = 0; kpt < rd.size(); kpt++ ) {
                cykdata_.cykgrid.Add ( categories[ssgd.getLHS ( idx )], x, y , idx );
                cykdata_.bp.Add ( categories[ssgd.getLHS ( idx )], x, y, rd[kpt] );
              }
            }
          }
        }
        insertMonoRHSRules ( x, y );
      }
    }
  };

  ZDISALLOW_COPY_AND_ASSIGN ( CYKParserTask );

};

}
} // end namespaces

#endif