private List<RichTranslation<TK,FV>> standardNbest(Beam<Derivation<TK,FV>> beam,RecombinationHistory<Derivation<TK,FV>> recombinationHistory,InputProperties sourceInputProperties,int sourceInputId,List<Sequence<TK>> targets,OutputSpace<TK,FV> outputSpace,int size,boolean distinct){
  List<Derivation<TK,FV>> goalStates=new ArrayList<>(beam.size());
  for (  Derivation<TK,FV> derivation : beam)   goalStates.add(derivation);
  final StateLatticeDecoder<Derivation<TK,FV>> latticeDecoder=new StateLatticeDecoder<>(goalStates,recombinationHistory);
  final boolean prefixDecoding=sourceInputProperties.containsKey(InputProperty.TargetPrefix);
  final boolean prefixDiversity=distinct && prefixDecoding;
  final Sequence<TK> prefix=prefixDecoding ? targets.get(0) : null;
  final Set<Sequence<TK>> distinctSurfaceTranslations=distinct ? new HashSet<>(size) : null;
  final List<RichTranslation<TK,FV>> translations=new ArrayList<>(size);
  int numExtracted=0;
  long nbestId=0;
  for (  List<Derivation<TK,FV>> latticePath : latticeDecoder) {
    ++numExtracted;
    if (numExtracted > MAX_POPPED_ITEMS)     break;
    if (distinct) {
      Sequence<TK> pathTarget=extractTarget(latticePath);
      if (prefixDiversity) {
        int start=prefix.size();
        int end=Math.min(pathTarget.size(),prefix.size() + PREFIX_DIVERSITY_SIZE);
        if (start < end)         pathTarget=pathTarget.subsequence(start,end);
      }
      if (distinctSurfaceTranslations.contains(pathTarget))       continue;
      distinctSurfaceTranslations.add(pathTarget);
    }
    boolean withDTUs=false;
    final Set<Rule<TK>> seenOptions=new HashSet<>();
    Derivation<TK,FV> goalHyp=null;
    for (    Derivation<TK,FV> node : latticePath) {
      if (goalHyp == null) {
        goalHyp=node;
        continue;
      }
      withDTUs=withDTUs || node.rule.abstractRule instanceof DTURule;
      goalHyp=withDTUs ? new DTUHypothesis<>(sourceInputId,node.rule,goalHyp.length,goalHyp,node,featurizer,scorer,heuristic,seenOptions,outputSpace) : new Derivation<>(sourceInputId,node.rule,goalHyp.length,goalHyp,featurizer,scorer,heuristic,outputSpace);
    }
    if (goalHyp == null || goalHyp.featurizable == null) {
      logger.warn("Input {}: null hypothesis encountered. Decoder failed.",sourceInputId);
      return null;
    }
    if (withDTUs) {
      DTUHypothesis<TK,FV> dtuHyp=(DTUHypothesis<TK,FV>)goalHyp;
      if (!dtuHyp.isDone() || dtuHyp.hasExpired())       logger.warn("Option not complete({},{}): {}",translations.size(),dtuHyp.hasExpired(),goalHyp);
    }
    RichTranslation<TK,FV> t=new RichTranslation<>(goalHyp.featurizable,goalHyp.score,FeatureValues.combine(goalHyp),nbestId++);
    translations.add(t);
    if (translations.size() >= size)     break;
  }
  Collections.sort(translations,translationComparator);
  logger.info("Input {}: nbest #extracted {} max-agenda-size {}",sourceInputId,numExtracted,latticeDecoder.maxAgendaSize);
  return translations;
}

private List < RichTranslation < TK , FV > > standardNbest ( Beam < Derivation < TK , FV > > beam , RecombinationHistory < Derivation < TK , FV > > recombinationHistory , InputProperties sourceInputProperties , int sourceInputId , List < Sequence < TK > > targets , OutputSpace < TK , FV > outputSpace , int size , boolean distinct ) { List < Derivation < TK , FV > > goalStates = new ArrayList < > ( beam . size ( ) ) ; for ( Derivation < TK , FV > derivation : beam ) goalStates . add ( derivation ) ; final StateLatticeDecoder < Derivation < TK , FV > > latticeDecoder = new StateLatticeDecoder < > ( goalStates , recombinationHistory ) ; final boolean prefixDecoding = sourceInputProperties . containsKey ( InputProperty . TargetPrefix ) ; final boolean prefixDiversity = distinct && prefixDecoding ; final Sequence < TK > prefix = prefixDecoding ? targets . get ( 0 ) : null ; final Set < Sequence < TK > > distinctSurfaceTranslations = distinct ? new HashSet < > ( size ) : null ; final List < RichTranslation < TK , FV > > translations = new ArrayList < > ( size ) ; int numExtracted = 0 ; long nbestId = 0 ; for ( List < Derivation < TK , FV > > latticePath : latticeDecoder ) { ++ numExtracted ; if ( numExtracted > MAX_POPPED_ITEMS ) break ; if ( distinct ) { Sequence < TK > pathTarget = extractTarget ( latticePath ) ; if ( prefixDiversity ) { int start = prefix . size ( ) ; int end = Math . min ( pathTarget . size ( ) , prefix . size ( ) + PREFIX_DIVERSITY_SIZE ) ; if ( start < end ) pathTarget = pathTarget . subsequence ( start , end ) ; } if ( distinctSurfaceTranslations . contains ( pathTarget ) ) continue ; distinctSurfaceTranslations . add ( pathTarget ) ; } boolean withDTUs = false ; final Set < Rule < TK > > seenOptions = new HashSet < > ( ) ; Derivation < TK , FV > goalHyp = null ; for ( Derivation < TK , FV > node : latticePath ) { if ( goalHyp == null ) { goalHyp = node ; continue ; } withDTUs = withDTUs || node . rule . abstractRule instanceof DTURule ; goalHyp = withDTUs ? new DTUHypothesis < > ( sourceInputId , node . rule , goalHyp . length , goalHyp , node , featurizer , scorer , heuristic , seenOptions , outputSpace ) : new Derivation < > ( sourceInputId , node . rule , goalHyp . length , goalHyp , featurizer , scorer , heuristic , outputSpace ) ; } if ( goalHyp == null || goalHyp . featurizable == null ) { logger . warn ( "Input {}: null hypothesis encountered. Decoder failed." , sourceInputId ) ; return null ; } if ( withDTUs ) { DTUHypothesis < TK , FV > dtuHyp = ( DTUHypothesis < TK , FV > ) goalHyp ; if ( ! dtuHyp . isDone ( ) || dtuHyp . hasExpired ( ) ) logger . warn ( "Option not complete({},{}): {}" , translations . size ( ) , dtuHyp . hasExpired ( ) , goalHyp ) ; } RichTranslation < TK , FV > t = new RichTranslation < > ( goalHyp . featurizable , goalHyp . score , FeatureValues . combine ( goalHyp ) , nbestId ++ ) ; translations . add ( t ) ; if ( translations . size ( ) >= size ) break ; } Collections . sort ( translations , translationComparator ) ; logger . info ( "Input {}: nbest #extracted {} max-agenda-size {}" , sourceInputId , numExtracted , latticeDecoder . maxAgendaSize ) ; return translations ; }
standard a * search through lattice .
