LexicalReorderingState* HierarchicalReorderingForwardState::Expand(const TranslationOption& topt, Scores& scores) const {
  const LexicalReorderingConfiguration::ModelType modelType = m_configuration.GetModelType();
  const WordsRange currWordsRange = topt.GetSourceWordsRange();
  // keep track of the current coverage ourselves so we don't need the hypothesis
  WordsBitmap coverage = m_coverage;
  coverage.SetValue(currWordsRange.GetStartPos(), currWordsRange.GetEndPos(), true);
  
  ReorderingType reoType;
  
  if (m_first) {
      ClearScores(scores);
  } else {
    if (modelType == LexicalReorderingConfiguration::MSD) {
      reoType = GetOrientationTypeMSD(currWordsRange, coverage);
    } else if (modelType == LexicalReorderingConfiguration::MSLR) {
      reoType = GetOrientationTypeMSLR(currWordsRange, coverage);
    } else if (modelType == LexicalReorderingConfiguration::Monotonic) {
      reoType = GetOrientationTypeMonotonic(currWordsRange, coverage);
    } else {
      reoType = GetOrientationTypeLeftRight(currWordsRange, coverage);
    }
  
    CopyScores(scores, topt, reoType);
  }
  
  return new HierarchicalReorderingForwardState(this, topt);
}

/*
 * Given a previous state, compute Bleu score for the updated state with an additional target
 * phrase translated.
 */
FFState* BleuScoreFeature::Evaluate(const Hypothesis& cur_hypo,
                                    const FFState* prev_state,
                                    ScoreComponentCollection* accumulator) const
{
    if (!m_enabled) return new BleuScoreState();

    NGrams::const_iterator reference_ngrams_iter;
    const BleuScoreState& ps = dynamic_cast<const BleuScoreState&>(*prev_state);
    BleuScoreState* new_state = new BleuScoreState(ps);

    float old_bleu, new_bleu;
    size_t num_new_words, ctx_start_idx, ctx_end_idx;

    // Calculate old bleu;
    old_bleu = CalculateBleu(new_state);

    // Get context and append new words.
    num_new_words = cur_hypo.GetCurrTargetLength();
    if (num_new_words == 0) {
        return new_state;
    }

    Phrase new_words = ps.m_words;
    new_words.Append(cur_hypo.GetCurrTargetPhrase());
    //cerr << "NW: " << new_words << endl;

    // get ngram matches for new words
    GetNgramMatchCounts(new_words,
                        m_cur_ref_ngrams,
                        new_state->m_ngram_counts,
                        new_state->m_ngram_matches,
                        new_state->m_words.GetSize()); // number of words in previous states

    // Update state variables
    ctx_end_idx = new_words.GetSize()-1;
    size_t bleu_context_length = BleuScoreState::bleu_order -1;
    if (ctx_end_idx > bleu_context_length) {
        ctx_start_idx = ctx_end_idx - bleu_context_length;
    } else {
        ctx_start_idx = 0;
    }

    WordsBitmap coverageVector = cur_hypo.GetWordsBitmap();
    new_state->m_source_length = coverageVector.GetNumWordsCovered();

    new_state->m_words = new_words.GetSubString(WordsRange(ctx_start_idx,
                         ctx_end_idx));
    new_state->m_target_length += cur_hypo.GetCurrTargetLength();

    // we need a scaled reference length to compare the current target phrase to the corresponding reference phrase
    new_state->m_scaled_ref_length = m_cur_ref_length *
                                     ((float)coverageVector.GetNumWordsCovered()/coverageVector.GetSize());

    // Calculate new bleu.
    new_bleu = CalculateBleu(new_state);

    // Set score to new Bleu score
    accumulator->PlusEquals(this, new_bleu - old_bleu);
    return new_state;
}

LexicalReorderingState::ReorderingType HierarchicalReorderingForwardState::GetOrientationTypeMSD(WordsRange currRange, WordsBitmap coverage) const {
  if (currRange.GetStartPos() > m_prevRange.GetEndPos() &&
      (!coverage.GetValue(m_prevRange.GetEndPos()+1) || currRange.GetStartPos() == m_prevRange.GetEndPos()+1)) {
      return M;
  } else if (currRange.GetEndPos() < m_prevRange.GetStartPos() &&
             (!coverage.GetValue(m_prevRange.GetStartPos()-1) || currRange.GetEndPos() == m_prevRange.GetStartPos()-1)) {
      return S;
  }
  return D;
}

