public HyperGraph search(){
  long startTime=System.currentTimeMillis();
  Future future=new Future(chart);
  stacks=new ArrayList<>();
  stacks.add(null);
  ComputeNodeResult result=new ComputeNodeResult(this.featureFunctions,Hypothesis.BEGIN_RULE,null,-1,1,null,this.sentence);
  Stack firstStack=new Stack(sentence,config);
  firstStack.add(new Hypothesis(result.getDPStates(),future.Full()));
  stacks.add(firstStack);
  for (int source_words=2; source_words <= sentence.length(); ++source_words) {
    Stack targetStack=new Stack(sentence,config);
    stacks.add(targetStack);
    for (int phrase_length=1; phrase_length <= Math.min(source_words - 1,chart.MaxSourcePhraseLength()); phrase_length++) {
      int from_stack=source_words - phrase_length;
      Stack tailStack=stacks.get(from_stack);
      LOG.debug("WORDS {} MAX {} (STACK {} phrase_length {})",source_words,chart.MaxSourcePhraseLength(),from_stack,phrase_length);
      for (      Coverage coverage : tailStack.getCoverages()) {
        ArrayList<Hypothesis> hypotheses=tailStack.get(coverage);
        int begin=coverage.firstZero();
        int last_end=Math.min(coverage.firstZero() + config.reordering_limit,chart.SentenceLength());
        int last_begin=(last_end > phrase_length) ? (last_end - phrase_length) : 0;
        for (begin=coverage.firstZero(); begin <= last_begin; begin++) {
          if (!coverage.compatible(begin,begin + phrase_length) || !permissible(coverage,begin,begin + phrase_length)) {
            continue;
          }
          if (begin == sentence.length() - 1 && source_words != sentence.length())           continue;
          PhraseNodes phrases=chart.getRange(begin,begin + phrase_length);
          if (phrases == null)           continue;
          LOG.debug("Applying {} target phrases over [{}, {}]",phrases.size(),begin,begin + phrase_length);
          float future_delta=future.Change(coverage,begin,begin + phrase_length);
          Candidate cand=new Candidate(featureFunctions,sentence,hypotheses,phrases,future_delta,new int[]{0,0});
          targetStack.addCandidate(cand);
        }
      }
    }
    targetStack.search();
  }
  LOG.info("Input {}: Search took {} seconds",sentence.id(),(System.currentTimeMillis() - startTime) / 1000.0f);
  return createGoalNode();
}

public HyperGraph search ( ) { long startTime = System . currentTimeMillis ( ) ; Future future = new Future ( chart ) ; stacks = new ArrayList < > ( ) ; stacks . add ( null ) ; ComputeNodeResult result = new ComputeNodeResult ( this . featureFunctions , Hypothesis . BEGIN_RULE , null , - 1 , 1 , null , this . sentence ) ; Stack firstStack = new Stack ( sentence , config ) ; firstStack . add ( new Hypothesis ( result . getDPStates ( ) , future . Full ( ) ) ) ; stacks . add ( firstStack ) ; for ( int source_words = 2 ; source_words <= sentence . length ( ) ; ++ source_words ) { Stack targetStack = new Stack ( sentence , config ) ; stacks . add ( targetStack ) ; for ( int phrase_length = 1 ; phrase_length <= Math . min ( source_words - 1 , chart . MaxSourcePhraseLength ( ) ) ; phrase_length ++ ) { int from_stack = source_words - phrase_length ; Stack tailStack = stacks . get ( from_stack ) ; LOG . debug ( "WORDS {} MAX {} (STACK {} phrase_length {})" , source_words , chart . MaxSourcePhraseLength ( ) , from_stack , phrase_length ) ; for ( Coverage coverage : tailStack . getCoverages ( ) ) { ArrayList < Hypothesis > hypotheses = tailStack . get ( coverage ) ; int begin = coverage . firstZero ( ) ; int last_end = Math . min ( coverage . firstZero ( ) + config . reordering_limit , chart . SentenceLength ( ) ) ; int last_begin = ( last_end > phrase_length ) ? ( last_end - phrase_length ) : 0 ; for ( begin = coverage . firstZero ( ) ; begin <= last_begin ; begin ++ ) { if ( ! coverage . compatible ( begin , begin + phrase_length ) || ! permissible ( coverage , begin , begin + phrase_length ) ) { continue ; } if ( begin == sentence . length ( ) - 1 && source_words != sentence . length ( ) ) continue ; PhraseNodes phrases = chart . getRange ( begin , begin + phrase_length ) ; if ( phrases == null ) continue ; LOG . debug ( "Applying {} target phrases over [{}, {}]" , phrases . size ( ) , begin , begin + phrase_length ) ; float future_delta = future . Change ( coverage , begin , begin + phrase_length ) ; Candidate cand = new Candidate ( featureFunctions , sentence , hypotheses , phrases , future_delta , new int [ ] { 0 , 0 } ) ; targetStack . addCandidate ( cand ) ; } } } targetStack . search ( ) ; } LOG . info ( "Input {}: Search took {} seconds" , sentence . id ( ) , ( System . currentTimeMillis ( ) - startTime ) / 1000.0f ) ; return createGoalNode ( ) ; }
the main algorithm . returns a hypergraph representing the search space .
