src/joshua/decoder/phrase/Stacks.java - joshua - Git at Google

 package joshua.decoder.phrase;

 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;

 import joshua.corpus.Span;
 import joshua.decoder.JoshuaConfiguration;
 import joshua.decoder.chart_parser.ComputeNodeResult;
 import joshua.decoder.ff.FeatureFunction;
 import joshua.decoder.ff.tm.AbstractGrammar;
 import joshua.decoder.ff.tm.Grammar;
 import joshua.decoder.hypergraph.HGNode;
 import joshua.decoder.hypergraph.HyperEdge;
 import joshua.decoder.hypergraph.HyperGraph;
 import joshua.decoder.segment_file.Sentence;

 public class Stacks {

   // The list of stacks, grouped according to number of source words covered
   private List<Stack> stacks;

   // The end state
   private Hypothesis end;

   List<FeatureFunction> featureFunctions;

   private Sentence sentence;

   private PhraseChart chart;

   private JoshuaConfiguration config;

   /**
    *
    *
    * @param context
    * @param chart
    * @param featureFunctions
    */
 //  public Stacks(Context context, Chart chart, List<FeatureFunction> featureFunctions) {
   public Stacks(Sentence sentence, List<FeatureFunction> featureFunctions, Grammar[] grammars,
       JoshuaConfiguration config) {

     this.sentence = sentence;
     this.featureFunctions = featureFunctions;
     this.config = config;

     int num_phrase_tables = 0;
     for (int i = 0; i < grammars.length; i++)
       if (grammars[i] instanceof PhraseTable)
         ++num_phrase_tables;

     PhraseTable[] phraseTables = new PhraseTable[num_phrase_tables + 2];
     for (int i = 0, j = 0; i < grammars.length; i++)
       if (grammars[i] instanceof PhraseTable)
         phraseTables[j++] = (PhraseTable) grammars[i];

     phraseTables[phraseTables.length - 2] = new PhraseTable("null", config, featureFunctions);
     phraseTables[phraseTables.length - 2].addEOSRule();

     phraseTables[phraseTables.length - 1] = new PhraseTable("oov", config, featureFunctions);
     AbstractGrammar.addOOVRules(phraseTables[phraseTables.length - 1], sentence.intLattice(), featureFunctions, config.true_oovs_only);

     this.chart = new PhraseChart(phraseTables, featureFunctions, sentence, config.num_translation_options);
   }


   /**
    * The main algorithm. Returns a hypergraph representing the search space.
    *
    * @return
    */
   public HyperGraph search() {

     long startTime = System.currentTimeMillis();

     Future future = new Future(chart);
     stacks = new ArrayList<Stack>();

     // Reservation is critical because pointers to Hypothesis objects are retained as history.
     //stacks.reserve(chart.SentenceLength() + 2 /* begin/end of sentence */);
     stacks.clear();
     stacks.add(null);
     for (int i = 1; i <= sentence.length(); i++)
       stacks.add(new Stack());

     // Initialize root hypothesis with <s> context and future cost for everything.
     ComputeNodeResult result = new ComputeNodeResult(this.featureFunctions, Hypothesis.BEGIN_RULE,
         null, -1, 1, null, this.sentence);
     stacks.get(1).add(new Hypothesis(result.getDPStates(), future.Full()));

     // Decode with increasing numbers of source words.
     for (int source_words = 2; source_words <= sentence.length(); ++source_words) {
       // A vertex represents the root of a trie, e.g., bundled translations of the same source phrase
       HashMap<Span, Vertex> vertices = new HashMap<Span, Vertex>();
       // Iterate over stacks to continue from.
       for (int from_stack = source_words - Math.min(source_words - 1, chart.MaxSourcePhraseLength());
            from_stack < source_words;
            ++from_stack) {
         int phrase_length = source_words - from_stack;

 //        System.err.println(String.format("\n  WORDS %d (STACK %d phrase_length %d)", source_words, from_stack, phrase_length));

         // Iterate over antecedents in this stack.
         for (Hypothesis ant : stacks.get(from_stack)) {
 //          System.err.println(String.format("  WORDS %d ANT %s", source_words, ant));
           Coverage coverage = ant.GetCoverage();
           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;

           // We can always go from first_zero because it doesn't create a reordering gap.
           do {

             // Don't append </s> until the end
             if (begin == sentence.length() - 1 && source_words != sentence.length())
               continue;

             TargetPhrases phrases = chart.getRange(begin, begin + phrase_length);

             if (phrases == null || !coverage.compatible(begin, begin + phrase_length))
               continue;

 //            System.err.println(String.format("  Applying %d target phrases over [%d,%d]", phrases.size(), begin, begin + phrase_length));

             // TODO: could also compute some number of features here (e.g., non-LM ones)
             // float score_delta = context.GetScorer().transition(ant, phrases, begin, begin + phrase_length);

             // Future costs: remove span to be filled.
             float score_delta = future.Change(coverage, begin, begin + phrase_length);

             Span span = new Span(begin, begin + phrase_length);
             if (! vertices.containsKey(span))
               vertices.put(span, new Vertex());

             /* This associates with each span a set of hypotheses that can be extended by
              * phrases from that span. The hypotheses are wrapped in HypoState objects, which
              * augment the hypothesis score with a future cost.
              */
             vertices.get(span).add(new HypoState(ant, score_delta));

             // Enforce the reordering limit on later iterations.

           } while (++begin <= last_begin);
         }
       }

       /* At this point, every vertex contains a list of all existing hypotheses that the target
        * phrases in that vertex could extend. Now we need to create the search object, which
        * implements cube pruning. There are up to O(n^2) cubes, n the size of the current stack,
        * one cube each over each span of the input. Each "cube" has two dimensions: one representing
        * the target phrases over the span, and one representing all of these incoming hypotheses.
        * We seed the chart with the best item in each cube, and then repeatedly pop and extend.
        */

       EdgeGenerator gen = new EdgeGenerator(sentence, featureFunctions, config);
 //      System.err.println(String.format("\nBuilding cube-pruning chart for %d words", source_words));
       for (Span pair : vertices.keySet()) {
         Vertex hypos = vertices.get(pair);
         if (hypos.isEmpty())
           continue;
         // Sorts the hypotheses, since we now know that we're done adding them
         hypos.finish();

         TargetPhrases phrases = chart.getRange(pair.start, pair.end);

 //        System.err.println(String.format("  Span %s hypotheses %s phrases %s", pair, hypos.size(), phrases.size()));

         Candidate cand = new Candidate(hypos, phrases, pair);
         gen.AddCandidate(cand);
       }

       Stack stack = stacks.get(source_words);
       EdgeOutput output = new EdgeOutput(stack);
       gen.Search(output);
     }

     System.err.println(String.format("[%d] Search took %.3f seconds", sentence.id(),
         (System.currentTimeMillis() - startTime) / 1000.0f));

     //    System.err.println("Stack(): END: " + end);
     return createGoalNode();
   }

   private HyperGraph createGoalNode() {
     Stack lastStack = stacks.get(sentence.length());

     for (Hypothesis hyp: lastStack) {
       float score = hyp.getScore();
       List<HGNode> tailNodes = new ArrayList<HGNode>();
       tailNodes.add(hyp);

       float finalTransitionScore = ComputeNodeResult.computeFinalCost(featureFunctions, tailNodes, 0, sentence.length(), null, sentence.id());

       if (null == this.end)
         this.end = new Hypothesis(null, score + finalTransitionScore, hyp, sentence.length(), null);

       HyperEdge edge = new HyperEdge(null, score + finalTransitionScore, finalTransitionScore, tailNodes, null);
       end.addHyperedgeInNode(edge);
     }

     this.end = lastStack.isEmpty() ? null : lastStack.get(0);

     return new HyperGraph(end, -1, -1, this.sentence);
   }


   /**
    * Creates a new hypothesis and adds it to the stack.
    *
    * Duplication-checking is done elsewhere. For regular decoding, an {@link EdgeOutput} keeps
    * track of added edges and combines the last item, after this call completes.
    *
    * @param complete the candidate used to build the hypothesis
    * @param out the stack to place it on
    */
   public static void AppendToStack(Candidate complete, Stack out) {

     Hypothesis h = new Hypothesis(complete);
     out.add(h);

     /*
     out.add(new Hypothesis(0, // complete.CompletedState().right,
           complete.GetScore(), // TODO: call scorer to adjust for last of lexro?
           (Hypothesis)(complete.NT()[0].End().get()),
           source_range.start,
           source_range.end,
           (Phrase)complete.NT()[1].End().get()));
      */
 //    out.add(h);
   }
 }
	package joshua.decoder.phrase;

	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.List;

	import joshua.corpus.Span;
	import joshua.decoder.JoshuaConfiguration;
	import joshua.decoder.chart_parser.ComputeNodeResult;
	import joshua.decoder.ff.FeatureFunction;
	import joshua.decoder.ff.tm.AbstractGrammar;
	import joshua.decoder.ff.tm.Grammar;
	import joshua.decoder.hypergraph.HGNode;
	import joshua.decoder.hypergraph.HyperEdge;
	import joshua.decoder.hypergraph.HyperGraph;
	import joshua.decoder.segment_file.Sentence;

	public class Stacks {

	// The list of stacks, grouped according to number of source words covered
	private List<Stack> stacks;

	// The end state
	private Hypothesis end;

	List<FeatureFunction> featureFunctions;

	private Sentence sentence;

	private PhraseChart chart;

	private JoshuaConfiguration config;

	/**
	*
	*
	* @param context
	* @param chart
	* @param featureFunctions
	*/
	// public Stacks(Context context, Chart chart, List<FeatureFunction> featureFunctions) {
	public Stacks(Sentence sentence, List<FeatureFunction> featureFunctions, Grammar[] grammars,
	JoshuaConfiguration config) {

	this.sentence = sentence;
	this.featureFunctions = featureFunctions;
	this.config = config;

	int num_phrase_tables = 0;
	for (int i = 0; i < grammars.length; i++)
	if (grammars[i] instanceof PhraseTable)
	++num_phrase_tables;

	PhraseTable[] phraseTables = new PhraseTable[num_phrase_tables + 2];
	for (int i = 0, j = 0; i < grammars.length; i++)
	if (grammars[i] instanceof PhraseTable)
	phraseTables[j++] = (PhraseTable) grammars[i];

	phraseTables[phraseTables.length - 2] = new PhraseTable("null", config, featureFunctions);
	phraseTables[phraseTables.length - 2].addEOSRule();

	phraseTables[phraseTables.length - 1] = new PhraseTable("oov", config, featureFunctions);
	AbstractGrammar.addOOVRules(phraseTables[phraseTables.length - 1], sentence.intLattice(), featureFunctions, config.true_oovs_only);

	this.chart = new PhraseChart(phraseTables, featureFunctions, sentence, config.num_translation_options);
	}


	/**
	* The main algorithm. Returns a hypergraph representing the search space.
	*
	* @return
	*/
	public HyperGraph search() {

	long startTime = System.currentTimeMillis();

	Future future = new Future(chart);
	stacks = new ArrayList<Stack>();

	// Reservation is critical because pointers to Hypothesis objects are retained as history.
	//stacks.reserve(chart.SentenceLength() + 2 /* begin/end of sentence */);
	stacks.clear();
	stacks.add(null);
	for (int i = 1; i <= sentence.length(); i++)
	stacks.add(new Stack());

	// Initialize root hypothesis with <s> context and future cost for everything.
	ComputeNodeResult result = new ComputeNodeResult(this.featureFunctions, Hypothesis.BEGIN_RULE,
	null, -1, 1, null, this.sentence);
	stacks.get(1).add(new Hypothesis(result.getDPStates(), future.Full()));

	// Decode with increasing numbers of source words.
	for (int source_words = 2; source_words <= sentence.length(); ++source_words) {
	// A vertex represents the root of a trie, e.g., bundled translations of the same source phrase
	HashMap<Span, Vertex> vertices = new HashMap<Span, Vertex>();
	// Iterate over stacks to continue from.
	for (int from_stack = source_words - Math.min(source_words - 1, chart.MaxSourcePhraseLength());
	from_stack < source_words;
	++from_stack) {
	int phrase_length = source_words - from_stack;

	// System.err.println(String.format("\n WORDS %d (STACK %d phrase_length %d)", source_words, from_stack, phrase_length));

	// Iterate over antecedents in this stack.
	for (Hypothesis ant : stacks.get(from_stack)) {
	// System.err.println(String.format(" WORDS %d ANT %s", source_words, ant));
	Coverage coverage = ant.GetCoverage();
	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;

	// We can always go from first_zero because it doesn't create a reordering gap.
	do {

	// Don't append </s> until the end
	if (begin == sentence.length() - 1 && source_words != sentence.length())
	continue;

	TargetPhrases phrases = chart.getRange(begin, begin + phrase_length);

	if (phrases == null \|\| !coverage.compatible(begin, begin + phrase_length))
	continue;

	// System.err.println(String.format(" Applying %d target phrases over [%d,%d]", phrases.size(), begin, begin + phrase_length));

	// TODO: could also compute some number of features here (e.g., non-LM ones)
	// float score_delta = context.GetScorer().transition(ant, phrases, begin, begin + phrase_length);

	// Future costs: remove span to be filled.
	float score_delta = future.Change(coverage, begin, begin + phrase_length);

	Span span = new Span(begin, begin + phrase_length);
	if (! vertices.containsKey(span))
	vertices.put(span, new Vertex());

	/* This associates with each span a set of hypotheses that can be extended by
	* phrases from that span. The hypotheses are wrapped in HypoState objects, which
	* augment the hypothesis score with a future cost.
	*/
	vertices.get(span).add(new HypoState(ant, score_delta));

	// Enforce the reordering limit on later iterations.

	} while (++begin <= last_begin);
	}
	}

	/* At this point, every vertex contains a list of all existing hypotheses that the target
	* phrases in that vertex could extend. Now we need to create the search object, which
	* implements cube pruning. There are up to O(n^2) cubes, n the size of the current stack,
	* one cube each over each span of the input. Each "cube" has two dimensions: one representing
	* the target phrases over the span, and one representing all of these incoming hypotheses.
	* We seed the chart with the best item in each cube, and then repeatedly pop and extend.
	*/

	EdgeGenerator gen = new EdgeGenerator(sentence, featureFunctions, config);
	// System.err.println(String.format("\nBuilding cube-pruning chart for %d words", source_words));
	for (Span pair : vertices.keySet()) {
	Vertex hypos = vertices.get(pair);
	if (hypos.isEmpty())
	continue;
	// Sorts the hypotheses, since we now know that we're done adding them
	hypos.finish();

	TargetPhrases phrases = chart.getRange(pair.start, pair.end);

	// System.err.println(String.format(" Span %s hypotheses %s phrases %s", pair, hypos.size(), phrases.size()));

	Candidate cand = new Candidate(hypos, phrases, pair);
	gen.AddCandidate(cand);
	}

	Stack stack = stacks.get(source_words);
	EdgeOutput output = new EdgeOutput(stack);
	gen.Search(output);
	}

	System.err.println(String.format("[%d] Search took %.3f seconds", sentence.id(),
	(System.currentTimeMillis() - startTime) / 1000.0f));

	// System.err.println("Stack(): END: " + end);
	return createGoalNode();
	}

	private HyperGraph createGoalNode() {
	Stack lastStack = stacks.get(sentence.length());

	for (Hypothesis hyp: lastStack) {
	float score = hyp.getScore();
	List<HGNode> tailNodes = new ArrayList<HGNode>();
	tailNodes.add(hyp);

	float finalTransitionScore = ComputeNodeResult.computeFinalCost(featureFunctions, tailNodes, 0, sentence.length(), null, sentence.id());

	if (null == this.end)
	this.end = new Hypothesis(null, score + finalTransitionScore, hyp, sentence.length(), null);

	HyperEdge edge = new HyperEdge(null, score + finalTransitionScore, finalTransitionScore, tailNodes, null);
	end.addHyperedgeInNode(edge);
	}

	this.end = lastStack.isEmpty() ? null : lastStack.get(0);

	return new HyperGraph(end, -1, -1, this.sentence);
	}


	/**
	* Creates a new hypothesis and adds it to the stack.
	*
	* Duplication-checking is done elsewhere. For regular decoding, an {@link EdgeOutput} keeps
	* track of added edges and combines the last item, after this call completes.
	*
	* @param complete the candidate used to build the hypothesis
	* @param out the stack to place it on
	*/
	public static void AppendToStack(Candidate complete, Stack out) {

	Hypothesis h = new Hypothesis(complete);
	out.add(h);

	/*
	out.add(new Hypothesis(0, // complete.CompletedState().right,
	complete.GetScore(), // TODO: call scorer to adjust for last of lexro?
	(Hypothesis)(complete.NT()[0].End().get()),
	source_range.start,
	source_range.end,
	(Phrase)complete.NT()[1].End().get()));
	*/
	// out.add(h);
	}
	}