You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@joshua.apache.org by le...@apache.org on 2016/05/16 06:26:27 UTC
[11/66] [partial] incubator-joshua git commit: JOSHUA-252 Make it
possible to use Maven to build Joshua
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/hypergraph/TrivialInsideOutside.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/hypergraph/TrivialInsideOutside.java b/src/main/java/org/apache/joshua/decoder/hypergraph/TrivialInsideOutside.java
new file mode 100644
index 0000000..f6f164f
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/hypergraph/TrivialInsideOutside.java
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.hypergraph;
+
+/**
+ * @author Zhifei Li, <zh...@gmail.com>
+ * @version $LastChangedDate$
+ */
+
+public class TrivialInsideOutside extends DefaultInsideOutside {
+ // used by inside-outside estimation
+ protected double getHyperedgeLogProb(HyperEdge dt, HGNode parent_it) {
+ return dt.getTransitionLogP(false);// TODO this is very bad in terms of computation
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/hypergraph/ViterbiExtractor.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/hypergraph/ViterbiExtractor.java b/src/main/java/org/apache/joshua/decoder/hypergraph/ViterbiExtractor.java
new file mode 100644
index 0000000..31c8dc0
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/hypergraph/ViterbiExtractor.java
@@ -0,0 +1,162 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.hypergraph;
+
+import static java.util.Collections.emptyList;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import joshua.decoder.ff.FeatureFunction;
+import joshua.decoder.ff.FeatureVector;
+import joshua.decoder.segment_file.Sentence;
+
+/**
+ * @author Zhifei Li, <zh...@gmail.com>
+ * @author Matt Post <po...@cs.jhu.edu>
+ */
+
+public class ViterbiExtractor {
+
+ /**
+ * This function recursively visits the nodes of the Viterbi derivation in a depth-first
+ * traversal, applying the walker to each of the nodes. It provides a more general framework for
+ * implementing operations on a tree.
+ *
+ * @param node the node to start viterbi traversal from
+ * @param walker an implementation of the WalkerFunction interface, to be applied to each node in
+ * the tree
+ * @param nodeIndex the tail node index of the given node. This allows implementations of the
+ * WalkerFunction to associate nonTerminals with the index of node in the outgoing edges
+ * list of tail nodes.
+ */
+ public static void viterbiWalk(
+ final HGNode node,
+ final WalkerFunction walker,
+ final int nodeIndex) {
+ // apply the walking function to the node
+ walker.apply(node, nodeIndex);
+ // recurse on the anterior nodes of the best hyperedge in source order
+ final HyperEdge bestEdge = node.bestHyperedge;
+ final List<HGNode> tailNodes = bestEdge.getTailNodes();
+ if (tailNodes != null) {
+ for (int tailNodeIndex = 0; tailNodeIndex < tailNodes.size(); tailNodeIndex++) {
+ viterbiWalk(tailNodes.get(tailNodeIndex), walker, tailNodeIndex);
+ }
+ }
+ }
+
+ public static void viterbiWalk(final HGNode node, final WalkerFunction walker) {
+ viterbiWalk(node, walker, 0);
+ }
+
+ /**
+ * Returns the Viterbi translation of the Hypergraph (includes sentence markers)
+ */
+ public static String getViterbiString(final HyperGraph hg) {
+ if (hg == null)
+ return "";
+
+ final WalkerFunction viterbiOutputStringWalker = new OutputStringExtractor(false);
+ viterbiWalk(hg.goalNode, viterbiOutputStringWalker);
+ return viterbiOutputStringWalker.toString();
+ }
+
+ /**
+ * Returns the Viterbi feature vector
+ */
+ public static FeatureVector getViterbiFeatures(
+ final HyperGraph hg,
+ final List<FeatureFunction> featureFunctions,
+ final Sentence sentence) {
+ if (hg == null)
+ return new FeatureVector();
+
+ final FeatureVectorExtractor extractor = new FeatureVectorExtractor(
+ featureFunctions, sentence);
+ viterbiWalk(hg.goalNode, extractor);
+ return extractor.getFeatures();
+ }
+
+ /**
+ * Returns the Viterbi Word Alignments as String.
+ */
+ public static String getViterbiWordAlignments(final HyperGraph hg) {
+ if (hg == null)
+ return "";
+
+ final WordAlignmentExtractor wordAlignmentWalker = new WordAlignmentExtractor();
+ viterbiWalk(hg.goalNode, wordAlignmentWalker);
+ return wordAlignmentWalker.toString();
+ }
+
+ /**
+ * Returns the Viterbi Word Alignments as list of lists (target-side).
+ */
+ public static List<List<Integer>> getViterbiWordAlignmentList(final HyperGraph hg) {
+ if (hg == null)
+ return emptyList();
+
+ final WordAlignmentExtractor wordAlignmentWalker = new WordAlignmentExtractor();
+ viterbiWalk(hg.goalNode, wordAlignmentWalker);
+ return wordAlignmentWalker.getFinalWordAlignments();
+ }
+
+ /** find 1best hypergraph */
+ public static HyperGraph getViterbiTreeHG(HyperGraph hg_in) {
+ HyperGraph res =
+ new HyperGraph(cloneNodeWithBestHyperedge(hg_in.goalNode), -1, -1, null);
+ // TODO: number of items/deductions
+ get1bestTreeNode(res.goalNode);
+ return res;
+ }
+
+ private static void get1bestTreeNode(HGNode it) {
+ HyperEdge dt = it.bestHyperedge;
+ if (null != dt.getTailNodes()) {
+ for (int i = 0; i < dt.getTailNodes().size(); i++) {
+ HGNode antNode = dt.getTailNodes().get(i);
+ HGNode newNode = cloneNodeWithBestHyperedge(antNode);
+ dt.getTailNodes().set(i, newNode);
+ get1bestTreeNode(newNode);
+ }
+ }
+ }
+
+ // TODO: tbl_states
+ private static HGNode cloneNodeWithBestHyperedge(HGNode inNode) {
+ List<HyperEdge> hyperedges = new ArrayList<HyperEdge>(1);
+ HyperEdge cloneEdge = cloneHyperedge(inNode.bestHyperedge);
+ hyperedges.add(cloneEdge);
+ return new HGNode(inNode.i, inNode.j, inNode.lhs, hyperedges, cloneEdge, inNode.getDPStates());
+ }
+
+
+ private static HyperEdge cloneHyperedge(HyperEdge inEdge) {
+ List<HGNode> antNodes = null;
+ if (null != inEdge.getTailNodes()) {
+ antNodes = new ArrayList<HGNode>(inEdge.getTailNodes());// l_ant_items will be changed in
+ // get_1best_tree_item
+ }
+ HyperEdge res =
+ new HyperEdge(inEdge.getRule(), inEdge.getBestDerivationScore(), inEdge.getTransitionLogP(false),
+ antNodes, inEdge.getSourcePath());
+ return res;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java b/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java
new file mode 100644
index 0000000..65bffbf
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.hypergraph;
+
+/**
+ * Classes implementing this interface define a single function that is applied to each node. This
+ * interface is used for various walkers (ViterbiExtractor).
+ */
+public interface WalkerFunction {
+
+ /**
+ * Function that is applied to node at tail node index nodeIndex.
+ * nodeIndex indicates the index of node in the list of tailnodes for the
+ * outgoing edge.
+ */
+ void apply(HGNode node, int nodeIndex);
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java b/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java
new file mode 100644
index 0000000..837c69f
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java
@@ -0,0 +1,133 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.hypergraph;
+
+import static java.util.Collections.emptyList;
+
+import java.util.List;
+import java.util.Stack;
+
+import joshua.decoder.ff.tm.Rule;
+import joshua.decoder.hypergraph.KBestExtractor.DerivationState;
+import joshua.decoder.hypergraph.KBestExtractor.DerivationVisitor;
+
+/**
+ * This class enables extraction of word-level alignments from hypotheses.
+ * It implements two interfaces, WalkerFunction and DerivationVisitor.
+ * The former is for using the Viterbi walk function, the latter is for
+ * k-best extraction.
+ * Intermediate WordAlignmentStates are placed on a stack and/or merged down
+ * if possible.
+ * @author fhieber
+ */
+public class WordAlignmentExtractor implements WalkerFunction, DerivationVisitor {
+
+ private final Stack<WordAlignmentState> stack = new Stack<WordAlignmentState>();
+
+ /**
+ * Merges a state with the top of the stack if applicable or places it on top of the stack.
+ */
+ private void merge(final WordAlignmentState state) {
+ // if alignment state has no NTs left AND stack is not empty
+ // and parent state on stack still needs something to substitute
+ if (!stack.isEmpty()
+ && state.isComplete()) {
+ final WordAlignmentState parentState = stack.pop();
+ if (parentState.isComplete()) {
+ throw new IllegalStateException("Parent state already complete");
+ }
+ parentState.substituteIn(state);
+ merge(parentState);
+ } else {
+ stack.add(state);
+ }
+ }
+
+ /**
+ * Common entry point for WalkerFunction and DerivationVisitor.
+ */
+ private void extract(final Rule rule, final int spanStart) {
+ if (rule != null) {
+ merge(new WordAlignmentState(rule, spanStart));
+ }
+ }
+
+ /**
+ * entry for Viterbi walker. Calls word alignment extraction
+ * for best hyperedge from given node.
+ */
+ @Override
+ public void apply(HGNode node, int nodeIndex) {
+ extract(node.bestHyperedge.getRule(), node.i);
+ }
+
+ /**
+ * Visiting a node during k-best extraction is the same as
+ * apply() for Viterbi extraction but using the edge from
+ * the Derivation state.
+ */
+ @Override
+ public void before(final DerivationState state, final int level, int tailNodeIndex) {
+ extract(state.edge.getRule(), state.parentNode.i);
+ }
+
+ /**
+ * Nothing to do after visiting a node.
+ */
+ @Override
+ public void after(final DerivationState state, final int level, int tailNodeIndex) {}
+
+ /**
+ * Final word alignment without sentence markers
+ * or empty list if stack is empty.
+ */
+ public List<List<Integer>> getFinalWordAlignments() {
+ if (stack.isEmpty()) {
+ return emptyList();
+ }
+
+ if (stack.size() != 1) {
+ throw new RuntimeException(
+ String.format(
+ "Stack of WordAlignmentExtractor should contain only a single (last) element, but was size %d", stack.size()));
+ }
+
+ return stack.peek().toFinalList();
+ }
+
+ /**
+ * Returns a String representation of the (final) word alignment
+ * state on top of the stack.
+ * Empty string for empty stack.
+ */
+ @Override
+ public String toString() {
+ if (stack.isEmpty()) {
+ return "";
+ }
+
+ if (stack.size() != 1) {
+ throw new RuntimeException(
+ String.format(
+ "Stack of WordAlignmentExtractor should contain only a single (last) element, but was size %d", stack.size()));
+ }
+
+ return stack.peek().toFinalString();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java b/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java
new file mode 100644
index 0000000..258e062
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java
@@ -0,0 +1,171 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.hypergraph;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+
+import joshua.decoder.ff.tm.Rule;
+
+/**
+ * This class encodes a derivation state in terms of a list of alignment points.
+ * Whenever a child instance is substituted into the parent instance, we need to
+ * adjust source indexes of the alignments.
+ *
+ * @author fhieber
+ */
+public class WordAlignmentState {
+
+ /**
+ * each element in this list corresponds to a token on the target side of the
+ * rule. The values of the elements correspond to the aligned source token on
+ * the source side of the rule.
+ */
+ private LinkedList<AlignedSourceTokens> trgPoints;
+ private int srcStart;
+ /** number of NTs we need to substitute. */
+ private int numNT;
+ /** grows with substitutions of child rules. Reaches original Rule span if substitutions are complete */
+ private int srcLength;
+
+ /**
+ * construct AlignmentState object from a virgin Rule and its source span.
+ * Determines if state is complete (if no NT present)
+ */
+ WordAlignmentState(Rule rule, int start) {
+ trgPoints = new LinkedList<AlignedSourceTokens>();
+ srcLength = rule.getFrench().length;
+ numNT = rule.getArity();
+ srcStart = start;
+ Map<Integer, List<Integer>> alignmentMap = rule.getAlignmentMap();
+ int[] nonTermPositions = rule.getNonTerminalSourcePositions();
+ int[] trg = rule.getEnglish();
+ // for each target index, create a TargetAlignmentPoint
+ for (int trgIndex = 0; trgIndex < trg.length; trgIndex++) {
+ AlignedSourceTokens trgPoint = new AlignedSourceTokens();
+
+ if (trg[trgIndex] >= 0) { // this is a terminal symbol, check for alignment
+ if (alignmentMap.containsKey(trgIndex)) {
+ // add source indexes to TargetAlignmentPoint
+ for (int srcIdx : alignmentMap.get(trgIndex)) {
+ trgPoint.add(srcStart + srcIdx);
+ }
+ } else { // this target word is NULL-aligned
+ trgPoint.setNull();
+ }
+ } else { // this is a nonterminal ([X]) [actually its the (negative) index of the NT in the source
+ trgPoint.setNonTerminal();
+ trgPoint.add(srcStart + nonTermPositions[Math.abs(trg[trgIndex]) - 1]);
+ }
+ trgPoints.add(trgPoint);
+ }
+ }
+
+ /**
+ * if there are no more NonTerminals to substitute,
+ * this state is said to be complete
+ */
+ public boolean isComplete() {
+ return numNT == 0;
+ }
+
+ /**
+ * builds the final alignment string in the standard alignment format: src -
+ * trg. Sorted by trg indexes. Disregards the sentence markers.
+ */
+ public String toFinalString() {
+ StringBuilder sb = new StringBuilder();
+ int t = 0;
+ for (AlignedSourceTokens pt : trgPoints) {
+ for (int s : pt)
+ sb.append(String.format(" %d-%d", s-1, t-1)); // disregard sentence
+ // markers
+ t++;
+ }
+ String result = sb.toString();
+ if (!result.isEmpty())
+ return result.substring(1);
+ return result;
+ }
+
+ /**
+ * builds the final alignment list.
+ * each entry in the list corresponds to a list of aligned source tokens.
+ * First and last item in trgPoints is skipped.
+ */
+ public List<List<Integer>> toFinalList() {
+ assert (isComplete() == true);
+ List<List<Integer>> alignment = new ArrayList<List<Integer>> ();
+ if (trgPoints.isEmpty())
+ return alignment;
+ ListIterator<AlignedSourceTokens> it = trgPoints.listIterator();
+ it.next(); // skip first item (sentence marker)
+ while (it.hasNext()) {
+ AlignedSourceTokens alignedSourceTokens = it.next();
+ if (it.hasNext()) { // if not last element in trgPoints
+ List<Integer> newAlignedSourceTokens = new ArrayList<Integer>();
+ for (Integer sourceIndex : alignedSourceTokens)
+ newAlignedSourceTokens.add(sourceIndex - 1); // shift by one to disregard sentence marker
+ alignment.add(newAlignedSourceTokens);
+ }
+ }
+ return alignment;
+ }
+
+ /**
+ * String representation for debugging.
+ */
+ public String toString() {
+ return String.format("%s , len=%d start=%d, isComplete=%s",
+ trgPoints.toString(), srcLength, srcStart, this.isComplete());
+ }
+
+ /**
+ * substitutes a child WorldAlignmentState into this instance at the first
+ * NT it finds. Also shifts the indeces in this instance by the span/width of the
+ * child that is to be substituted.
+ * Substitution order is determined by the source-first traversal through the hypergraph.
+ */
+ void substituteIn(WordAlignmentState child) {
+ // update existing indexes by length of child (has no effect on NULL and
+ // NonTerminal points)
+ for (AlignedSourceTokens trgPoint : trgPoints)
+ trgPoint.shiftBy(child.srcStart, child.srcLength - 1);
+
+ // now substitute in the child at first NT, modifying the list
+ ListIterator<AlignedSourceTokens> it = trgPoints.listIterator();
+ while (it.hasNext()) {
+ AlignedSourceTokens trgPoint = it.next();
+ if (trgPoint.isNonTerminal()) { // found first NT
+ it.remove(); // remove NT symbol
+ for (AlignedSourceTokens childElement : child.trgPoints) {
+ childElement.setFinal(); // child source indexes are final, do not change them anymore
+ it.add(childElement);
+ }
+ this.srcLength += child.srcLength - 1; // -1 (NT)
+ this.numNT--;
+ break;
+ }
+ }
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/hypergraph/package.html
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/hypergraph/package.html b/src/main/java/org/apache/joshua/decoder/hypergraph/package.html
new file mode 100644
index 0000000..6fdd043
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/hypergraph/package.html
@@ -0,0 +1,18 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
+<html>
+<head></head>
+<body bgcolor="white">
+
+<!--
+##### THIS IS THE TEMPLATE FOR THE PACKAGE DOC COMMENTS. #####
+##### TYPE YOUR PACKAGE COMMENTS HERE. BEGIN WITH A #####
+##### ONE-SENTENCE SUMMARY STARTING WITH A VERB LIKE: #####
+-->
+
+Provides implementations of hypergraph data structures and related algorithms
+used in extracting translation results in hierarchical phrase-based translation.
+
+<!-- Put @see and @since tags down here. -->
+
+</body>
+</html>
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java b/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java
new file mode 100644
index 0000000..328e01b
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.io;
+
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
+
+/**
+ * Denormalize a(n English) string in a collection of ways listed below.
+ * <UL>
+ * <LI>Capitalize the first character in the string</LI>
+ * <LI>Detokenize</LI>
+ * <UL>
+ * <LI>Delete whitespace in front of periods and commas</LI>
+ * <LI>Join contractions</LI>
+ * <LI>Capitalize name titles (Mr Ms Miss Dr etc.)</LI>
+ * <LI>TODO: Handle surrounding characters ([{<"''">}])</LI>
+ * <LI>TODO: Join multi-period abbreviations (e.g. M.Phil. i.e.)</LI>
+ * <LI>TODO: Handle ambiguities like "st.", which can be an abbreviation for both "Saint" and
+ * "street"</LI>
+ * <LI>TODO: Capitalize both the title and the name of a person, e.g. Mr. Morton (named entities
+ * should be demarcated).</LI>
+ * </UL>
+ * </UL> <bold>N.B.</bold> These methods all assume that every translation result that will be
+ * denormalized has the following format:
+ * <UL>
+ * <LI>There is only one space between every pair of tokens</LI>
+ * <LI>There is no whitespace before the first token</LI>
+ * <LI>There is no whitespace after the final token</LI>
+ * <LI>Standard spaces are the only type of whitespace</LI>
+ * </UL>
+ * </UL>
+ */
+
+public class DeNormalize {
+
+ /**
+ * Apply all the denormalization methods to the normalized input line.
+ *
+ * @param normalized
+ * @return
+ */
+ public static String processSingleLine(String normalized) {
+ // The order in which the methods are applied could matter in some situations. E.g., a token to
+ // be matched is "phd", but if it is the first token in the line, it might have already been
+ // capitalized to "Phd" by the capitalizeFirstLetter method, and because the "phd" token won't
+ // match, "Phd" won't be corrected to "PhD".
+ String deNormalized = normalized;
+ deNormalized = capitalizeNameTitleAbbrvs(deNormalized);
+ deNormalized = replaceBracketTokens(deNormalized);
+ deNormalized = joinPunctuationMarks(deNormalized);
+ deNormalized = joinHyphen(deNormalized);
+ deNormalized = joinContractions(deNormalized);
+ deNormalized = capitalizeLineFirstLetter(deNormalized);
+ return deNormalized;
+ }
+
+ /**
+ * Capitalize the first letter of a line. This should be the last denormalization step applied to
+ * a line.
+ *
+ * @param line The single-line input string
+ * @return The input string modified as described above
+ */
+ public static String capitalizeLineFirstLetter(String line) {
+ String result = null;
+ Pattern regexp = Pattern.compile("[^\\p{Punct}\\p{Space}��]");
+ Matcher matcher = regexp.matcher(line);
+ if (matcher.find()) {
+ String match = matcher.group(0);
+ result = line.replaceFirst(match, match.toUpperCase());
+ } else {
+ result = line;
+ }
+ return result;
+ }
+
+ /**
+ * Scanning from left-to-right, a comma or period preceded by a space will become just the
+ * comma/period.
+ *
+ * @param line The single-line input string
+ * @return The input string modified as described above
+ */
+ public static String joinPunctuationMarks(String line) {
+ String result = line;
+ result = result.replace(" ,", ",");
+ result = result.replace(" ;", ";");
+ result = result.replace(" :", ":");
+ result = result.replace(" .", ".");
+ result = result.replace(" !", "!");
+ result = result.replace("� ", "�");
+ result = result.replace(" ?", "?");
+ result = result.replace("� ", "�");
+ result = result.replace(" )", ")");
+ result = result.replace(" ]", "]");
+ result = result.replace(" }", "}");
+ result = result.replace("( ", "(");
+ result = result.replace("[ ", "[");
+ result = result.replace("{ ", "{");
+ return result;
+ }
+
+ /**
+ * Scanning from left-to-right, a hyphen surrounded by a space before and after it will become
+ * just the hyphen.
+ *
+ * @param line The single-line input string
+ * @return The input string modified as described above
+ */
+ public static String joinHyphen(String line) {
+ return line.replace(" - ", "-");
+ }
+
+ /**
+ * Scanning the line from left-to-right, a contraction suffix preceded by a space will become just
+ * the contraction suffix. <br>
+ * <br>
+ * I.e., the preceding space will be deleting, joining the prefix to the suffix. <br>
+ * <br>
+ * E.g.
+ *
+ * <pre>wo n't</pre>
+ *
+ * becomes
+ *
+ * <pre>won't</pre>
+ *
+ * @param line The single-line input string
+ * @return The input string modified as described above
+ */
+ public static String joinContractions(String line) {
+ String result = line;
+ for (String suffix : new String[] {"'d", "'ll", "'m", "n't", "'re", "'s", "'ve",}) {
+ result = result.replace(" " + suffix, suffix);
+ }
+ return result;
+ }
+
+ /**
+ * Capitalize the first character of the titles of names: Mr Mrs Ms Miss Dr Prof
+ *
+ * @param line The single-line input string
+ * @return The input string modified as described above
+ */
+ public static String capitalizeNameTitleAbbrvs(String line) {
+ String result = line;
+
+ // Capitalize only the first character of certain name titles.
+ for (String title : new String[] {"dr", "miss", "mr", "mrs", "ms", "prof"}) {
+ result =
+ result.replaceAll("\\b" + title + "\\b",
+ Character.toUpperCase(title.charAt(0)) + title.substring(1));
+ }
+ // Capitalize the relevant characters of certain name titles.
+ result = result.replaceAll("\\b" + "phd" + "\\b", "PhD");
+ result = result.replaceAll("\\b" + "mphil" + "\\b", "MPhil");
+ return result;
+ }
+
+ public static String capitalizeI(String line) {
+ // Capitalize only the first character of certain name titles.
+ return line.replaceAll("\\b" + "i" + "\\b", "I");
+ }
+
+ /**
+ * Case-insensitively replace all of the character sequences that represent a bracket character.
+ *
+ * Keys are token representations of abbreviations of titles for names that capitalize more than
+ * just the first letter.<br>
+ * Bracket token sequences: -lrb- -rrb- -lsb- -rsb- -lcb- -rcb- <br>
+ * <br>
+ * See http://www.cis.upenn.edu/~treebank/tokenization.html
+ *
+ * @param line The single-line input string
+ * @return The input string modified as described above
+ */
+ public static String replaceBracketTokens(String line) {
+ String result = line;
+ result = result.replaceAll("(?iu)" + "-lrb-", "(");
+ result = result.replaceAll("(?iu)" + "-rrb-", ")");
+ result = result.replaceAll("(?iu)" + "-lsb-", "[");
+ result = result.replaceAll("(?iu)" + "-rsb-", "]");
+ result = result.replaceAll("(?iu)" + "-lcb-", "{");
+ result = result.replaceAll("(?iu)" + "-rcb-", "}");
+ return result;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java b/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java
new file mode 100644
index 0000000..2733db4
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.io;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.google.gson.Gson;
+import com.google.gson.GsonBuilder;
+
+import joshua.decoder.Translation;
+
+public class JSONMessage {
+ public Data data = null;
+ public List<String> rules = null;
+
+ public JSONMessage() {
+ }
+
+ public class Data {
+ public List<TranslationItem> translations;
+
+ public Data() {
+ translations = new ArrayList<TranslationItem>();
+ }
+ }
+
+ public TranslationItem addTranslation(String text) {
+ if (data == null)
+ data = new Data();
+
+ TranslationItem newItem = new TranslationItem(text);
+ data.translations.add(newItem);
+ return newItem;
+ }
+
+ public class TranslationItem {
+ public String translatedText;
+ public List<NBestItem> raw_nbest;
+
+ public TranslationItem(String value) {
+ this.translatedText = value;
+ this.raw_nbest = new ArrayList<NBestItem>();
+ }
+
+ public void addHypothesis(String hyp, float score) {
+ this.raw_nbest.add(new NBestItem(hyp, score));
+ }
+ }
+
+ public class NBestItem {
+ public String hyp;
+ public float totalScore;
+
+ public NBestItem(String hyp, float score) {
+ this.hyp = hyp;
+ this.totalScore = score;
+ }
+ }
+
+ public void addRule(String rule) {
+ if (rules == null)
+ rules = new ArrayList<String>();
+ rules.add(rule);
+ }
+
+ public class MetaData {
+
+ public MetaData() {
+ }
+ }
+
+ public static JSONMessage buildMessage(Translation translation) {
+ JSONMessage message = new JSONMessage();
+ String[] results = translation.toString().split("\\n");
+ if (results.length > 0) {
+ JSONMessage.TranslationItem item = message.addTranslation(translation.getStructuredTranslation().getTranslationString());
+
+ for (String result: results) {
+ String[] tokens = result.split(" \\|\\|\\| ");
+ String rawResult = tokens[1];
+ float score = Float.parseFloat(tokens[3]);
+ item.addHypothesis(rawResult, score);
+ }
+ }
+ return message;
+ }
+
+ public String toString() {
+ Gson gson = new GsonBuilder().setPrettyPrinting().create();
+ return gson.toJson(this);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java b/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java
new file mode 100644
index 0000000..47f5d81
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java
@@ -0,0 +1,186 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.io;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.Reader;
+
+import com.google.gson.stream.JsonReader;
+
+import joshua.decoder.JoshuaConfiguration;
+import joshua.decoder.JoshuaConfiguration.INPUT_TYPE;
+import joshua.decoder.MetaDataException;
+import joshua.decoder.segment_file.Sentence;
+
+/**
+ * This class iterates over an input stream, looking for inputs to translate. By default, it
+ * expects plain-text input, which can be plain sentences or PLF-encoded lattices. If
+ * '-input-type json' is passed to the decoder, it will instead read JSON objects from the input
+ * stream, with the following format:
+ *
+ * {
+ * "data": {
+ * "translations": [
+ * { "sourceText": "sentence to be translated" },
+ * { "sourceText": "next sentence" },
+ * { "sourceText": "@some command to run" }
+ * ]
+ * }
+ * }
+ *
+ * @author Matt Post <po...@cs.jhu.edu>
+ * @author orluke
+ */
+public class TranslationRequestStream {
+ private final JoshuaConfiguration joshuaConfiguration;
+ private int sentenceNo = -1;
+
+ private Sentence nextSentence = null;
+
+ /* Plain text or JSON input */
+ private StreamHandler requestHandler = null;
+
+ /* Whether the request has been killed by a broken client connection. */
+ private volatile boolean isShutDown = false;
+
+ public TranslationRequestStream(BufferedReader reader, JoshuaConfiguration joshuaConfiguration) {
+ this.joshuaConfiguration = joshuaConfiguration;
+
+ if (joshuaConfiguration.input_type == INPUT_TYPE.json) {
+ this.requestHandler = new JSONStreamHandler(reader);
+ } else {
+ this.requestHandler = new PlaintextStreamHandler(reader);
+ }
+ }
+
+ private interface StreamHandler {
+ Sentence next() throws IOException, MetaDataException;
+ }
+
+ private class JSONStreamHandler implements StreamHandler {
+
+ private JsonReader reader = null;
+ private String line = null;
+
+ public JSONStreamHandler(Reader in) {
+ reader = new JsonReader(in);
+ try {
+ reader.beginObject();
+ reader.nextName(); // "data"
+ reader.beginObject();
+ reader.nextName(); // "translations"
+ reader.beginArray();
+ } catch (IOException e) {
+ e.printStackTrace();
+ }
+ }
+
+ @Override
+ public Sentence next() throws IOException, MetaDataException {
+ line = null;
+
+ if (reader.hasNext()) {
+ reader.beginObject();
+ reader.nextName();
+ line = reader.nextString();
+ reader.endObject();
+ }
+
+ if (line == null)
+ return null;
+
+ if (line.startsWith("@"))
+ throw new MetaDataException(line);
+
+ return new Sentence(line, -1, joshuaConfiguration);
+ }
+ }
+
+ private class PlaintextStreamHandler implements StreamHandler {
+
+ private BufferedReader reader = null;
+
+ public PlaintextStreamHandler(BufferedReader in) {
+ reader = in;
+ }
+
+ @Override
+ public Sentence next() throws IOException, MetaDataException {
+
+ String line = reader.readLine();
+
+ if (line != null) {
+ if (line.startsWith("@"))
+ throw new MetaDataException(line);
+
+ return new Sentence(line, sentenceNo, joshuaConfiguration);
+ }
+
+ return null;
+ }
+ }
+
+ public int size() {
+ return sentenceNo + 1;
+ }
+
+ /*
+ * Returns the next sentence item, then sets it to null, so that hasNext() will know to produce a
+ * new one.
+ */
+ public synchronized Sentence next() throws MetaDataException {
+ nextSentence = null;
+
+ if (isShutDown)
+ return null;
+
+ try {
+ nextSentence = requestHandler.next();
+ if (nextSentence != null) {
+ sentenceNo++;
+ nextSentence.id = sentenceNo;
+ }
+ } catch (IOException e) {
+ this.shutdown();
+ }
+
+ return nextSentence;
+ }
+
+ /**
+ * When the client socket is interrupted, we need to shut things down. On the source side, the
+ * TranslationRequest could easily have buffered a lot of lines and so will keep discovering
+ * sentences to translate, but the output Translation objects will start throwing exceptions when
+ * trying to print to the closed socket. When that happens, we call this function() so that we can
+ * tell next() to stop returning translations, which in turn will cause it to stop asking for
+ * them.
+ *
+ * Note that we don't go to the trouble of shutting down existing DecoderThreads. This would be
+ * good to do, but for the moment would require more bookkeeping than we want to do.
+ */
+
+ public void shutdown() {
+ isShutDown = true;
+ }
+
+ public boolean isShutDown() {
+ return isShutDown;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/package.html
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/package.html b/src/main/java/org/apache/joshua/decoder/package.html
new file mode 100644
index 0000000..fda252e
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/package.html
@@ -0,0 +1,21 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
+<html>
+<head></head>
+<body bgcolor="white">
+
+<!--
+##### THIS IS THE TEMPLATE FOR THE PACKAGE DOC COMMENTS. #####
+##### TYPE YOUR PACKAGE COMMENTS HERE. BEGIN WITH A #####
+##### ONE-SENTENCE SUMMARY STARTING WITH A VERB LIKE: #####
+-->
+
+Provides infrastructure and wrapper code used relevant to
+hierarchical phrase-based decoding for statistical machine translation.
+<p>
+This package does not include an implementation of any actual decoding algorithm.
+Rather, such code is in child packages of this package.
+
+<!-- Put @see and @since tags down here. -->
+
+</body>
+</html>
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/Candidate.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/Candidate.java b/src/main/java/org/apache/joshua/decoder/phrase/Candidate.java
new file mode 100644
index 0000000..4b8b6a6
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/Candidate.java
@@ -0,0 +1,241 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+/***
+ * A candidate is basically a cube prune state. It contains a list of hypotheses and target
+ * phrases, and an instantiated candidate is a pair of indices that index these two lists. This
+ * is the "cube prune" position.
+ */
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import joshua.corpus.Span;
+import joshua.decoder.chart_parser.ComputeNodeResult;
+import joshua.decoder.ff.state_maintenance.DPState;
+import joshua.decoder.ff.tm.Rule;
+import joshua.decoder.hypergraph.HGNode;
+
+public class Candidate {
+
+ // the set of hypotheses that can be paired with phrases from this span
+ private List<Hypothesis> hypotheses;
+
+ // the list of target phrases gathered from a span of the input
+ private TargetPhrases phrases;
+
+ // source span of new phrase
+ public Span span;
+
+ // future cost of applying phrases to hypotheses
+ float future_delta;
+
+ // indices into the hypotheses and phrases arrays (used for cube pruning)
+ private int[] ranks;
+
+ // scoring and state information
+ private ComputeNodeResult result;
+
+ /**
+ * When candidate objects are extended, the new one is initialized with the same underlying
+ * "phrases" and "hypotheses" and "span" objects. So these all have to be equal, as well as
+ * the ranks.
+ *
+ * This is used to prevent cube pruning from adding the same candidate twice, having reached
+ * a point in the cube via different paths.
+ */
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof Candidate) {
+ Candidate other = (Candidate) obj;
+ if (hypotheses != other.hypotheses || phrases != other.phrases || span != other.span)
+ return false;
+
+ if (ranks.length != other.ranks.length)
+ return false;
+
+ for (int i = 0; i < ranks.length; i++)
+ if (ranks[i] != other.ranks[i])
+ return false;
+
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return 17 * hypotheses.size()
+ + 23 * phrases.size()
+ + 57 * span.hashCode()
+ + 117 * Arrays.hashCode(ranks);
+// return hypotheses.hashCode() * phrases.hashCode() * span.hashCode() * Arrays.hashCode(ranks);
+ }
+
+ @Override
+ public String toString() {
+ return String.format("CANDIDATE(hyp %d/%d, phr %d/%d) [%s] phrase=[%s] span=%s",
+ ranks[0], hypotheses.size(), ranks[1], phrases.size(),
+ getHypothesis(), getRule().getEnglishWords().replaceAll("\\[.*?\\] ",""), getSpan());
+ }
+
+ public Candidate(List<Hypothesis> hypotheses, TargetPhrases phrases, Span span, float delta) {
+ this.hypotheses = hypotheses;
+ this.phrases = phrases;
+ this.span = span;
+ this.future_delta = delta;
+ this.ranks = new int[] { 0, 0 };
+ }
+
+ public Candidate(List<Hypothesis> hypotheses, TargetPhrases phrases, Span span, float delta, int[] ranks) {
+ this.hypotheses = hypotheses;
+ this.phrases = phrases;
+ this.span = span;
+ this.future_delta = delta;
+ this.ranks = ranks;
+// this.score = hypotheses.get(ranks[0]).score + phrases.get(ranks[1]).getEstimatedCost();
+ }
+
+ /**
+ * Extends the cube pruning dot in both directions and returns the resulting set. Either of the
+ * results can be null if the end of their respective lists is reached.
+ *
+ * @return The neighboring candidates (possibly null)
+ */
+ public Candidate[] extend() {
+ return new Candidate[] { extendHypothesis(), extendPhrase() };
+ }
+
+ /**
+ * Extends the cube pruning dot along the dimension of existing hypotheses.
+ *
+ * @return the next candidate, or null if none
+ */
+ public Candidate extendHypothesis() {
+ if (ranks[0] < hypotheses.size() - 1) {
+ return new Candidate(hypotheses, phrases, span, future_delta, new int[] { ranks[0] + 1, ranks[1] });
+ }
+ return null;
+ }
+
+ /**
+ * Extends the cube pruning dot along the dimension of candidate target sides.
+ *
+ * @return the next Candidate, or null if none
+ */
+ public Candidate extendPhrase() {
+ if (ranks[1] < phrases.size() - 1) {
+ return new Candidate(hypotheses, phrases, span, future_delta, new int[] { ranks[0], ranks[1] + 1 });
+ }
+
+ return null;
+ }
+
+ /**
+ * Returns the input span from which the phrases for this candidates were gathered.
+ *
+ * @return the span object
+ */
+ public Span getSpan() {
+ return this.span;
+ }
+
+ /**
+ * A candidate is a (hypothesis, target phrase) pairing. The hypothesis and target phrase are
+ * drawn from a list that is indexed by (ranks[0], ranks[1]), respectively. This is a shortcut
+ * to return the hypothesis of the candidate pair.
+ *
+ * @return the hypothesis at position ranks[0]
+ */
+ public Hypothesis getHypothesis() {
+ return this.hypotheses.get(ranks[0]);
+ }
+
+ /**
+ * This returns the target side {@link Phrase}, which is a {@link Rule} object. This is just a
+ * convenience function that works by returning the phrase indexed in ranks[1].
+ *
+ * @return the phrase at position ranks[1]
+ */
+ public Rule getRule() {
+ return phrases.get(ranks[1]);
+ }
+
+ /**
+ * The hypotheses list is a list of tail pointers. This function returns the tail pointer
+ * currently selected by the value in ranks.
+ *
+ * @return a list of size one, wrapping the tail node pointer
+ */
+ public List<HGNode> getTailNodes() {
+ List<HGNode> tailNodes = new ArrayList<HGNode>();
+ tailNodes.add(getHypothesis());
+ return tailNodes;
+ }
+
+ /**
+ * Returns the bit vector of this hypothesis. The bit vector is computed by ORing the coverage
+ * vector of the tail node (hypothesis) and the source span of phrases in this candidate.
+ * @return
+ */
+ public Coverage getCoverage() {
+ Coverage cov = new Coverage(getHypothesis().getCoverage());
+ cov.set(getSpan());
+ return cov;
+ }
+
+ /**
+ * Sets the result of a candidate (should just be moved to the constructor).
+ *
+ * @param result
+ */
+ public void setResult(ComputeNodeResult result) {
+ this.result = result;
+ }
+
+ /**
+ * This returns the sum of two costs: the HypoState cost + the transition cost. The HypoState cost
+ * is in turn the sum of two costs: the Viterbi cost of the underlying hypothesis, and the adjustment
+ * to the future score incurred by translating the words under the source phrase being added.
+ * The transition cost is the sum of new features incurred along the transition (mostly, the
+ * language model costs).
+ *
+ * The Future Cost item should probably just be implemented as another kind of feature function,
+ * but it would require some reworking of that interface, which isn't worth it.
+ *
+ * @return
+ */
+ public float score() {
+ return getHypothesis().getScore() + future_delta + result.getTransitionCost();
+ }
+
+ public float getFutureEstimate() {
+ return getHypothesis().getScore() + future_delta;
+ }
+
+ public List<DPState> getStates() {
+ return result.getDPStates();
+ }
+
+ public ComputeNodeResult getResult() {
+ return result;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/CandidateComparator.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/CandidateComparator.java b/src/main/java/org/apache/joshua/decoder/phrase/CandidateComparator.java
new file mode 100644
index 0000000..2526ed6
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/CandidateComparator.java
@@ -0,0 +1,28 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+import java.util.Comparator;
+
+public class CandidateComparator implements Comparator<Candidate> {
+ @Override
+ public int compare(Candidate one, Candidate another) {
+ return Float.compare(another.score(), one.score());
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java b/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java
new file mode 100644
index 0000000..398c7a0
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java
@@ -0,0 +1,231 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+import java.util.BitSet;
+
+import joshua.corpus.Span;
+
+/**
+ * Represents a coverage vector. The vector is relative to a hypothesis. {firstZero} denotes the
+ * first uncovered word of the sentence, and {bits} contains the coverage vector of all the words
+ * after it, with the first zero removed.
+ */
+
+public class Coverage {
+
+ // The index of the first uncovered word
+ private int firstZero;
+
+ // Bits with the first zero removed.
+ // We also assume anything beyond this is zero due to the reordering window.
+ // Lowest bits correspond to next word.
+ private BitSet bits;
+
+ // Default bit vector length
+ private static int INITIAL_LENGTH = 10;
+
+ public Coverage() {
+ firstZero = 0;
+ bits = new BitSet(INITIAL_LENGTH);
+ }
+
+ public Coverage(int firstZero) {
+ this.firstZero = firstZero;
+ bits = new BitSet(INITIAL_LENGTH);
+ }
+
+ /**
+ * Pretty-prints the coverage vector, making a guess about the length
+ */
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append(String.format("%d ", firstZero));
+
+ for (int i = 0; i < Math.max(INITIAL_LENGTH, bits.length()); i++) { // only display first 10 bits
+ sb.append(bits.get(i) ? "x" : ".");
+ }
+
+ return sb.toString();
+ }
+
+ /**
+ * Initialize a coverage vector from another Coverage vector, creating a separate object.
+ *
+ * @param firstZero
+ * @param bits
+ */
+ public Coverage(Coverage other) {
+ this.firstZero = other.firstZero;
+ this.bits = (BitSet) other.bits.clone();
+ }
+
+ /**
+ * Turns on all bits from position start to position (end - 1), that is, in the range [start .. end).
+ * This is done relative to the current coverage vector, of course, which may not start at 0.
+ *
+ * @param begin
+ * @param end
+ */
+ public void set(int begin, int end) {
+ assert compatible(begin, end);
+
+// StringBuffer sb = new StringBuffer();
+// sb.append(String.format("SET(%d,%d) %s", begin, end, this));
+
+ if (begin == firstZero) {
+ // A concatenation.
+ firstZero = end;
+ bits = bits.get(end - begin, Math.max(end - begin, bits.length()));
+ int firstClear = bits.nextClearBit(0);
+ if (firstClear != 0) {
+ // We might have exactly covered a gap, in which case we need to adjust shift
+ // firstZero and the bits until we reach the new end
+ firstZero += firstClear;
+ bits = bits.get(firstClear, bits.length());
+ }
+ } else {
+ // Set the bits relative to the currenS
+ bits.or(pattern(begin, end));
+ }
+
+// sb.append(String.format(" -> %s", this));
+// System.err.println(sb);
+ }
+
+ /**
+ * Convenience function.
+ */
+ public final void set(Span span) {
+ set(span.start, span.end);
+ }
+
+ /**
+ * Tests whether a new range is compatible with the current coverage vector. It must be after
+ * the first uncovered word, obviously, and must not conflict with spans after the first
+ * uncovered word.
+ *
+ * @param begin the begin index (absolute)
+ * @param end the end index (absolute)
+ * @return true if the span is compatible with the coverage vector
+ */
+ public boolean compatible(int begin, int end) {
+ if (begin >= firstZero) {
+ BitSet pattern = new BitSet();
+ pattern.set(begin - firstZero, end - firstZero);
+ return ! bits.intersects(pattern);
+ }
+ return false;
+ }
+
+ /**
+ * Returns the source sentence index of the first uncovered word.
+ *
+ * @return the index
+ */
+ public int firstZero() {
+ return firstZero;
+ }
+
+ /**
+ * LeftOpen() and RightOpen() find the larger gap in which a new source phrase pair sits.
+ * When using a phrase pair covering (begin, end), the pair
+ *
+ * (LeftOpen(begin), RightOpen(end, sentence_length))
+ *
+ * provides this gap.
+
+ * Find the left bound of the gap in which the phrase [begin, ...) sits.
+ *
+ * @param begin the start index of the phrase being applied.
+ * @return
+ */
+ public int leftOpening(int begin) {
+ for (int i = begin - firstZero; i > 0; --i) {
+ if (bits.get(i)) {
+ assert compatible(i + firstZero + 1, begin);
+ assert !compatible(i + firstZero, begin);
+ return i + firstZero + 1;
+ }
+ }
+
+ assert compatible(firstZero, begin);
+ return firstZero;
+ }
+
+ /**
+ * LeftOpen() and RightOpen() find the larger gap in which a new source phrase pair sits.
+ * When using a phrase pair covering (begin, end), the pair
+ *
+ * (LeftOpen(begin), RightOpen(end, sentence_length))
+ *
+ * provides this gap.
+ *
+ * Finds the right bound of the enclosing gap, or the end of sentence, whichever is less.
+ */
+ public int rightOpening(int end, int sentenceLength) {
+ for (int i = end - firstZero; i < Math.min(64, sentenceLength - firstZero); i++) {
+ if (bits.get(i)) {
+ return i + firstZero;
+ }
+ }
+ return sentenceLength;
+ }
+
+ /**
+ * Creates a bit vector with the same offset as the current coverage vector, flipping on
+ * bits begin..end.
+ *
+ * @param begin the begin index (absolute)
+ * @param end the end index (absolute)
+ * @return a bit vector (relative) with positions [begin..end) on
+ */
+ public BitSet pattern(int begin, int end) {
+// System.err.println(String.format("pattern(%d,%d) %d %s %s", begin, end, firstZero, begin >= firstZero, toString()));
+ assert begin >= firstZero;
+ BitSet pattern = new BitSet(INITIAL_LENGTH);
+ pattern.set(begin - firstZero, end - firstZero);
+ return pattern;
+ }
+
+ /**
+ * Returns the underlying coverage bits.
+ *
+ * @return
+ */
+ public BitSet getCoverage() {
+ return bits;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof Coverage) {
+ Coverage other = (Coverage) obj;
+ return getCoverage().equals(other.getCoverage()) && firstZero() == other.firstZero();
+ }
+
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return getCoverage().hashCode() * firstZero();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/CoverageTest.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/CoverageTest.java b/src/main/java/org/apache/joshua/decoder/phrase/CoverageTest.java
new file mode 100644
index 0000000..90bcbaf
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/CoverageTest.java
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+import static org.junit.Assert.*;
+
+import java.util.BitSet;
+
+import org.junit.Test;
+
+public class CoverageTest {
+
+ @Test
+ public void testSet() {
+ Coverage cov = new Coverage();
+ cov.set(1,2);
+ cov.set(3,4);
+ cov.set(2,3);
+ cov.set(0,1);
+
+ assertFalse(cov.compatible(0, 1));
+ assertFalse(cov.compatible(0, 5));
+ assertTrue(cov.compatible(4, 6));
+
+ assertEquals(cov.toString(), "4 ..........");
+ }
+
+ @Test
+ public void testPattern() {
+ Coverage cov = new Coverage();
+ cov.set(5,6);
+ cov.set(0,4);
+ BitSet bits = cov.pattern(4, 5);
+ BitSet answerBits = new BitSet();
+ answerBits.set(0);
+ assertEquals(bits, answerBits);
+ }
+
+ @Test
+ public void testCopyConstructor() {
+ Coverage a = new Coverage();
+ a.set(2,3);
+ Coverage b = new Coverage(a);
+ b.set(4,5);
+
+ assertFalse(a.toString().equals(b.toString()));
+ }
+
+ @Test
+ public void testCompatible() {
+ Coverage a = new Coverage();
+ a.set(10, 14);
+
+ assertTrue(a.compatible(14, 16));
+ assertTrue(a.compatible(6, 10));
+ assertTrue(a.compatible(1, 10));
+ assertTrue(a.compatible(1, 9));
+ assertFalse(a.compatible(9, 11));
+ assertFalse(a.compatible(13, 15));
+ assertFalse(a.compatible(9, 15));
+ assertFalse(a.compatible(9, 14));
+ assertFalse(a.compatible(10, 15));
+
+ a.set(0,9);
+
+ for (int width = 1; width <= 3; width++) {
+ for (int i = 0; i < 20; i++) {
+ int j = i + width;
+ if ((i == 9 && j == 10) || i >= 14)
+ assertTrue(a.compatible(i,j));
+ else {
+// System.err.println(String.format("%d,%d -> %s %s", i, j, a.compatible(i,j), a));
+ assertFalse(a.compatible(i,j));
+ }
+ }
+ }
+ }
+
+ @Test
+ public void testFirstZero() {
+ Coverage cov = new Coverage();
+ cov.set(2, 5);
+ assertEquals(cov.firstZero(), 0);
+ cov.set(8,10);
+ assertEquals(cov.firstZero(), 0);
+ cov.set(0, 2);
+ assertEquals(cov.firstZero(), 5);
+ cov.set(5, 7);
+ assertEquals(cov.firstZero(), 7);
+ cov.set(7,8);
+ assertEquals(cov.firstZero(), 10);
+ }
+
+ @Test
+ public void testOpenings() {
+ Coverage cov = new Coverage();
+ cov.set(0, 2);
+ cov.set(8, 10);
+
+ for (int i = 2; i < 7; i++) {
+ assertEquals(cov.leftOpening(i), 2);
+ assertEquals(cov.rightOpening(i, 17), 8);
+ assertEquals(cov.rightOpening(i, 7), 7);
+ }
+ }
+
+ @Test
+ public void testEquals() {
+ Coverage cov = new Coverage();
+ cov.set(9, 11);
+ Coverage cov2 = new Coverage();
+ cov2.set(9,10);
+ cov2.set(10,11);
+ assertEquals(cov, cov2);
+ }
+
+ @Test
+ public void testToString() {
+ Coverage cov = new Coverage();
+ cov.set(0, 40);
+ cov.set(44, 49);
+ assertEquals(cov.toString(), "40 ....xxxxx.");
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/Future.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/Future.java b/src/main/java/org/apache/joshua/decoder/phrase/Future.java
new file mode 100644
index 0000000..22a0225
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/Future.java
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+/***
+ * This class represents the future cost of a hypothesis. The future cost of a hypothesis is the
+ * cost of covering all uncovered words. The way this is computed is with a simple dynamic program
+ * that computes, for each span of the input, the best possible way to cover that span with
+ * phrases from the phrase table. No non-local features (e.g., the language model cost) are used
+ * in computing this estimate.
+ */
+
+import joshua.decoder.Decoder;
+import joshua.util.ChartSpan;
+
+public class Future {
+
+ // Square matrix with half the values ignored.
+ private ChartSpan<Float> entries;
+
+ private int sentlen;
+
+ /**
+ * Computes bottom-up the best way to cover all spans of the input sentence, using the phrases
+ * that have been assembled in a {@link PhraseChart}. Requires that there be a translation at least
+ * for every word (which can be accomplished with a pass-through grammar).
+ *
+ * @param chart
+ */
+ public Future(PhraseChart chart) {
+
+ sentlen = chart.SentenceLength();
+ entries = new ChartSpan<Float>(sentlen + 1, Float.NEGATIVE_INFINITY);
+
+ /*
+ * The sentence is represented as a sequence of words, with the first and last words set
+ * to <s> and </s>. We start indexing at 1 because the first word (<s>) is always covered.
+ */
+ for (int begin = 1; begin <= chart.SentenceLength(); begin++) {
+ // Nothing is nothing (this is a useful concept when two phrases abut)
+ setEntry(begin, begin, 0.0f);
+ // Insert phrases
+ int max_end = Math.min(begin + chart.MaxSourcePhraseLength(), chart.SentenceLength());
+ for (int end = begin + 1; end <= max_end; end++) {
+
+ // Moses doesn't include the cost of applying </s>, so force it to zero
+ if (begin == sentlen - 1 && end == sentlen)
+ setEntry(begin, end, 0.0f);
+ else {
+ TargetPhrases phrases = chart.getRange(begin, end);
+ if (phrases != null)
+ setEntry(begin, end, phrases.get(0).getEstimatedCost());
+ }
+ }
+ }
+
+ // All the phrases are in, now do minimum dynamic programming. Lengths 0 and 1 were already handled above.
+ for (int length = 2; length <= chart.SentenceLength(); length++) {
+ for (int begin = 1; begin <= chart.SentenceLength() - length; begin++) {
+ for (int division = begin + 1; division < begin + length; division++) {
+ setEntry(begin, begin + length, Math.max(getEntry(begin, begin + length), getEntry(begin, division) + getEntry(division, begin + length)));
+ }
+ }
+ }
+
+ if (Decoder.VERBOSE >= 3) {
+ for (int i = 1; i < chart.SentenceLength(); i++)
+ for (int j = i + 1; j < chart.SentenceLength(); j++)
+ System.err.println(String.format("future cost from %d to %d is %.3f", i-1, j-2, getEntry(i, j)));
+ }
+ }
+
+ public float Full() {
+// System.err.println("Future::Full(): " + Entry(1, sentlen));
+ return getEntry(1, sentlen);
+ }
+
+ /**
+ * Calculate change in rest cost when the given coverage is to be covered.
+ */
+ public float Change(Coverage coverage, int begin, int end) {
+ int left = coverage.leftOpening(begin);
+ int right = coverage.rightOpening(end, sentlen);
+// System.err.println(String.format("Future::Change(%s, %d, %d) left %d right %d %.3f %.3f %.3f", coverage, begin, end, left, right,
+// Entry(left, begin), Entry(end, right), Entry(left, right)));
+ return getEntry(left, begin) + getEntry(end, right) - getEntry(left, right);
+ }
+
+ private float getEntry(int begin, int end) {
+ assert end >= begin;
+ assert end < this.sentlen;
+ return entries.get(begin, end);
+ }
+
+ private void setEntry(int begin, int end, float value) {
+ assert end >= begin;
+ assert end < this.sentlen;
+// System.err.println(String.format("future cost from %d to %d is %.5f", begin, end, value));
+ entries.set(begin, end, value);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/Header.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/Header.java b/src/main/java/org/apache/joshua/decoder/phrase/Header.java
new file mode 100644
index 0000000..2a8370d
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/Header.java
@@ -0,0 +1,81 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+// PORT: done
+
+import java.util.Comparator;
+
+public class Header implements Comparable<Header>, Comparator<Header> {
+ private float score;
+ private int arity;
+ private Note note;
+
+ protected Header() {
+ score = 0.0f;
+ arity = 0;
+ note = null;
+ }
+
+ protected Header(Header other) {
+ this.score = other.GetScore();
+ this.arity = other.GetArity();
+ this.note = other.GetNote();
+ }
+
+ protected Header(int arity) {
+ this.score = 0.0f;
+ this.arity = arity;
+ this.note = new Note();
+ }
+
+ public boolean Valid() {
+ // C++: return base_;
+ System.err.println("Header::Valid(): " + (note != null));
+ return note != null;
+ }
+
+ public float GetScore() {
+ return score;
+ }
+
+ public void SetScore(float score) {
+ this.score = score;
+ }
+
+ public int GetArity() { return arity; }
+
+ public Note GetNote() { return note; }
+
+ public void SetNote(Note note) { this.note = note; }
+
+ @Override
+ public int compareTo(Header other) {
+ if (this.GetScore() < other.GetScore())
+ return -1;
+ else if (this.GetScore() > other.GetScore())
+ return 1;
+ return 0;
+ }
+
+ @Override
+ public int compare(Header arg0, Header arg1) {
+ return arg0.compareTo(arg1);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/Hypothesis.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/Hypothesis.java b/src/main/java/org/apache/joshua/decoder/phrase/Hypothesis.java
new file mode 100644
index 0000000..3d4bf51
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/Hypothesis.java
@@ -0,0 +1,154 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+import java.util.List;
+
+import joshua.corpus.Vocabulary;
+import joshua.decoder.ff.state_maintenance.DPState;
+import joshua.decoder.ff.tm.Rule;
+import joshua.decoder.ff.tm.format.HieroFormatReader;
+import joshua.decoder.hypergraph.HGNode;
+import joshua.decoder.hypergraph.HyperEdge;
+
+/**
+ * Represents a hypothesis, a translation of some coverage of the input. Extends {@link HGNode},
+ * through a bit of a hack. Whereas (i,j) represents the span of an {@link HGNode}, i here is not used,
+ * and j is overloaded to denote the span of the phrase being applied. The complete coverage vector
+ * can be obtained by looking at the tail pointer and casting it.
+ *
+ * @author Kenneth Heafield
+ * @author Matt Post <po...@cs.jhu.edu>
+ */
+public class Hypothesis extends HGNode implements Comparable<Hypothesis> {
+
+ // The hypothesis' coverage vector
+ private Coverage coverage;
+
+ public static Rule BEGIN_RULE = new HieroFormatReader().parseLine("[X] ||| <s> ||| <s> ||| ||| 0-0");
+ public static Rule END_RULE = new HieroFormatReader().parseLine("[GOAL] ||| [X,1] </s> ||| [X,1] </s> ||| ||| 0-0 1-1");
+
+ public String toString() {
+ StringBuffer sb = new StringBuffer();
+ for (DPState state: getDPStates())
+ sb.append(state);
+ String words = bestHyperedge.getRule().getEnglishWords();
+// return String.format("HYP[%s] %.5f j=%d words=%s state=%s", coverage, score, j, words, sb);
+ return String.format("HYP[%s] j=%d words=[%s] state=%s", coverage, j, words, sb);
+ }
+
+ // Initialize root hypothesis. Provide the LM's BeginSentence.
+ public Hypothesis(List<DPState> states, float futureCost) {
+ super(0, 1, Vocabulary.id("[X]"), states,
+ new HyperEdge(BEGIN_RULE, 0.0f, 0.0f, null, null), futureCost);
+ this.coverage = new Coverage(1);
+ }
+
+ public Hypothesis(Candidate cand) {
+ // TODO: sourcepath
+ super(-1, cand.span.end, Vocabulary.id("[X]"), cand.getStates(), new HyperEdge(
+ cand.getRule(), cand.getResult().getViterbiCost(), cand.getResult().getTransitionCost(),
+ cand.getTailNodes(), null), cand.score());
+ this.coverage = cand.getCoverage();
+ }
+
+ // Extend a previous hypothesis.
+ public Hypothesis(List<DPState> states, float score, Hypothesis previous, int source_end, Rule target) {
+ super(-1, source_end, -1, null, null, score);
+ this.coverage = previous.coverage;
+ }
+
+ public Coverage getCoverage() {
+ return coverage;
+ }
+
+ public Rule getRule() {
+ return bestHyperedge.getRule();
+ }
+
+ /**
+ * HGNodes (designed for chart parsing) maintain a span (i,j). We overload j
+ * here to record the index of the last translated source word.
+ *
+ * @return
+ */
+ public int LastSourceIndex() {
+ return j;
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 0;
+ hash = 31 * LastSourceIndex() + 19 * getCoverage().hashCode();
+ if (null != dpStates && dpStates.size() > 0)
+ for (DPState dps: dpStates)
+ hash *= 57 + dps.hashCode();
+ return hash;
+ }
+
+ /**
+ * Defines equivalence in terms of recombinability. Two hypotheses are recombinable if
+ * all their DP states are the same, their coverage is the same, and they have the next soure
+ * index the same.
+ */
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof Hypothesis) {
+ Hypothesis other = (Hypothesis) obj;
+
+ if (LastSourceIndex() != other.LastSourceIndex() || ! getCoverage().equals(other.getCoverage()))
+ return false;
+
+ if (dpStates == null)
+ return (other.dpStates == null);
+
+ if (other.dpStates == null)
+ return false;
+
+ if (dpStates.size() != other.dpStates.size())
+ return false;
+
+ for (int i = 0; i < dpStates.size(); i++) {
+ if (!dpStates.get(i).equals(other.dpStates.get(i)))
+ return false;
+ }
+
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public int compareTo(Hypothesis o) {
+ // TODO: is this the order we want?
+ return Float.compare(o.getScore(), getScore());
+ }
+
+ /**
+ * Performs hypothesis recombination, incorporating the incoming hyperedges of the added
+ * hypothesis and possibly updating the cache of the best incoming hyperedge and score.
+ *
+ * @param added the equivalent hypothesis
+ */
+ public void absorb(Hypothesis added) {
+ assert(this.equals(added));
+ score = Math.max(score, added.getScore());
+ addHyperedgesInNode(added.hyperedges);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/Note.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/Note.java b/src/main/java/org/apache/joshua/decoder/phrase/Note.java
new file mode 100644
index 0000000..19e6f62
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/Note.java
@@ -0,0 +1,44 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+// PORT: done
+
+public class Note {
+ public Object value;
+
+ public String toString() {
+ return value.toString();
+ }
+
+ public Note() {
+ }
+
+ public Note(Object value) {
+ this.value = value;
+ }
+
+ public Object get() {
+ return value;
+ }
+
+ public void set(Object object) {
+ this.value = object;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/8cdbc4b8/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java b/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java
new file mode 100644
index 0000000..a0179ff
--- /dev/null
+++ b/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java
@@ -0,0 +1,191 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file 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.
+ */
+package joshua.decoder.phrase;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import joshua.decoder.Decoder;
+import joshua.decoder.ff.FeatureFunction;
+import joshua.decoder.ff.tm.Rule;
+import joshua.decoder.ff.tm.RuleCollection;
+import joshua.decoder.segment_file.Sentence;
+
+/**
+ * This class represents a bundle of phrase tables that have been read in,
+ * reporting some stats about them. Probably could be done away with.
+ */
+public class PhraseChart {
+
+ private int sentence_length;
+ private int max_source_phrase_length;
+
+ // Banded array: different source lengths are next to each other.
+ private List<TargetPhrases> entries;
+
+ // number of translation options
+ int numOptions = 20;
+ private List<FeatureFunction> features;
+
+ /**
+ * Create a new PhraseChart object, which represents all phrases that are
+ * applicable against the current input sentence. These phrases are extracted
+ * from all available grammars.
+ *
+ * @param tables
+ * @param source
+ */
+ public PhraseChart(PhraseTable[] tables, List<FeatureFunction> features, Sentence source,
+ int num_options) {
+
+ float startTime = System.currentTimeMillis();
+
+ this.numOptions = num_options;
+ this.features = features;
+
+ max_source_phrase_length = 0;
+ for (int i = 0; i < tables.length; i++)
+ max_source_phrase_length = Math.max(max_source_phrase_length,
+ tables[i].getMaxSourcePhraseLength());
+ sentence_length = source.length();
+
+// System.err.println(String.format(
+// "PhraseChart()::Initializing chart for sentlen %d max %d from %s", sentence_length,
+// max_source_phrase_length, source));
+
+ entries = new ArrayList<TargetPhrases>();
+ for (int i = 0; i < sentence_length * max_source_phrase_length; i++)
+ entries.add(null);
+
+ // There's some unreachable ranges off the edge. Meh.
+ for (int begin = 0; begin != sentence_length; ++begin) {
+ for (int end = begin + 1; (end != sentence_length + 1)
+ && (end <= begin + max_source_phrase_length); ++end) {
+ if (source.hasPath(begin, end)) {
+ for (PhraseTable table : tables)
+ addToRange(begin, end,
+ table.getPhrases(Arrays.copyOfRange(source.getWordIDs(), begin, end)));
+ }
+
+ }
+ }
+
+ for (TargetPhrases phrases : entries) {
+ if (phrases != null)
+ phrases.finish(features, Decoder.weights, num_options);
+ }
+
+ Decoder.LOG(1, String.format("Input %d: Collecting options took %.3f seconds", source.id(),
+ (System.currentTimeMillis() - startTime) / 1000.0f));
+
+ if (Decoder.VERBOSE(3)) {
+ for (int i = 1; i < sentence_length - 1; i++) {
+ for (int j = i + 1; j < sentence_length && j <= i + max_source_phrase_length; j++) {
+ if (source.hasPath(i, j)) {
+ TargetPhrases phrases = getRange(i, j);
+ if (phrases != null) {
+ System.err.println(String.format("%s (%d-%d)", source.source(i,j), i, j));
+ for (Rule rule: phrases)
+ System.err.println(String.format(" %s :: est=%.3f", rule.getEnglishWords(), rule.getEstimatedCost()));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ public int SentenceLength() {
+ return sentence_length;
+ }
+
+ // c++: TODO: make this reflect the longest source phrase for this sentence.
+ public int MaxSourcePhraseLength() {
+ return max_source_phrase_length;
+ }
+
+ /**
+ * Maps two-dimensional span into a one-dimensional array.
+ *
+ * @param i
+ * @param j
+ * @return offset into private list of TargetPhrases
+ */
+ private int offset(int i, int j) {
+ return i * max_source_phrase_length + j - i - 1;
+ }
+
+ /**
+ * Returns phrases from all grammars that match the span.
+ *
+ * @param begin
+ * @param end
+ * @return
+ */
+ public TargetPhrases getRange(int begin, int end) {
+ int index = offset(begin, end);
+ // System.err.println(String.format("PhraseChart::Range(%d,%d): found %d entries",
+ // begin, end,
+ // entries.get(index) == null ? 0 : entries.get(index).size()));
+ // if (entries.get(index) != null)
+ // for (Rule phrase: entries.get(index))
+ // System.err.println(" RULE: " + phrase);
+
+ if (index < 0 || index >= entries.size() || entries.get(index) == null)
+ return null;
+
+ return entries.get(index);
+ }
+
+ /**
+ * Add a set of phrases from a grammar to the current span.
+ *
+ * @param begin
+ * @param end
+ * @param to
+ */
+ private void addToRange(int begin, int end, RuleCollection to) {
+ if (to != null) {
+ /*
+ * This first call to getSortedRules() is important, because it is what
+ * causes the scoring and sorting to happen. It is also a synchronized call,
+ * which is necessary because the underlying grammar gets sorted. Subsequent calls to get the
+ * rules will just return the already-sorted list. Here, we score, sort,
+ * and then trim the list to the number of translation options. Trimming provides huge
+ * performance gains --- the more common the word, the more translations options it is
+ * likely to have (often into the tens of thousands).
+ */
+ List<Rule> rules = to.getSortedRules(features);
+ if (numOptions > 0 && rules.size() > numOptions)
+ rules = rules.subList(0, numOptions);
+// to.getRules().subList(numOptions, to.getRules().size()).clear();
+
+ try {
+ int offset = offset(begin, end);
+ if (entries.get(offset) == null)
+ entries.set(offset, new TargetPhrases(rules));
+ else
+ entries.get(offset).addAll(rules);
+ } catch (java.lang.IndexOutOfBoundsException e) {
+ System.err.println(String.format("Whoops! %s [%d-%d] too long (%d)", to, begin, end,
+ entries.size()));
+ }
+ }
+ }
+}