float SquareMatrix::CalcFutureScore2( WordsBitmap const &bitmap, size_t startPos, size_t endPos ) const
{
  const size_t notInGap= numeric_limits<size_t>::max();
  float futureScore = 0.0f;
  size_t startGap = bitmap.GetFirstGapPos();
  if (startGap == NOT_FOUND) return futureScore; // everything filled

  // start loop at first gap
  size_t startLoop = startGap+1;
  if (startPos == startGap) { // unless covered by phrase
    startGap = notInGap;
    startLoop = endPos+1; // -> postpone start
  }

  size_t lastCovered = bitmap.GetLastPos();
  if (endPos > lastCovered || lastCovered == NOT_FOUND) lastCovered = endPos;

  for(size_t currPos = startLoop; currPos <= lastCovered ; currPos++) {
    // start of a new gap?
    if(startGap == notInGap && bitmap.GetValue(currPos) == false && (currPos < startPos || currPos > endPos)) {
      startGap = currPos;
    }
    // end of a gap?
    else if(startGap != notInGap && (bitmap.GetValue(currPos) == true || (startPos <= currPos && currPos <= endPos))) {
      futureScore += GetScore(startGap, currPos - 1);
      startGap = notInGap;
    }
  }
  // coverage ending with gap?
  if (lastCovered != bitmap.GetSize() - 1) {
    futureScore += GetScore(lastCovered+1, bitmap.GetSize() - 1);
  }

  return futureScore;
}

float SquareMatrix::CalcFutureScore( WordsBitmap const &bitmap ) const
{
  const size_t notInGap= numeric_limits<size_t>::max();
  size_t startGap = notInGap;
  float futureScore = 0.0f;
  for(size_t currPos = 0 ; currPos < bitmap.GetSize() ; currPos++) {
    // start of a new gap?
    if(bitmap.GetValue(currPos) == false && startGap == notInGap) {
      startGap = currPos;
    }
    // end of a gap?
    else if(bitmap.GetValue(currPos) == true && startGap != notInGap) {
      futureScore += GetScore(startGap, currPos - 1);
      startGap = notInGap;
    }
  }
  // coverage ending with gap?
  if (startGap != notInGap) {
    futureScore += GetScore(startGap, bitmap.GetSize() - 1);
  }

  return futureScore;
}

bool SearchCubePruning::CheckDistortion(const WordsBitmap &hypoBitmap, const WordsRange &range) const
{
  // since we check for reordering limits, its good to have that limit handy
  int maxDistortion = StaticData::Instance().GetMaxDistortion();

  // if there are reordering limits, make sure it is not violated
  // the coverage bitmap is handy here (and the position of the first gap)
  const size_t	hypoFirstGapPos	= hypoBitmap.GetFirstGapPos()
                                  , startPos				= range.GetStartPos()
                                      , endPos					= range.GetEndPos();

  // if reordering constraints are used (--monotone-at-punctuation or xml), check if passes all
  if (! m_source.GetReorderingConstraint().Check( hypoBitmap, startPos, endPos ) ) {
    return false;
  }

  // no limit of reordering: no problem
  if (maxDistortion < 0) {
    return true;
  }

  bool leftMostEdge = (hypoFirstGapPos == startPos);
  // any length extension is okay if starting at left-most edge
  if (leftMostEdge) {
    return true;
  }
  // starting somewhere other than left-most edge, use caution
  // the basic idea is this: we would like to translate a phrase starting
  // from a position further right than the left-most open gap. The
  // distortion penalty for the following phrase will be computed relative
  // to the ending position of the current extension, so we ask now what
  // its maximum value will be (which will always be the value of the
  // hypothesis starting at the left-most edge).  If this vlaue is than
  // the distortion limit, we don't allow this extension to be made.
  WordsRange bestNextExtension(hypoFirstGapPos, hypoFirstGapPos);
  int required_distortion =
    m_source.ComputeDistortionDistance(range, bestNextExtension);

  if (required_distortion > maxDistortion) {
    return false;
  }
  return true;
}

