You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@joshua.apache.org by mj...@apache.org on 2016/06/23 18:45:45 UTC
[34/60] [partial] incubator-joshua git commit: maven multi-module
layout 1st commit: moving files into joshua-core
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java
new file mode 100644
index 0000000..811521c
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WalkerFunction.java
@@ -0,0 +1,37 @@
+/*
+ * 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 org.apache.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.
+ * @param node the {{@link org.apache.joshua.decoder.hypergraph.HGNode} we
+ * wish to apply some Walker Function to.
+ * @param nodeIndex 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java
new file mode 100644
index 0000000..04d0897
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentExtractor.java
@@ -0,0 +1,134 @@
+/*
+ * 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 org.apache.joshua.decoder.hypergraph;
+
+import static java.util.Collections.emptyList;
+
+import java.util.List;
+import java.util.Stack;
+
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.joshua.decoder.hypergraph.KBestExtractor.DerivationState;
+import org.apache.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.
+ * @return a final alignment list
+ */
+ 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java
new file mode 100644
index 0000000..f057f23
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/WordAlignmentState.java
@@ -0,0 +1,192 @@
+/*
+ * 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 org.apache.joshua.decoder.hypergraph;
+
+import static java.lang.Integer.MAX_VALUE;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+
+import org.apache.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 List<AlignedSourceTokens> trgPoints;
+ private final 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)
+ *
+ * @param rule the input Rule
+ * @param start the start index
+ */
+ public WordAlignmentState(final Rule rule, final int start) {
+ trgPoints = new LinkedList<AlignedSourceTokens>();
+ srcLength = rule.getFrench().length;
+ numNT = rule.getArity();
+ srcStart = start;
+ final Map<Integer, List<Integer>> alignmentMap = rule.getAlignmentMap();
+ final int[] nonTerminalSourcePositions = rule.getNonTerminalSourcePositions();
+ final int[] trg = rule.getEnglish();
+ // for each target index, create a TargetAlignmentPoint
+ for (int trgIndex = 0; trgIndex < trg.length; trgIndex++) {
+ final 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(); // mark as non-terminal
+ final int absoluteNonTerminalSourcePosition = srcStart + nonTerminalSourcePositions[Math.abs(trg[trgIndex]) - 1];
+ trgPoint.add(absoluteNonTerminalSourcePosition);
+ }
+ trgPoints.add(trgPoint);
+ }
+ }
+
+ /**
+ * if there are no more NonTerminals to substitute,
+ * this state is said to be complete
+ * @return true if 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.
+ * @return result string
+ */
+ public String toFinalString() {
+ final 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++;
+ }
+ final 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.
+ * @return a final alignment list
+ */
+ public List<List<Integer>> toFinalList() {
+ final List<List<Integer>> alignment = new ArrayList<List<Integer>>(trgPoints.size());
+ if (trgPoints.isEmpty()) {
+ return alignment;
+ }
+ final ListIterator<AlignedSourceTokens> it = trgPoints.listIterator();
+ it.next(); // skip first item (sentence marker)
+ while (it.hasNext()) {
+ final AlignedSourceTokens alignedSourceTokens = it.next();
+ if (it.hasNext()) { // if not last element in trgPoints
+ final 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.
+ */
+ @Override
+ 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 next
+ * nonterminal slot. 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.
+ *
+ * @param child The child
+ */
+ public void substituteIn(WordAlignmentState child) {
+ // find the index of the NonTerminal where we substitute the child targetPoints into.
+ // The correct NT is the first one on the SOURCE side.
+ // Also shift all trgPoints by the child length.
+ int substitutionIndex = 0;
+ int sourcePosition = MAX_VALUE;
+ for (final ListIterator<AlignedSourceTokens> trgPointsIterator = trgPoints.listIterator(); trgPointsIterator.hasNext();) {
+ final AlignedSourceTokens trgPoint = trgPointsIterator.next();
+ trgPoint.shiftBy(child.srcStart, child.srcLength - 1);
+ if (trgPoint.isNonTerminal() && trgPoint.get(0) < sourcePosition) {
+ sourcePosition = trgPoint.get(0);
+ substitutionIndex = trgPointsIterator.previousIndex();
+ }
+ }
+
+ // point and remove NT element determined from above
+ final ListIterator<AlignedSourceTokens> insertionIterator = trgPoints.listIterator(substitutionIndex);
+ insertionIterator.next();
+ insertionIterator.remove();
+
+ // insert child target points and set them to final.
+ for (AlignedSourceTokens childElement : child.trgPoints) {
+ childElement.setFinal();
+ insertionIterator.add(childElement);
+ }
+
+ // update length and number of non terminal slots
+ this.srcLength += child.srcLength - 1; // -1 (NT)
+ this.numNT--;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/package-info.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/package-info.java b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/package-info.java
new file mode 100644
index 0000000..05e66e2
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/hypergraph/package-info.java
@@ -0,0 +1,25 @@
+/*
+ * 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.
+ */
+
+/**
+ * Provides implementations of hypergraph data structures
+ * and related algorithms used in extracting translation
+ * results in hierarchical phrase-based translation.
+ */
+package org.apache.joshua.decoder.hypergraph;
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java b/joshua-core/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java
new file mode 100644
index 0000000..cc6e839
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/io/DeNormalize.java
@@ -0,0 +1,203 @@
+/*
+ * 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 org.apache.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>
+ * <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>
+ * <b>N.B.</b> 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>
+ */
+
+public class DeNormalize {
+
+ /**
+ * Apply all the denormalization methods to the normalized input line.
+ *
+ * @param normalized a normalized input line
+ * @return the denormalized String
+ */
+ 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java b/joshua-core/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java
new file mode 100644
index 0000000..9c3899e
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/io/JSONMessage.java
@@ -0,0 +1,159 @@
+/*
+ * 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 org.apache.joshua.decoder.io;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.google.gson.Gson;
+import com.google.gson.GsonBuilder;
+
+import org.apache.joshua.decoder.StructuredTranslation;
+import org.apache.joshua.decoder.Translation;
+
+/**
+ * Represents a JSON object returned by the server. The object has the format
+ *
+ * { data: {
+ * translations: [
+ * { annotatedSource: "",
+ * translatedText: "",
+ * raw_nbest: [
+ * { hyp: "",
+ * totalScore: 0.0, } ]
+ * tokenization: { ... }
+ * translatedTextRaw: "",
+ * nbest: [
+ * { translatedText: "",
+ * translatedTextRaw: "",
+ * tokenization: { ... } } ] } ] } }
+ *
+ * @author post
+ */
+
+public class JSONMessage {
+ public Data data = null;
+ public List<String> metadata = null;
+ public JSONMessage() {
+ metadata = new ArrayList<String>();
+ }
+
+ public class Data {
+ public List<TranslationItem> translations;
+
+ public Data() {
+ translations = new ArrayList<TranslationItem>();
+ }
+ }
+//
+// public class Metadata {
+// public String metadata = null;
+// public List<String> rules = null;
+//
+// public Metadata() {
+// rules = new ArrayList<String>();
+// }
+// }
+
+ public void addTranslation(Translation translation) {
+ String viterbi = translation.getStructuredTranslations().get(0).getTranslationString();
+
+ TranslationItem item = addTranslation(viterbi);
+
+ for (StructuredTranslation hyp: translation.getStructuredTranslations()) {
+ String text = hyp.getFormattedTranslationString();
+ float score = hyp.getTranslationScore();
+
+ item.addHypothesis(text, score);
+ }
+
+ // old string-based k-best output
+ // String[] results = translation.toString().split("\\n");
+ // if (results.length > 0) {
+ // String rawTranslation = results[0].split(" \\|\\|\\| ")[1];
+ // JSONMessage.TranslationItem item = message.addTranslation(rawTranslation);
+ //
+ // for (String result: results) {
+ // String[] tokens = result.split(" \\|\\|\\| ");
+ // String rawResult = tokens[1];
+ // float score = Float.parseFloat(tokens[3]);
+ // item.addHypothesis(rawResult, score);
+ // }
+ // }
+ }
+
+ /**
+ * Adds a new Translation to the JSON object. A Translation represents one or more hypotheses
+ * (or k-best items)
+ *
+ * @param text
+ * @return the new TranslationItem object
+ */
+ public TranslationItem addTranslation(String text) {
+ if (data == null)
+ data = new Data();
+
+ TranslationItem newItem = new TranslationItem(text);
+ data.translations.add(newItem);
+ return newItem;
+ }
+
+ public void addMetaData(String msg) {
+ this.metadata.add(msg);
+ }
+
+ public class TranslationItem {
+ public String translatedText;
+ public List<NBestItem> raw_nbest;
+
+ public TranslationItem(String value) {
+ this.translatedText = value;
+ this.raw_nbest = new ArrayList<NBestItem>();
+ }
+
+ /**
+ * Adds a new item to the translation's list of k-best items
+ *
+ * @param hyp the hypothesis
+ * @param score its score
+ */
+ 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) {
+ metadata.add("custom_rule " + rule);
+ }
+
+ public String toString() {
+ Gson gson = new GsonBuilder().setPrettyPrinting().create();
+ return gson.toJson(this) + "\n";
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java b/joshua-core/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java
new file mode 100644
index 0000000..0287688
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/io/TranslationRequestStream.java
@@ -0,0 +1,179 @@
+/*
+ * 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 org.apache.joshua.decoder.io;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.Reader;
+
+import com.google.gson.stream.JsonReader;
+
+import org.apache.joshua.decoder.JoshuaConfiguration;
+import org.apache.joshua.decoder.JoshuaConfiguration.INPUT_TYPE;
+import org.apache.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:
+ * <pre>
+ * {
+ * "data": {
+ * "translations": [
+ * { "sourceText": "sentence to be translated" },
+ * { "sourceText": "next sentence" },
+ * { "sourceText": "@some command to run" }
+ * ]
+ * }
+ * }
+ * </pre>
+ * @author Matt Post post@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;
+ }
+
+ 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 {
+ line = null;
+
+ if (reader.hasNext()) {
+ reader.beginObject();
+ reader.nextName();
+ line = reader.nextString();
+ reader.endObject();
+ }
+
+ if (line == null)
+ return null;
+
+ 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 {
+
+ String line = reader.readLine();
+
+ if (line != null) {
+ 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() {
+ 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/package-info.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/package-info.java b/joshua-core/src/main/java/org/apache/joshua/decoder/package-info.java
new file mode 100644
index 0000000..af1127b
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/package-info.java
@@ -0,0 +1,26 @@
+/*
+ * 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.
+ */
+/**
+ * Provides infrastructure and wrapper code used relevant to
+ * hierarchical phrase-based decoding for statistical machine
+ * translation. This package does not include an implementation
+ * of any actual decoding algorithm. Rather, such code is in
+ * child packages of this package.
+ */
+package org.apache.joshua.decoder;
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Candidate.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Candidate.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Candidate.java
new file mode 100644
index 0000000..ee8a2a9
--- /dev/null
+++ b/joshua-core/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 org.apache.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 org.apache.joshua.corpus.Span;
+import org.apache.joshua.decoder.chart_parser.ComputeNodeResult;
+import org.apache.joshua.decoder.ff.state_maintenance.DPState;
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.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 org.apache.joshua.corpus.Phrase}, which is a {@link org.apache.joshua.decoder.ff.tm.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 the bit vector of this hypothesis
+ */
+ public Coverage getCoverage() {
+ Coverage cov = new Coverage(getHypothesis().getCoverage());
+ cov.set(getSpan());
+ return cov;
+ }
+
+ /**
+ * Sets the result of a candidate (TODO should just be moved to the constructor).
+ *
+ * @param result todo
+ */
+ 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 the sum of two costs: the HypoState cost + the transition cost
+ */
+ 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/CandidateComparator.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/CandidateComparator.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/CandidateComparator.java
new file mode 100644
index 0000000..322f47a
--- /dev/null
+++ b/joshua-core/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 org.apache.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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java
new file mode 100644
index 0000000..2c674fc
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Coverage.java
@@ -0,0 +1,235 @@
+/*
+ * 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 org.apache.joshua.decoder.phrase;
+
+import java.util.BitSet;
+
+import org.apache.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 other an existing coverage vector from which to create a new coverage vector
+ */
+ 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 bits at start position
+ * @param end bits at end position (end - 1)
+ */
+ 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.
+ * @param span todo
+ */
+ 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 todo
+ */
+ 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
+ * <pre>
+ * (LeftOpen(begin), RightOpen(end, sentence_length))
+ * </pre>
+ *
+ * provides this gap.
+ *
+ * Finds the right bound of the enclosing gap, or the end of sentence, whichever is less.
+ * @param end end of phrase pair
+ * @param sentenceLength length of sentence
+ * @return todo
+ */
+ 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 {@link java.util.BitSet} vector of bits
+ */
+ 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Future.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Future.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Future.java
new file mode 100644
index 0000000..0ece4a3
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Future.java
@@ -0,0 +1,119 @@
+/*
+ * 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 org.apache.joshua.decoder.phrase;
+
+import org.apache.joshua.util.ChartSpan;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public class Future {
+
+ private static final Logger LOG = LoggerFactory.getLogger(Future.class);
+
+ // 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 org.apache.joshua.decoder.phrase.PhraseChart}.
+ * Requires that there be a translation at least for every word (which can be
+ * accomplished with a pass-through grammar).
+ *
+ * @param chart an input {@link org.apache.joshua.decoder.phrase.PhraseChart}
+ */
+ 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 (LOG.isDebugEnabled()) {
+ for (int i = 1; i < chart.SentenceLength(); i++) {
+ for (int j = i + 1; j < chart.SentenceLength(); j++) {
+ LOG.debug("future cost from {} to {} is {}", 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.
+ * @param coverage input {@link org.apache.joshua.decoder.phrase.Coverage} vector
+ * @param begin word at which to begin within a sentence
+ * @param end word at which to end within a sentence
+ * @return a float value representing a {@link Future} entry
+ */
+ 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Header.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Header.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Header.java
new file mode 100644
index 0000000..30d771c
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Header.java
@@ -0,0 +1,87 @@
+/*
+ * 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 org.apache.joshua.decoder.phrase;
+
+// PORT: done
+
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.util.Comparator;
+
+public class Header implements Comparable<Header>, Comparator<Header> {
+
+ private static final Logger LOG = LoggerFactory.getLogger(Header.class);
+
+ 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_;
+ LOG.debug("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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Hypothesis.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Hypothesis.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Hypothesis.java
new file mode 100644
index 0000000..71d3df9
--- /dev/null
+++ b/joshua-core/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 org.apache.joshua.decoder.phrase;
+
+import java.util.List;
+
+import org.apache.joshua.corpus.Vocabulary;
+import org.apache.joshua.decoder.ff.state_maintenance.DPState;
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.joshua.decoder.ff.tm.format.HieroFormatReader;
+import org.apache.joshua.decoder.hypergraph.HGNode;
+import org.apache.joshua.decoder.hypergraph.HyperEdge;
+
+/**
+ * Represents a hypothesis, a translation of some coverage of the input. Extends {@link org.apache.joshua.decoder.hypergraph.HGNode},
+ * through a bit of a hack. Whereas (i,j) represents the span of an {@link org.apache.joshua.decoder.hypergraph.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 post@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 the int 'j' which is overloaded to denote the span of the phrase being applied
+ */
+ 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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Note.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Note.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/Note.java
new file mode 100644
index 0000000..15b0057
--- /dev/null
+++ b/joshua-core/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 org.apache.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/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java
new file mode 100644
index 0000000..9803d9b
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseChart.java
@@ -0,0 +1,197 @@
+/*
+ * 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 org.apache.joshua.decoder.phrase;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.joshua.decoder.Decoder;
+import org.apache.joshua.decoder.ff.FeatureFunction;
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.joshua.decoder.ff.tm.RuleCollection;
+import org.apache.joshua.decoder.segment_file.Sentence;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * 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 static final Logger LOG = LoggerFactory.getLogger(PhraseChart.class);
+
+ 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 input array of {@link org.apache.joshua.decoder.phrase.PhraseTable}'s
+ * @param features {@link java.util.List} of {@link org.apache.joshua.decoder.ff.FeatureFunction}'s
+ * @param source input to {@link org.apache.joshua.lattice.Lattice}
+ * @param num_options number of translation options (typically set to 20)
+ */
+ 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);
+ }
+
+ LOG.info("Input {}: Collecting options took {} seconds", source.id(),
+ (System.currentTimeMillis() - startTime) / 1000.0f);
+
+ if (LOG.isDebugEnabled()) {
+ 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) {
+ LOG.debug("{} ({}-{})", source.source(i,j), i, j);
+ for (Rule rule: phrases)
+ LOG.debug(" {} :: est={}", 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 beginning of span
+ * @param j end of span
+ * @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 beginning of span
+ * @param end end of span
+ * @return the {@link org.apache.joshua.decoder.phrase.TargetPhrases} at the specified position in this list.
+ */
+ 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 beginning of span
+ * @param end end of span
+ * @param to a {@link org.apache.joshua.decoder.ff.tm.RuleCollection} to be used in scoring and sorting.
+ */
+ 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) {
+ LOG.error("Whoops! {} [{}-{}] too long ({})", to, begin, end, entries.size());
+ LOG.error(e.getMessage(), e);
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseTable.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseTable.java b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseTable.java
new file mode 100644
index 0000000..27f92ac
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/phrase/PhraseTable.java
@@ -0,0 +1,181 @@
+/*
+ * 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 org.apache.joshua.decoder.phrase;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.List;
+
+import org.apache.joshua.corpus.Vocabulary;
+import org.apache.joshua.decoder.JoshuaConfiguration;
+import org.apache.joshua.decoder.ff.FeatureFunction;
+import org.apache.joshua.decoder.ff.tm.Grammar;
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.joshua.decoder.ff.tm.RuleCollection;
+import org.apache.joshua.decoder.ff.tm.Trie;
+import org.apache.joshua.decoder.ff.tm.hash_based.MemoryBasedBatchGrammar;
+import org.apache.joshua.decoder.ff.tm.packed.PackedGrammar;
+
+/**
+ * Represents a phrase table, and is implemented as a wrapper around either a {@link PackedGrammar}
+ * or a {@link MemoryBasedBatchGrammar}.
+ *
+ * TODO: this should all be implemented as a two-level trie (source trie and target trie).
+ */
+public class PhraseTable implements Grammar {
+
+ private JoshuaConfiguration config;
+ private Grammar backend;
+
+ /**
+ * Chain to the super with a number of defaults. For example, we only use a single nonterminal,
+ * and there is no span limit.
+ *
+ * @param grammarFile file path parent directory
+ * @param owner used to set phrase owners
+ * @param type the grammar specification keyword (e.g., "thrax" or "moses")
+ * @param config a populated {@link org.apache.joshua.decoder.JoshuaConfiguration}
+ * @throws IOException if there is an error reading the grammar file
+ */
+ public PhraseTable(String grammarFile, String owner, String type, JoshuaConfiguration config)
+ throws IOException {
+ this.config = config;
+ int spanLimit = 0;
+
+ if (grammarFile != null && new File(grammarFile).isDirectory()) {
+ this.backend = new PackedGrammar(grammarFile, spanLimit, owner, type, config);
+ if (this.backend.getMaxSourcePhraseLength() == -1) {
+ String msg = "FATAL: Using a packed grammar for a phrase table backend requires that you "
+ + "packed the grammar with Joshua 6.0.2 or greater";
+ throw new RuntimeException(msg);
+ }
+
+ } else {
+ this.backend = new MemoryBasedBatchGrammar(type, grammarFile, owner, "[X]", spanLimit, config);
+ }
+ }
+
+ public PhraseTable(String owner, JoshuaConfiguration config) {
+ this.config = config;
+
+ this.backend = new MemoryBasedBatchGrammar(owner, config);
+ }
+
+ /**
+ * Returns the longest source phrase read. Because phrases have a dummy nonterminal prepended to
+ * them, we need to subtract 1.
+ *
+ * @return the longest source phrase read.
+ */
+ @Override
+ public int getMaxSourcePhraseLength() {
+ return this.backend.getMaxSourcePhraseLength() - 1;
+ }
+
+ /**
+ * Collect the set of target-side phrases associated with a source phrase.
+ *
+ * @param sourceWords the sequence of source words
+ * @return the rules
+ */
+ public RuleCollection getPhrases(int[] sourceWords) {
+ if (sourceWords.length != 0) {
+ Trie pointer = getTrieRoot();
+ pointer = pointer.match(Vocabulary.id("[X]"));
+ int i = 0;
+ while (pointer != null && i < sourceWords.length)
+ pointer = pointer.match(sourceWords[i++]);
+
+ if (pointer != null && pointer.hasRules()) {
+ return pointer.getRuleCollection();
+ }
+ }
+
+ return null;
+ }
+
+ /**
+ * Adds a rule to the grammar. Only supported when the backend is a MemoryBasedBatchGrammar.
+ *
+ * @param rule the rule to add
+ */
+ public void addRule(Rule rule) {
+ ((MemoryBasedBatchGrammar)backend).addRule(rule);
+ }
+
+ @Override
+ public void addOOVRules(int sourceWord, List<FeatureFunction> featureFunctions) {
+ // TODO: _OOV shouldn't be outright added, since the word might not be OOV for the LM (but now almost
+ // certainly is)
+ int targetWord = config.mark_oovs
+ ? Vocabulary.id(Vocabulary.word(sourceWord) + "_OOV")
+ : sourceWord;
+
+ int nt_i = Vocabulary.id("[X]");
+ Rule oovRule = new Rule(nt_i, new int[] { nt_i, sourceWord },
+ new int[] { -1, targetWord }, "", 1, null);
+ addRule(oovRule);
+ oovRule.estimateRuleCost(featureFunctions);
+
+// String ruleString = String.format("[X] ||| [X,1] %s ||| [X,1] %s",
+// Vocabulary.word(sourceWord), Vocabulary.word(targetWord));
+// Rule oovRule = new HieroFormatReader().parseLine(ruleString);
+// oovRule.setOwner(Vocabulary.id("oov"));
+// addRule(oovRule);
+// oovRule.estimateRuleCost(featureFunctions);
+ }
+
+ @Override
+ public Trie getTrieRoot() {
+ return backend.getTrieRoot();
+ }
+
+ @Override
+ public void sortGrammar(List<FeatureFunction> models) {
+ backend.sortGrammar(models);
+ }
+
+ @Override
+ public boolean isSorted() {
+ return backend.isSorted();
+ }
+
+ /**
+ * This should never be called.
+ */
+ @Override
+ public boolean hasRuleForSpan(int startIndex, int endIndex, int pathLength) {
+ return true;
+ }
+
+ @Override
+ public int getNumRules() {
+ return backend.getNumRules();
+ }
+
+ @Override
+ public int getOwner() {
+ return backend.getOwner();
+ }
+
+ @Override
+ public int getNumDenseFeatures() {
+ return backend.getNumDenseFeatures();
+ }
+}