//! check if the current hypothesis extension violates reordering constraints
bool ReorderingConstraint::Check( const WordsBitmap &bitmap, size_t startPos, size_t endPos ) const
{
  // nothing to be checked, we are done
  if (! IsActive() ) return true;

  VERBOSE(3,"CHECK " << bitmap << " " << startPos << "-" << endPos);

  // check walls
  size_t firstGapPos = bitmap.GetFirstGapPos();
  // filling first gap -> no wall violation possible
  if (firstGapPos != startPos) {
    // if there is a wall before the last word,
    // we created a gap while moving through wall
    // -> violation
    for( size_t pos = firstGapPos; pos < endPos; pos++ ) {
      if( GetWall( pos ) ) {
        VERBOSE(3," hitting wall " << pos << std::endl);
        return false;
      }
    }
  }

  // monotone -> no violation possible
  size_t lastPos = bitmap.GetLastPos();
  if ((lastPos == NOT_FOUND && startPos == 0) || // nothing translated
      (firstGapPos > lastPos &&  // no gaps
       firstGapPos == startPos)) { // translating first empty word
    VERBOSE(3," montone, fine." << std::endl);
    return true;
  }

  // check zones
  for(size_t z = 0; z < m_zone.size(); z++ ) {
    const size_t startZone = m_zone[z][0];
    const size_t endZone = m_zone[z][1];

    // fine, if translation has not reached zone yet and phrase outside zone
    if (lastPos < startZone && ( endPos < startZone || startPos > endZone ) ) {
      continue;
    }

    // already completely translated zone, no violations possible
    if (firstGapPos > endZone) {
      continue;
    }

    // some words are translated beyond the start
    // let's look closer if some are in the zone
    size_t numWordsInZoneTranslated = 0;
    if (lastPos >= startZone) {
      for(size_t pos = startZone; pos <= endZone; pos++ ) {
        if( bitmap.GetValue( pos ) ) {
          numWordsInZoneTranslated++;
        }
      }
    }

    // all words in zone translated, no violation possible
    if (numWordsInZoneTranslated == endZone-startZone+1) {
      continue;
    }

    // flag if this is an active zone
    bool activeZone = (numWordsInZoneTranslated > 0);

    // fine, if zone completely untranslated and phrase outside zone
    if (!activeZone && ( endPos < startZone || startPos > endZone ) ) {
      continue;
    }

    // violation, if phrase completely outside active zone
    if (activeZone && ( endPos < startZone || startPos > endZone ) ) {
      VERBOSE(3," outside active zone" << std::endl);
      return false;
    }

    // ok, this is what we know now:
    // * the phrase is in the zone (at least partially)
    // * either zone is already active, or it becomes active now


    // check, if we are setting us up for a dead end due to distortion limits
    int distortionLimit = StaticData::Instance().GetMaxDistortion();
    if (startPos != firstGapPos && endZone-firstGapPos >= distortionLimit) {
      VERBOSE(3," dead end due to distortion limit" << std::endl);
      return false;
    }

    // let us check on phrases that are partially outside

    // phrase overlaps at the beginning, always ok
    if (startPos <= startZone) {
      continue;
    }

    // phrase goes beyond end, has to fill zone completely
    if (endPos > endZone) {
      if (endZone-startPos+1 < // num. words filled in by phrase
          endZone-startZone+1-numWordsInZoneTranslated) { // num. untranslated
//.........这里部分代码省略.........

FFState* OpSequenceModel::Evaluate(
  const Hypothesis& cur_hypo,
  const FFState* prev_state,
  ScoreComponentCollection* accumulator) const
{
  const TargetPhrase &target = cur_hypo.GetCurrTargetPhrase();
  const WordsBitmap &bitmap = cur_hypo.GetWordsBitmap();
  WordsBitmap myBitmap = bitmap;
  const Manager &manager = cur_hypo.GetManager();
  const InputType &source = manager.GetSource();
  const Sentence &sourceSentence = static_cast<const Sentence&>(source);
  osmHypothesis obj;
  vector <string> mySourcePhrase;
  vector <string> myTargetPhrase;
  vector<float> scores;


  //target.GetWord(0)

  //cerr << target <<" --- "<<target.GetSourcePhrase()<< endl;  // English ...

  //cerr << align << endl;   // Alignments ...
  //cerr << cur_hypo.GetCurrSourceWordsRange() << endl;

  //cerr << source <<endl;

// int a = sourceRange.GetStartPos();
// cerr << source.GetWord(a);
  //cerr <<a<<endl;

  //const Sentence &sentence = static_cast<const Sentence&>(curr_hypo.GetManager().GetSource());


  const WordsRange & sourceRange = cur_hypo.GetCurrSourceWordsRange();
  int startIndex  = sourceRange.GetStartPos();
  int endIndex = sourceRange.GetEndPos();
  const AlignmentInfo &align = cur_hypo.GetCurrTargetPhrase().GetAlignTerm();
  osmState * statePtr;

  vector <int> alignments;



  AlignmentInfo::const_iterator iter;

  for (iter = align.begin(); iter != align.end(); ++iter) {
    //cerr << iter->first << "----" << iter->second << " ";
    alignments.push_back(iter->first);
    alignments.push_back(iter->second);
  }


  //cerr<<bitmap<<endl;
  //cerr<<startIndex<<" "<<endIndex<<endl;


  for (int i = startIndex; i <= endIndex; i++) {
    myBitmap.SetValue(i,0); // resetting coverage of this phrase ...
    mySourcePhrase.push_back(source.GetWord(i).GetFactor(sFactor)->GetString().as_string());
    // cerr<<mySourcePhrase[i]<<endl;
  }

  for (int i = 0; i < target.GetSize(); i++) {

    if (target.GetWord(i).IsOOV() && sFactor == 0 && tFactor == 0)
      myTargetPhrase.push_back("_TRANS_SLF_");
    else
      myTargetPhrase.push_back(target.GetWord(i).GetFactor(tFactor)->GetString().as_string());

  }


  //cerr<<myBitmap<<endl;

  obj.setState(prev_state);
  obj.constructCepts(alignments,startIndex,endIndex,target.GetSize());
  obj.setPhrases(mySourcePhrase , myTargetPhrase);
  obj.computeOSMFeature(startIndex,myBitmap);
  obj.calculateOSMProb(*OSM);
  obj.populateScores(scores,numFeatures);
  //obj.print();

  /*
    if (bitmap.GetFirstGapPos() == NOT_FOUND)
    {

      int xx;
  	 cerr<<bitmap<<endl;
  	 int a = bitmap.GetFirstGapPos();
  	 obj.print();
      cin>>xx;
    }
    */



  accumulator->PlusEquals(this, scores);

  return obj.saveState();

//.........这里部分代码省略.........

void osmHypothesis :: generateOperations(int & startIndex , int j1 , int contFlag , WordsBitmap & coverageVector , string english , string german , set <int> & targetNullWords , vector <string> & currF)
{
	
	int gFlag = 0;
	int gp = 0; 	
	int ans;
	

		if ( j < j1) // j1 is the index of the source word we are about to generate ...
		{
			//if(coverageVector[j]==0) // if source word at j is not generated yet ...
			if(coverageVector.GetValue(j)==0) // if source word at j is not generated yet ...
			{
				operations.push_back("_INS_GAP_");
				gFlag++;
				gap[j]="Unfilled";
			}
			if (j == E)
			{
				j = j1;
			}
			else
			{
				operations.push_back("_JMP_FWD_");
				j=E;
			}
		}
		
		if (j1 < j)
		{
			// if(j < E && coverageVector[j]==0)
			if(j < E && coverageVector.GetValue(j)==0)
			{
				operations.push_back("_INS_GAP_");
				gFlag++;
				gap[j]="Unfilled";
			}

			j=closestGap(gap,j1,gp);
			operations.push_back("_JMP_BCK_"+ intToString(gp));

			//cout<<"I am j "<<j<<endl;
			//cout<<"I am j1 "<<j1<<endl;

			if(j==j1)
			  gap[j]="Filled";
		}

		if (j < j1)
		{
			operations.push_back("_INS_GAP_");
			gap[j] = "Unfilled";
			gFlag++;
			j=j1;
		}

		if(contFlag == 0) // First words of the multi-word cept ...
		{

			if(english == "_TRANS_SLF_") // Unknown word ...
			{
				operations.push_back("_TRANS_SLF_");
			}
			else
			{
				operations.push_back("_TRANS_" + english + "_TO_" + german);
			}

			//ans = firstOpenGap(coverageVector);
			ans = coverageVector.GetFirstGapPos();
		
			if (ans != -1)
		 		gapWidth += j - ans;

		}
		else if (contFlag == 2)
		{

			operations.push_back("_INS_" + german);
			ans = coverageVector.GetFirstGapPos();

			if (ans != -1)
				gapWidth += j - ans;
			deletionCount++;
		}
		else
		{
			operations.push_back("_CONT_CEPT_");
		}

		//coverageVector[j]=1;
		coverageVector.SetValue(j,1);
		j+=1;
		
		if(E<j)
		  E=j;

	if (gFlag > 0)
		gapCount++;

//.........这里部分代码省略.........