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:51 UTC
[40/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/ff/TargetBigram.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/TargetBigram.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/TargetBigram.java
new file mode 100644
index 0000000..e7de1f8
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/TargetBigram.java
@@ -0,0 +1,216 @@
+/*
+ * 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.ff;
+
+import java.io.IOException;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.apache.joshua.corpus.Vocabulary;
+import org.apache.joshua.decoder.JoshuaConfiguration;
+import org.apache.joshua.decoder.chart_parser.SourcePath;
+import org.apache.joshua.decoder.ff.state_maintenance.DPState;
+import org.apache.joshua.decoder.ff.state_maintenance.NgramDPState;
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.joshua.decoder.hypergraph.HGNode;
+import org.apache.joshua.decoder.segment_file.Sentence;
+import org.apache.joshua.util.FormatUtils;
+import org.apache.joshua.util.io.LineReader;
+
+/***
+ * The RuleBigram feature is an indicator feature that counts target word bigrams that are created when
+ * a rule is applied. It accepts three parameters:
+ *
+ * -vocab /path/to/vocab
+ *
+ * The path to a vocabulary, where each line is of the format ID WORD COUNT.
+ *
+ * -threshold N
+ *
+ * Mask to UNK all words whose COUNT is less than N.
+ *
+ * -top-n N
+ *
+ * Only use the top N words.
+ */
+
+public class TargetBigram extends StatefulFF {
+
+ private HashSet<String> vocab = null;
+ private int maxTerms = 1000000;
+ private int threshold = 0;
+
+ public TargetBigram(FeatureVector weights, String[] args, JoshuaConfiguration config) {
+ super(weights, "TargetBigram", args, config);
+
+ if (parsedArgs.containsKey("threshold"))
+ threshold = Integer.parseInt(parsedArgs.get("threshold"));
+
+ if (parsedArgs.containsKey("top-n"))
+ maxTerms = Integer.parseInt(parsedArgs.get("top-n"));
+
+ if (parsedArgs.containsKey("vocab")) {
+ loadVocab(parsedArgs.get("vocab"));
+ }
+ }
+
+ /**
+ * Load vocabulary items passing the 'threshold' and 'top-n' filters.
+ *
+ * @param filename
+ */
+ private void loadVocab(String filename) {
+ this.vocab = new HashSet<String>();
+ this.vocab.add("<s>");
+ this.vocab.add("</s>");
+ try {
+ LineReader lineReader = new LineReader(filename);
+ for (String line: lineReader) {
+ if (lineReader.lineno() > maxTerms)
+ break;
+
+ String[] tokens = line.split("\\s+");
+ String word = tokens[1];
+ int count = Integer.parseInt(tokens[2]);
+
+ if (count >= threshold)
+ vocab.add(word);
+ }
+
+ } catch (IOException e) {
+ throw new RuntimeException(String.format(
+ "* FATAL: couldn't load TargetBigram vocabulary '%s'", filename), e);
+ }
+ }
+
+ @Override
+ public DPState compute(Rule rule, List<HGNode> tailNodes, int spanStart, int spanEnd,
+ SourcePath sourcePath, Sentence sentence, Accumulator acc) {
+
+ int[] enWords = rule.getEnglish();
+
+ int left = -1;
+ int right = -1;
+
+ List<String> currentNgram = new LinkedList<String>();
+ for (int c = 0; c < enWords.length; c++) {
+ int curID = enWords[c];
+
+ if (FormatUtils.isNonterminal(curID)) {
+ int index = -(curID + 1);
+ NgramDPState state = (NgramDPState) tailNodes.get(index).getDPState(stateIndex);
+ int[] leftContext = state.getLeftLMStateWords();
+ int[] rightContext = state.getRightLMStateWords();
+
+ // Left context.
+ for (int token : leftContext) {
+ currentNgram.add(getWord(token));
+ if (left == -1)
+ left = token;
+ right = token;
+ if (currentNgram.size() == 2) {
+ String ngram = join(currentNgram);
+ acc.add(String.format("%s_%s", name, ngram), 1);
+ // System.err.println(String.format("ADDING %s_%s", name, ngram));
+ currentNgram.remove(0);
+ }
+ }
+ // Replace right context.
+ int tSize = currentNgram.size();
+ for (int i = 0; i < rightContext.length; i++)
+ currentNgram.set(tSize - rightContext.length + i, getWord(rightContext[i]));
+
+ } else { // terminal words
+ currentNgram.add(getWord(curID));
+ if (left == -1)
+ left = curID;
+ right = curID;
+ if (currentNgram.size() == 2) {
+ String ngram = join(currentNgram);
+ acc.add(String.format("%s_%s", name, ngram), 1);
+ // System.err.println(String.format("ADDING %s_%s", name, ngram));
+ currentNgram.remove(0);
+ }
+ }
+ }
+
+ NgramDPState state = new NgramDPState(new int[] { left }, new int[] { right });
+ // System.err.println(String.format("RULE %s -> state %s", rule.getRuleString(), state));
+ return state;
+ }
+
+ /**
+ * Returns the word after comparing against the private vocabulary (if set).
+ *
+ * @param curID
+ * @return the word
+ */
+ private String getWord(int curID) {
+ String word = Vocabulary.word(curID);
+
+ if (vocab != null && ! vocab.contains(word)) {
+ return "UNK";
+ }
+
+ return word;
+ }
+
+ /**
+ * We don't compute a future cost.
+ */
+ @Override
+ public float estimateFutureCost(Rule rule, DPState state, Sentence sentence) {
+ return 0.0f;
+ }
+
+ /**
+ * There is nothing to be done here, since <s> and </s> are included in rules that are part
+ * of the grammar. We simply return the DP state of the tail node.
+ */
+ @Override
+ public DPState computeFinal(HGNode tailNode, int i, int j, SourcePath sourcePath,
+ Sentence sentence, Accumulator acc) {
+
+ return tailNode.getDPState(stateIndex);
+ }
+
+ /**
+ * TargetBigram features are only computed across hyperedges, so there is nothing to be done here.
+ */
+ @Override
+ public float estimateCost(Rule rule, Sentence sentence) {
+ return 0.0f;
+ }
+
+ /**
+ * Join a list with the _ character. I am sure this is in a library somewhere.
+ *
+ * @param list a list of strings
+ * @return the joined String
+ */
+ private String join(List<String> list) {
+ StringBuilder sb = new StringBuilder();
+ for (String item : list) {
+ sb.append(item.toString() + "_");
+ }
+
+ return sb.substring(0, sb.length() - 1);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/ff/WordPenalty.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/WordPenalty.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/WordPenalty.java
new file mode 100644
index 0000000..da315ec
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/WordPenalty.java
@@ -0,0 +1,80 @@
+/*
+ * 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.ff;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.joshua.decoder.JoshuaConfiguration;
+import org.apache.joshua.decoder.ff.state_maintenance.DPState;
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.joshua.decoder.chart_parser.SourcePath;
+import org.apache.joshua.decoder.hypergraph.HGNode;
+import org.apache.joshua.decoder.phrase.Hypothesis;
+import org.apache.joshua.decoder.segment_file.Sentence;
+
+/**
+ *
+ * @author Zhifei Li zhifei.work@gmail.com
+ * @author Matt Post post@cs.jhu.edu
+ */
+public final class WordPenalty extends StatelessFF {
+
+ private float OMEGA = -(float) Math.log10(Math.E); // -0.435
+ private final boolean isCky;
+
+ public WordPenalty(final FeatureVector weights, String[] args, JoshuaConfiguration config) {
+ super(weights, "WordPenalty", args, config);
+
+ if (parsedArgs.containsKey("value"))
+ OMEGA = Float.parseFloat(parsedArgs.get("value"));
+
+ isCky = config.search_algorithm.equals("cky");
+ }
+
+ @Override
+ public DPState compute(Rule rule, List<HGNode> tailNodes, int i, int j, SourcePath sourcePath,
+ Sentence sentence, Accumulator acc) {
+
+ if (rule != null) {
+ // TODO: this is an inefficient way to do this. Find a better way to not apply this rule
+ // to start and stop glue rules when phrase-based decoding.
+ if (isCky || (rule != Hypothesis.BEGIN_RULE && rule != Hypothesis.END_RULE)) {
+ acc.add(denseFeatureIndex, OMEGA * (rule.getEnglish().length - rule.getArity()));
+ }
+ }
+
+ return null;
+ }
+
+ @Override
+ public ArrayList<String> reportDenseFeatures(int index) {
+ denseFeatureIndex = index;
+ ArrayList<String> names = new ArrayList<>(1);
+ names.add(name);
+ return names;
+ }
+
+ @Override
+ public float estimateCost(Rule rule, Sentence sentence) {
+ if (rule != null)
+ return weights.getDense(denseFeatureIndex) * OMEGA * (rule.getEnglish().length - rule.getArity());
+ return 0.0f;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/ConcatenationIterator.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/ConcatenationIterator.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/ConcatenationIterator.java
new file mode 100644
index 0000000..f75dffa
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/ConcatenationIterator.java
@@ -0,0 +1,93 @@
+/*
+ * 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.ff.fragmentlm;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+/**
+ * Concatenates an iterator over iterators into one long iterator.
+ *
+ * @author Dan Klein
+ */
+public class ConcatenationIterator<E> implements Iterator<E> {
+
+ Iterator<Iterator<E>> sourceIterators;
+ Iterator<E> currentIterator;
+ Iterator<E> lastIteratorToReturn;
+
+ public boolean hasNext() {
+ if (currentIterator.hasNext())
+ return true;
+ return false;
+ }
+
+ public E next() {
+ if (currentIterator.hasNext()) {
+ E e = currentIterator.next();
+ lastIteratorToReturn = currentIterator;
+ advance();
+ return e;
+ }
+ throw new NoSuchElementException();
+ }
+
+ private void advance() {
+ while (! currentIterator.hasNext() && sourceIterators.hasNext()) {
+ currentIterator = sourceIterators.next();
+ }
+ }
+
+ public void remove() {
+ if (lastIteratorToReturn == null)
+ throw new IllegalStateException();
+ currentIterator.remove();
+ }
+
+ public ConcatenationIterator(Iterator<Iterator<E>> sourceIterators) {
+ this.sourceIterators = sourceIterators;
+ this.currentIterator = (new ArrayList<E>()).iterator();
+ this.lastIteratorToReturn = null;
+ advance();
+ }
+
+ public ConcatenationIterator(Collection<Iterator<E>> iteratorCollection) {
+ this(iteratorCollection.iterator());
+ }
+
+ public static void main(String[] args) {
+ List<String> list0 = Collections.emptyList();
+ List<String> list1 = Arrays.asList("a b c d".split(" "));
+ List<String> list2 = Arrays.asList("e f".split(" "));
+ List<Iterator<String>> iterators = new ArrayList<Iterator<String>>();
+ iterators.add(list1.iterator());
+ iterators.add(list0.iterator());
+ iterators.add(list2.iterator());
+ iterators.add(list0.iterator());
+ Iterator<String> iterator = new ConcatenationIterator<String>(iterators);
+ while (iterator.hasNext()) {
+ System.out.println(iterator.next());
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/FragmentLMFF.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/FragmentLMFF.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/FragmentLMFF.java
new file mode 100644
index 0000000..fa4c4af
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/FragmentLMFF.java
@@ -0,0 +1,365 @@
+/*
+ * 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.ff.fragmentlm;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Stack;
+
+import org.apache.joshua.decoder.JoshuaConfiguration;
+import org.apache.joshua.decoder.chart_parser.SourcePath;
+import org.apache.joshua.decoder.ff.FeatureVector;
+import org.apache.joshua.decoder.ff.StatefulFF;
+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;
+import org.apache.joshua.decoder.segment_file.Sentence;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * <p>Feature function that reads in a list of language model fragments and matches them against the
+ * hypergraph. This allows for language model fragment "glue" features, which fire when LM fragments
+ * (supplied as input) are assembled. These LM fragments are presumably useful in ensuring
+ * grammaticality and can be independent of the translation model fragments.</p>
+ *
+ * <p>Usage: in the Joshua Configuration file, put</p>
+ *
+ * <code>feature-function = FragmentLM -lm LM_FRAGMENTS_FILE -map RULE_FRAGMENTS_MAP_FILE</code>
+ *
+ * <p>LM_FRAGMENTS_FILE is a pointer to a file containing a list of fragments that it should look for.
+ * The format of the file is one fragment per line in PTB format, e.g.:</p>
+ *
+ * <code>(S NP (VP (VBD said) SBAR) (. .))</code>
+ *
+ * <p>RULE_FRAGMENTS_MAP_FILE points to a file that maps fragments to the flattened SCFG rule format
+ * that Joshua uses. This mapping is necessary because Joshua's rules have been flattened, meaning
+ * that their internal structure has been removed, yet this structure is needed for matching LM
+ * fragments. The format of the file is</p>
+ *
+ * <code>FRAGMENT ||| RULE-TARGET-SIDE</code>
+ *
+ * <p>for example,</p>
+ *
+ * <code>(S (NP (DT the) (NN man)) VP .) ||| the man [VP,1] [.,2] (SBAR (IN that) (S (NP (PRP he)) (VP
+ * (VBD was) (VB done)))) ||| that he was done (VP (VBD said) SBAR) ||| said SBAR</code>
+ *
+ * @author Matt Post post@cs.jhu.edu
+ */
+public class FragmentLMFF extends StatefulFF {
+
+ private static final Logger LOG = LoggerFactory.getLogger(FragmentLMFF.class);
+
+ /*
+ * When building a fragment from a rule rooted in the hypergraph, this parameter determines how
+ * deep we'll go. Smaller values mean less hypergraph traversal but may also limit the LM
+ * fragments that can be fired.
+ */
+ private int BUILD_DEPTH = 1;
+
+ /*
+ * The maximum depth of a fragment, defined as the longest path from the fragment root to any of
+ * its leaves.
+ */
+ private int MAX_DEPTH = 0;
+
+ /*
+ * This is the minimum depth for lexicalized LM fragments. This allows you to easily exclude small
+ * depth-one fragments that may be overfit to the training data. A depth of 1 (the default) does
+ * not exclude any fragments.
+ */
+ private int MIN_LEX_DEPTH = 1;
+
+ /*
+ * Set to true to activate meta-features.
+ */
+ private boolean OPTS_DEPTH = false;
+
+ /*
+ * This contains a list of the language model fragments, indexed by LHS.
+ */
+ private HashMap<String, ArrayList<Tree>> lmFragments = null;
+
+ private int numFragments = 0;
+
+ /* The location of the file containing the language model fragments */
+ private String fragmentLMFile = "";
+
+ /**
+ * @param weights a {@link org.apache.joshua.decoder.ff.FeatureVector} with weights
+ * @param args arguments passed to the feature function
+ * @param config the {@link org.apache.joshua.decoder.JoshuaConfiguration}
+ */
+ public FragmentLMFF(FeatureVector weights, String[] args, JoshuaConfiguration config) {
+ super(weights, "FragmentLMFF", args, config);
+
+ lmFragments = new HashMap<String, ArrayList<Tree>>();
+
+ fragmentLMFile = parsedArgs.get("lm");
+ BUILD_DEPTH = Integer.parseInt(parsedArgs.get("build-depth"));
+ MAX_DEPTH = Integer.parseInt(parsedArgs.get("max-depth"));
+ MIN_LEX_DEPTH = Integer.parseInt(parsedArgs.get("min-lex-depth"));
+
+ /* Read in the language model fragments */
+ try {
+ Collection<Tree> trees = PennTreebankReader.readTrees(fragmentLMFile);
+ for (Tree fragment : trees) {
+ addLMFragment(fragment);
+
+ // System.err.println(String.format("Read fragment: %s",
+ // lmFragments.get(lmFragments.size()-1)));
+ }
+ } catch (IOException e) {
+ throw new RuntimeException(String.format("* WARNING: couldn't read fragment LM file '%s'",
+ fragmentLMFile), e);
+ }
+ LOG.info("FragmentLMFF: Read {} LM fragments from '{}'", numFragments, fragmentLMFile);
+ }
+
+ /**
+ * Add the provided fragment to the language model, subject to some filtering.
+ *
+ * @param fragment a {@link org.apache.joshua.decoder.ff.fragmentlm.Tree} fragment
+ */
+ public void addLMFragment(Tree fragment) {
+ if (lmFragments == null)
+ return;
+
+ int fragmentDepth = fragment.getDepth();
+
+ if (MAX_DEPTH != 0 && fragmentDepth > MAX_DEPTH) {
+ LOG.warn("Skipping fragment {} (depth {} > {})", fragment, fragmentDepth, MAX_DEPTH);
+ return;
+ }
+
+ if (MIN_LEX_DEPTH > 1 && fragment.isLexicalized() && fragmentDepth < MIN_LEX_DEPTH) {
+ LOG.warn("Skipping fragment {} (lex depth {} < {})", fragment, fragmentDepth, MIN_LEX_DEPTH);
+ return;
+ }
+
+ if (lmFragments.get(fragment.getRule()) == null) {
+ lmFragments.put(fragment.getRule(), new ArrayList<Tree>());
+ }
+ lmFragments.get(fragment.getRule()).add(fragment);
+ numFragments++;
+ }
+
+ /**
+ * This function computes the features that fire when the current rule is applied. The features
+ * that fire are any LM fragments that match the fragment associated with the current rule. LM
+ * fragments may recurse over the tail nodes, following 1-best backpointers until the fragment
+ * either matches or fails.
+ *
+ * @param rule {@link org.apache.joshua.decoder.ff.tm.Rule} to be utilized within computation
+ * @param tailNodes {@link java.util.List} of {@link org.apache.joshua.decoder.hypergraph.HGNode} tail nodes
+ * @param i todo
+ * @param j todo
+ * @param sourcePath information about a path taken through the source {@link org.apache.joshua.lattice.Lattice}
+ * @param sentence {@link org.apache.joshua.lattice.Lattice} input
+ * @param acc {@link org.apache.joshua.decoder.ff.FeatureFunction.Accumulator} object permitting generalization of feature computation
+ * @return the new dynamic programming state (null for stateless features)
+ */
+ @Override
+ public DPState compute(Rule rule, List<HGNode> tailNodes, int i, int j, SourcePath sourcePath,
+ Sentence sentence, Accumulator acc) {
+
+ /*
+ * Get the fragment associated with the target side of this rule.
+ *
+ * This could be done more efficiently. For example, just build the tree fragment once and then
+ * pattern match against it. This would circumvent having to build the tree possibly once every
+ * time you try to apply a rule.
+ */
+ Tree baseTree = Tree.buildTree(rule, tailNodes, BUILD_DEPTH);
+
+ Stack<Tree> nodeStack = new Stack<Tree>();
+ nodeStack.add(baseTree);
+ while (!nodeStack.empty()) {
+ Tree tree = nodeStack.pop();
+ if (tree == null)
+ continue;
+
+ if (lmFragments.get(tree.getRule()) != null) {
+ for (Tree fragment : lmFragments.get(tree.getRule())) {
+// System.err.println(String.format("Does\n %s match\n %s??\n -> %s", fragment, tree,
+// match(fragment, tree)));
+
+ if (fragment.getLabel() == tree.getLabel() && match(fragment, tree)) {
+// System.err.println(String.format(" FIRING: matched %s against %s", fragment, tree));
+ acc.add(fragment.escapedString(), 1);
+ if (OPTS_DEPTH)
+ if (fragment.isLexicalized())
+ acc.add(String.format("FragmentFF_lexdepth%d", fragment.getDepth()), 1);
+ else
+ acc.add(String.format("FragmentFF_depth%d", fragment.getDepth()), 1);
+ }
+ }
+ }
+
+ // We also need to try matching rules against internal nodes of the fragment corresponding to
+ // this
+ // rule
+ if (tree.getChildren() != null)
+ for (Tree childNode : tree.getChildren()) {
+ if (!childNode.isBoundary())
+ nodeStack.add(childNode);
+ }
+ }
+
+ return new FragmentState(baseTree);
+ }
+
+ /**
+ * Matches the fragment against the (possibly partially-built) tree. Assumption
+ *
+ * @param fragment the language model fragment
+ * @param tree the tree to match against (expanded from the hypergraph)
+ * @return
+ */
+ private boolean match(Tree fragment, Tree tree) {
+ // System.err.println(String.format("MATCH(%s,%s)", fragment, tree));
+
+ /* Make sure the root labels match. */
+ if (fragment.getLabel() != tree.getLabel()) {
+ return false;
+ }
+
+ /* Same number of kids? */
+ List<Tree> fkids = fragment.getChildren();
+ if (fkids.size() > 0) {
+ List<Tree> tkids = tree.getChildren();
+ if (fkids.size() != tkids.size()) {
+ return false;
+ }
+
+ /* Do the kids match on all labels? */
+ for (int i = 0; i < fkids.size(); i++)
+ if (fkids.get(i).getLabel() != tkids.get(i).getLabel())
+ return false;
+
+ /* Recursive match. */
+ for (int i = 0; i < fkids.size(); i++) {
+ if (!match(fkids.get(i), tkids.get(i)))
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ @Override
+ public DPState computeFinal(HGNode tailNodes, int i, int j, SourcePath sourcePath, Sentence sentence,
+ Accumulator acc) {
+ // TODO Auto-generated method stub
+ return null;
+ }
+
+ @Override
+ public float estimateFutureCost(Rule rule, DPState state, Sentence sentence) {
+ // TODO Auto-generated method stub
+ return 0;
+ }
+
+ @Override
+ public float estimateCost(Rule rule, Sentence sentence) {
+ // TODO Auto-generated method stub
+ return 0;
+ }
+
+ public static void main(String[] args) {
+ /* Add an LM fragment, then create a dummy multi-level hypergraph to match the fragment against. */
+ // FragmentLMFF fragmentLMFF = new FragmentLMFF(new FeatureVector(), (StateComputer) null, "");
+ FragmentLMFF fragmentLMFF = new FragmentLMFF(new FeatureVector(),
+ new String[] {"-lm", "test/fragments.txt", "-map", "test/mapping.txt"}, null);
+
+ Tree fragment = Tree.fromString("(S NP (VP (VBD \"said\") SBAR) (. \".\"))");
+
+ Rule ruleS = new HieroFormatReader()
+ .parseLine("[S] ||| the man [VP,1] [.,2] ||| the man [VP,1] [.,2] ||| 0");
+ Rule ruleVP = new HieroFormatReader()
+ .parseLine("[VP] ||| said [SBAR,1] ||| said [SBAR,1] ||| 0");
+ Rule ruleSBAR = new HieroFormatReader()
+ .parseLine("[SBAR] ||| that he was done ||| that he was done ||| 0");
+ Rule rulePERIOD = new HieroFormatReader().parseLine("[.] ||| . ||| . ||| 0");
+
+ ruleS.setOwner(0);
+ ruleVP.setOwner(0);
+ ruleSBAR.setOwner(0);
+ rulePERIOD.setOwner(0);
+
+ HyperEdge edgeSBAR = new HyperEdge(ruleSBAR, 0.0f, 0.0f, null, (SourcePath) null);
+
+ HGNode nodeSBAR = new HGNode(3, 7, ruleSBAR.getLHS(), null, edgeSBAR, 0.0f);
+ ArrayList<HGNode> tailNodesVP = new ArrayList<HGNode>();
+ Collections.addAll(tailNodesVP, nodeSBAR);
+ HyperEdge edgeVP = new HyperEdge(ruleVP, 0.0f, 0.0f, tailNodesVP, (SourcePath) null);
+ HGNode nodeVP = new HGNode(2, 7, ruleVP.getLHS(), null, edgeVP, 0.0f);
+
+ HyperEdge edgePERIOD = new HyperEdge(rulePERIOD, 0.0f, 0.0f, null, (SourcePath) null);
+ HGNode nodePERIOD = new HGNode(7, 8, rulePERIOD.getLHS(), null, edgePERIOD, 0.0f);
+
+ ArrayList<HGNode> tailNodes = new ArrayList<HGNode>();
+ Collections.addAll(tailNodes, nodeVP, nodePERIOD);
+
+ Tree tree = Tree.buildTree(ruleS, tailNodes, 1);
+ boolean matched = fragmentLMFF.match(fragment, tree);
+ LOG.info("Does\n {} match\n {}??\n -> {}", fragment, tree, matched);
+ }
+
+ /**
+ * Maintains a state pointer used by KenLM to implement left-state minimization.
+ *
+ * @author Matt Post post@cs.jhu.edu
+ * @author Juri Ganitkevitch juri@cs.jhu.edu
+ */
+ public class FragmentState extends DPState {
+
+ private Tree tree = null;
+
+ public FragmentState(Tree tree) {
+ this.tree = tree;
+ }
+
+ /**
+ * Every tree is unique.
+ *
+ * Some savings could be had here if we grouped together items with the same string.
+ */
+ @Override
+ public int hashCode() {
+ return tree.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ return (other instanceof FragmentState && this == other);
+ }
+
+ @Override
+ public String toString() {
+ return String.format("[FragmentState %s]", tree);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/PennTreebankReader.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/PennTreebankReader.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/PennTreebankReader.java
new file mode 100644
index 0000000..1637b5f
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/PennTreebankReader.java
@@ -0,0 +1,135 @@
+/*
+ * 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.ff.fragmentlm;
+
+import java.util.*;
+import java.io.*;
+import java.nio.charset.Charset;
+import java.nio.charset.UnsupportedCharsetException;
+
+/**
+ * @author Dan Klein
+ */
+public class PennTreebankReader {
+
+ static class TreeCollection extends AbstractCollection<Tree> {
+
+ List<File> files;
+ Charset charset;
+
+ static class TreeIteratorIterator implements Iterator<Iterator<Tree>> {
+ Iterator<File> fileIterator;
+ Iterator<Tree> nextTreeIterator;
+ Charset charset;
+
+ public boolean hasNext() {
+ return nextTreeIterator != null;
+ }
+
+ public Iterator<Tree> next() {
+ Iterator<Tree> currentTreeIterator = nextTreeIterator;
+ advance();
+ return currentTreeIterator;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ private void advance() {
+ nextTreeIterator = null;
+ while (nextTreeIterator == null && fileIterator.hasNext()) {
+ File file = fileIterator.next();
+ // System.out.println(file);
+ try {
+ nextTreeIterator = new Trees.PennTreeReader(new BufferedReader(new InputStreamReader(
+ new FileInputStream(file), this.charset)));
+ } catch (FileNotFoundException e) {
+ } catch (UnsupportedCharsetException e) {
+ throw new Error("Unsupported charset in file " + file.getPath());
+ }
+ }
+ }
+
+ TreeIteratorIterator(List<File> files, Charset charset) {
+ this.fileIterator = files.iterator();
+ this.charset = charset;
+ advance();
+ }
+ }
+
+ public Iterator<Tree> iterator() {
+ return new ConcatenationIterator<Tree>(new TreeIteratorIterator(files, this.charset));
+ }
+
+ public int size() {
+ int size = 0;
+ Iterator<Tree> i = iterator();
+ while (i.hasNext()) {
+ size++;
+ i.next();
+ }
+ return size;
+ }
+
+ @SuppressWarnings("unused")
+ private List<File> getFilesUnder(String path, FileFilter fileFilter) {
+ File root = new File(path);
+ List<File> files = new ArrayList<File>();
+ addFilesUnder(root, files, fileFilter);
+ return files;
+ }
+
+ private void addFilesUnder(File root, List<File> files, FileFilter fileFilter) {
+ if (!fileFilter.accept(root))
+ return;
+ if (root.isFile()) {
+ files.add(root);
+ return;
+ }
+ if (root.isDirectory()) {
+ File[] children = root.listFiles();
+ for (int i = 0; i < children.length; i++) {
+ File child = children[i];
+ addFilesUnder(child, files, fileFilter);
+ }
+ }
+ }
+
+ public TreeCollection(String file) throws FileNotFoundException, IOException {
+ this.files = new ArrayList<File>();
+ this.files.add(new File(file));
+ this.charset = Charset.defaultCharset();
+ }
+ }
+
+ public static Collection<Tree> readTrees(String path) throws FileNotFoundException, IOException {
+ return new TreeCollection(path);
+ }
+
+ public static void main(String[] args) {
+/* Collection<Tree> trees = readTrees(args[0], Charset.defaultCharset());
+ for (Tree tree : trees) {
+ tree = (new Trees.StandardTreeNormalizer()).transformTree(tree);
+ System.out.println(Trees.PennTreeRenderer.render(tree));
+ }
+ */
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Tree.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Tree.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Tree.java
new file mode 100644
index 0000000..07c7ecd
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Tree.java
@@ -0,0 +1,779 @@
+/*
+ * 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.ff.fragmentlm;
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.io.StringReader;
+import java.util.*;
+
+import org.apache.joshua.corpus.Vocabulary;
+import org.apache.joshua.decoder.ff.fragmentlm.Trees.PennTreeReader;
+import org.apache.joshua.decoder.ff.tm.Rule;
+import org.apache.joshua.decoder.hypergraph.HGNode;
+import org.apache.joshua.decoder.hypergraph.HyperEdge;
+import org.apache.joshua.decoder.hypergraph.KBestExtractor.DerivationState;
+import org.apache.joshua.util.io.LineReader;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Represent phrase-structure trees, with each node consisting of a label and a list of children.
+ * Borrowed from the Berkeley Parser, and extended to allow the representation of tree fragments in
+ * addition to complete trees (the BP requires terminals to be immediately governed by a
+ * preterminal). To distinguish terminals from nonterminals in fragments, the former must be
+ * enclosed in double-quotes when read in.
+ *
+ * @author Dan Klein
+ * @author Matt Post post@cs.jhu.edu
+ */
+public class Tree implements Serializable {
+
+ private static final Logger LOG = LoggerFactory.getLogger(Tree.class);
+ private static final long serialVersionUID = 1L;
+
+ protected int label;
+
+ /* Marks a frontier node as a terminal (as opposed to a nonterminal). */
+ boolean isTerminal = false;
+
+ /*
+ * Marks the root and frontier nodes of a fragment. Useful for denoting fragment derivations in
+ * larger trees.
+ */
+ boolean isBoundary = false;
+
+ /* A list of the node's children. */
+ List<Tree> children;
+
+ /* The maximum distance from the root to any of the frontier nodes. */
+ int depth = -1;
+
+ /* The number of lexicalized items among the tree's frontier. */
+ private int numLexicalItems = -1;
+
+ /*
+ * This maps the flat right-hand sides of Joshua rules to the tree fragments they were derived
+ * from. It is used to lookup the fragment that language model fragments should be match against.
+ * For example, if the target (English) side of your rule is
+ *
+ * [NP,1] said [SBAR,2]
+ *
+ * we will retrieve the unflattened fragment
+ *
+ * (S NP (VP (VBD said) SBAR))
+ *
+ * which presumably was the fronter fragment used to derive the translation rule. With this in
+ * hand, we can iterate through our store of language model fragments to match them against this,
+ * following tail nodes if necessary.
+ */
+ public static HashMap<String, String> rulesToFragmentStrings = new HashMap<String, String>();
+
+ public Tree(String label, List<Tree> children) {
+ setLabel(label);
+ this.children = children;
+ }
+
+ public Tree(String label) {
+ setLabel(label);
+ this.children = Collections.emptyList();
+ }
+
+ public Tree(int label2, ArrayList<Tree> newChildren) {
+ this.label = label2;
+ this.children = newChildren;
+ }
+
+ public void setChildren(List<Tree> c) {
+ this.children = c;
+ }
+
+ public List<Tree> getChildren() {
+ return children;
+ }
+
+ public int getLabel() {
+ return label;
+ }
+
+ /**
+ * Computes the depth-one rule rooted at this node. If the node has no children, null is returned.
+ *
+ * @return string representation of the rule
+ */
+ public String getRule() {
+ if (isLeaf()) {
+ return null;
+ }
+ StringBuilder ruleString = new StringBuilder("(" + Vocabulary.word(getLabel()));
+ for (Tree child : getChildren()) {
+ ruleString.append(" ").append(Vocabulary.word(child.getLabel()));
+ }
+ return ruleString.toString();
+ }
+
+ /*
+ * Boundary nodes are used externally to mark merge points between different fragments. This is
+ * separate from the internal ( (substitution point) denotation.
+ */
+ public boolean isBoundary() {
+ return isBoundary;
+ }
+
+ public void setBoundary(boolean b) {
+ this.isBoundary = b;
+ }
+
+ public boolean isTerminal() {
+ return isTerminal;
+ }
+
+ public boolean isLeaf() {
+ return getChildren().isEmpty();
+ }
+
+ public boolean isPreTerminal() {
+ return getChildren().size() == 1 && getChildren().get(0).isLeaf();
+ }
+
+ public List<Tree> getNonterminalYield() {
+ List<Tree> yield = new ArrayList<Tree>();
+ appendNonterminalYield(this, yield);
+ return yield;
+ }
+
+ public List<Tree> getYield() {
+ List<Tree> yield = new ArrayList<Tree>();
+ appendYield(this, yield);
+ return yield;
+ }
+
+ public List<Tree> getTerminals() {
+ List<Tree> yield = new ArrayList<Tree>();
+ appendTerminals(this, yield);
+ return yield;
+ }
+
+ private static void appendTerminals(Tree tree, List<Tree> yield) {
+ if (tree.isLeaf()) {
+ yield.add(tree);
+ return;
+ }
+ for (Tree child : tree.getChildren()) {
+ appendTerminals(child, yield);
+ }
+ }
+
+ /**
+ * Clone the structure of the tree.
+ *
+ * @return a cloned tree
+ */
+ public Tree shallowClone() {
+ ArrayList<Tree> newChildren = new ArrayList<Tree>(children.size());
+ for (Tree child : children) {
+ newChildren.add(child.shallowClone());
+ }
+
+ Tree newTree = new Tree(label, newChildren);
+ newTree.setIsTerminal(isTerminal());
+ newTree.setBoundary(isBoundary());
+ return newTree;
+ }
+
+ private void setIsTerminal(boolean terminal) {
+ isTerminal = terminal;
+ }
+
+ private static void appendNonterminalYield(Tree tree, List<Tree> yield) {
+ if (tree.isLeaf() && !tree.isTerminal()) {
+ yield.add(tree);
+ return;
+ }
+ for (Tree child : tree.getChildren()) {
+ appendNonterminalYield(child, yield);
+ }
+ }
+
+ private static void appendYield(Tree tree, List<Tree> yield) {
+ if (tree.isLeaf()) {
+ yield.add(tree);
+ return;
+ }
+ for (Tree child : tree.getChildren()) {
+ appendYield(child, yield);
+ }
+ }
+
+ public List<Tree> getPreTerminalYield() {
+ List<Tree> yield = new ArrayList<Tree>();
+ appendPreTerminalYield(this, yield);
+ return yield;
+ }
+
+ private static void appendPreTerminalYield(Tree tree, List<Tree> yield) {
+ if (tree.isPreTerminal()) {
+ yield.add(tree);
+ return;
+ }
+ for (Tree child : tree.getChildren()) {
+ appendPreTerminalYield(child, yield);
+ }
+ }
+
+ /**
+ * A tree is lexicalized if it has terminal nodes among the leaves of its frontier. For normal
+ * trees this is always true since they bottom out in terminals, but for fragments, this may or
+ * may not be true.
+ *
+ * @return true if the tree is lexicalized
+ */
+ public boolean isLexicalized() {
+ if (this.numLexicalItems < 0) {
+ if (isTerminal())
+ this.numLexicalItems = 1;
+ else {
+ this.numLexicalItems = 0;
+ for (Tree child : children)
+ if (child.isLexicalized())
+ this.numLexicalItems += 1;
+ }
+ }
+
+ return (this.numLexicalItems > 0);
+ }
+
+ /**
+ * The depth of a tree is the maximum distance from the root to any of the frontier nodes.
+ *
+ * @return the tree depth
+ */
+ public int getDepth() {
+ if (this.depth >= 0)
+ return this.depth;
+
+ if (isLeaf()) {
+ this.depth = 0;
+ } else {
+ int maxDepth = 0;
+ for (Tree child : children) {
+ int depth = child.getDepth();
+ if (depth > maxDepth)
+ maxDepth = depth;
+ }
+ this.depth = maxDepth + 1;
+ }
+ return this.depth;
+ }
+
+ public List<Tree> getAtDepth(int depth) {
+ List<Tree> yield = new ArrayList<Tree>();
+ appendAtDepth(depth, this, yield);
+ return yield;
+ }
+
+ private static void appendAtDepth(int depth, Tree tree, List<Tree> yield) {
+ if (depth < 0)
+ return;
+ if (depth == 0) {
+ yield.add(tree);
+ return;
+ }
+ for (Tree child : tree.getChildren()) {
+ appendAtDepth(depth - 1, child, yield);
+ }
+ }
+
+ public void setLabel(String label) {
+ if (label.length() >= 3 && label.startsWith("\"") && label.endsWith("\"")) {
+ this.isTerminal = true;
+ label = label.substring(1, label.length() - 1);
+ }
+
+ this.label = Vocabulary.id(label);
+ }
+
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ toStringBuilder(sb);
+ return sb.toString();
+ }
+
+ /**
+ * Removes the quotes around terminals. Note that the resulting tree could not be read back
+ * in by this class, since unquoted leaves are interpreted as nonterminals.
+ *
+ * @return unquoted string
+ */
+ public String unquotedString() {
+ return toString().replaceAll("\"", "");
+ }
+
+ public String escapedString() {
+ return toString().replaceAll(" ", "_");
+ }
+
+ public void toStringBuilder(StringBuilder sb) {
+ if (!isLeaf())
+ sb.append('(');
+
+ if (isTerminal())
+ sb.append(String.format("\"%s\"", Vocabulary.word(getLabel())));
+ else
+ sb.append(Vocabulary.word(getLabel()));
+
+ if (!isLeaf()) {
+ for (Tree child : getChildren()) {
+ sb.append(' ');
+ child.toStringBuilder(sb);
+ }
+ sb.append(')');
+ }
+ }
+
+ /**
+ * Get the set of all subtrees inside the tree by returning a tree rooted at each node. These are
+ * <i>not</i> copies, but all share structure. The tree is regarded as a subtree of itself.
+ *
+ * @return the <code>Set</code> of all subtrees in the tree.
+ */
+ public Set<Tree> subTrees() {
+ return (Set<Tree>) subTrees(new HashSet<Tree>());
+ }
+
+ /**
+ * Get the list of all subtrees inside the tree by returning a tree rooted at each node. These are
+ * <i>not</i> copies, but all share structure. The tree is regarded as a subtree of itself.
+ *
+ * @return the <code>List</code> of all subtrees in the tree.
+ */
+ public List<Tree> subTreeList() {
+ return (List<Tree>) subTrees(new ArrayList<Tree>());
+ }
+
+ /**
+ * Add the set of all subtrees inside a tree (including the tree itself) to the given
+ * <code>Collection</code>.
+ *
+ * @param n A collection of nodes to which the subtrees will be added
+ * @return The collection parameter with the subtrees added
+ */
+ public Collection<Tree> subTrees(Collection<Tree> n) {
+ n.add(this);
+ List<Tree> kids = getChildren();
+ for (Tree kid : kids) {
+ kid.subTrees(n);
+ }
+ return n;
+ }
+
+ /**
+ * Returns an iterator over the nodes of the tree. This method implements the
+ * <code>iterator()</code> method required by the <code>Collections</code> interface. It does a
+ * preorder (children after node) traversal of the tree. (A possible extension to the class at
+ * some point would be to allow different traversal orderings via variant iterators.)
+ *
+ * @return An interator over the nodes of the tree
+ */
+ public TreeIterator iterator() {
+ return new TreeIterator();
+ }
+
+ private class TreeIterator implements Iterator<Tree> {
+
+ private List<Tree> treeStack;
+
+ private TreeIterator() {
+ treeStack = new ArrayList<Tree>();
+ treeStack.add(Tree.this);
+ }
+
+ public boolean hasNext() {
+ return (!treeStack.isEmpty());
+ }
+
+ public Tree next() {
+ int lastIndex = treeStack.size() - 1;
+ Tree tr = treeStack.remove(lastIndex);
+ List<Tree> kids = tr.getChildren();
+ // so that we can efficiently use one List, we reverse them
+ for (int i = kids.size() - 1; i >= 0; i--) {
+ treeStack.add(kids.get(i));
+ }
+ return tr;
+ }
+
+ /**
+ * Not supported
+ */
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ }
+
+ public boolean hasUnaryChain() {
+ return hasUnaryChainHelper(this, false);
+ }
+
+ private boolean hasUnaryChainHelper(Tree tree, boolean unaryAbove) {
+ boolean result = false;
+ if (tree.getChildren().size() == 1) {
+ if (unaryAbove)
+ return true;
+ else if (tree.getChildren().get(0).isPreTerminal())
+ return false;
+ else
+ return hasUnaryChainHelper(tree.getChildren().get(0), true);
+ } else {
+ for (Tree child : tree.getChildren()) {
+ if (!child.isPreTerminal())
+ result = result || hasUnaryChainHelper(child, false);
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Inserts the SOS (and EOS) symbols into a parse tree, attaching them as a left (right) sibling
+ * to the leftmost (rightmost) pre-terminal in the tree. This facilitates using trees as language
+ * models. The arguments have to be passed in to preserve Java generics, even though this is only
+ * ever used with String versions.
+ *
+ * @param sos presumably "<s>"
+ * @param eos presumably "</s>"
+ */
+ public void insertSentenceMarkers(String sos, String eos) {
+ insertSentenceMarker(sos, 0);
+ insertSentenceMarker(eos, -1);
+ }
+
+ public void insertSentenceMarkers() {
+ insertSentenceMarker("<s>", 0);
+ insertSentenceMarker("</s>", -1);
+ }
+
+ /**
+ *
+ * @param symbol the marker to insert
+ * @param pos the position at which to insert
+ */
+ private void insertSentenceMarker(String symbol, int pos) {
+
+ if (isLeaf() || isPreTerminal())
+ return;
+
+ List<Tree> children = getChildren();
+ int index = (pos == -1) ? children.size() - 1 : pos;
+ if (children.get(index).isPreTerminal()) {
+ if (pos == -1)
+ children.add(new Tree(symbol));
+ else
+ children.add(pos, new Tree(symbol));
+ } else {
+ children.get(index).insertSentenceMarker(symbol, pos);
+ }
+ }
+
+ /**
+ * This is a convenience function for producing a fragment from its string representation.
+ *
+ * @param ptbStr input string from which to produce a fragment
+ * @return the fragment
+ */
+ public static Tree fromString(String ptbStr) {
+ PennTreeReader reader = new PennTreeReader(new StringReader(ptbStr));
+ Tree fragment = reader.next();
+ return fragment;
+ }
+
+ public static Tree getFragmentFromYield(String yield) {
+ String fragmentString = rulesToFragmentStrings.get(yield);
+ if (fragmentString != null)
+ return fromString(fragmentString);
+
+ return null;
+ }
+
+ public static void readMapping(String fragmentMappingFile) {
+ /* Read in the rule / fragments mapping */
+ try {
+ LineReader reader = new LineReader(fragmentMappingFile);
+ for (String line : reader) {
+ String[] fields = line.split("\\s+\\|{3}\\s+");
+ if (fields.length != 2 || !fields[0].startsWith("(")) {
+ LOG.warn("malformed line {}: {}", reader.lineno(), line);
+ continue;
+ }
+
+ rulesToFragmentStrings.put(fields[1].trim(), fields[0].trim()); // buildFragment(fields[0]));
+ }
+ } catch (IOException e) {
+ throw new RuntimeException(String.format("* WARNING: couldn't read fragment mapping file '%s'",
+ fragmentMappingFile), e);
+ }
+ LOG.info("FragmentLMFF: Read {} mappings from '{}'", rulesToFragmentStrings.size(),
+ fragmentMappingFile);
+ }
+
+ /**
+ * Builds a tree from the kth-best derivation state. This is done by initializing the tree with
+ * the internal fragment corresponding to the rule; this will be the top of the tree. We then
+ * recursively visit the derivation state objects, following the route through the hypergraph
+ * defined by them.
+ *
+ * This function is like Tree#buildTree(DerivationState, int),
+ * but that one simply follows the best incoming hyperedge for each node.
+ *
+ * @param rule for which corresponding internal fragment can be used to initialize the tree
+ * @param derivationStates array of state objects
+ * @param maxDepth of route through the hypergraph
+ * @return the Tree
+ */
+ public static Tree buildTree(Rule rule, DerivationState[] derivationStates, int maxDepth) {
+ Tree tree = getFragmentFromYield(rule.getEnglishWords());
+
+ if (tree == null) {
+ return null;
+ }
+
+ tree = tree.shallowClone();
+
+ if (LOG.isDebugEnabled()) {
+ LOG.debug("buildTree({})", tree);
+ for (int i = 0; i < derivationStates.length; i++) {
+ LOG.debug(" -> {}: {}", i, derivationStates[i]);
+ }
+ }
+
+ List<Tree> frontier = tree.getNonterminalYield();
+
+ /* The English side of a rule is a sequence of integers. Nonnegative integers are word
+ * indices in the Vocabulary, while negative indices are used to nonterminals. These negative
+ * indices are a *permutation* of the source side nonterminals, which contain the actual
+ * nonterminal Vocabulary indices for the nonterminal names. Here, we convert this permutation
+ * to a nonnegative 0-based permutation and store it in tailIndices. This is used to index
+ * the incoming DerivationState items, which are ordered by the source side.
+ */
+ ArrayList<Integer> tailIndices = new ArrayList<Integer>();
+ int[] englishInts = rule.getEnglish();
+ for (int i = 0; i < englishInts.length; i++)
+ if (englishInts[i] < 0)
+ tailIndices.add(-(englishInts[i] + 1));
+
+ /*
+ * We now have the tree's yield. The substitution points on the yield should match the
+ * nonterminals of the heads of the derivation states. Since we don't know which of the tree's
+ * frontier items are terminals and which are nonterminals, we walk through the tail nodes,
+ * and then match the label of each against the frontier node labels until we have a match.
+ */
+ // System.err.println(String.format("WORDS: %s\nTREE: %s", rule.getEnglishWords(), tree));
+ for (int i = 0; i < derivationStates.length; i++) {
+
+ Tree frontierTree = frontier.get(tailIndices.get(i));
+ frontierTree.setBoundary(true);
+
+ HyperEdge nextEdge = derivationStates[i].edge;
+ if (nextEdge != null) {
+ DerivationState[] nextStates = null;
+ if (nextEdge.getTailNodes() != null && nextEdge.getTailNodes().size() > 0) {
+ nextStates = new DerivationState[nextEdge.getTailNodes().size()];
+ for (int j = 0; j < nextStates.length; j++)
+ nextStates[j] = derivationStates[i].getChildDerivationState(nextEdge, j);
+ }
+ Tree childTree = buildTree(nextEdge.getRule(), nextStates, maxDepth - 1);
+
+ /* This can be null if there is no entry for the rule in the map */
+ if (childTree != null)
+ frontierTree.children = childTree.children;
+ } else {
+ frontierTree.children = tree.children;
+ }
+ }
+
+ return tree;
+ }
+
+ /**
+ * <p>Builds a tree from the kth-best derivation state. This is done by initializing the tree with
+ * the internal fragment corresponding to the rule; this will be the top of the tree. We then
+ * recursively visit the derivation state objects, following the route through the hypergraph
+ * defined by them.</p>
+ *
+ * @param derivationState array of state objects
+ * @param maxDepth of route through the hypergraph
+ * @return the Tree
+ */
+ public static Tree buildTree(DerivationState derivationState, int maxDepth) {
+ Rule rule = derivationState.edge.getRule();
+
+ Tree tree = getFragmentFromYield(rule.getEnglishWords());
+
+ if (tree == null) {
+ return null;
+ }
+
+ tree = tree.shallowClone();
+
+ LOG.debug("buildTree({})", tree);
+
+ if (rule.getArity() > 0 && maxDepth > 0) {
+ List<Tree> frontier = tree.getNonterminalYield();
+
+ /* The English side of a rule is a sequence of integers. Nonnegative integers are word
+ * indices in the Vocabulary, while negative indices are used to nonterminals. These negative
+ * indices are a *permutation* of the source side nonterminals, which contain the actual
+ * nonterminal Vocabulary indices for the nonterminal names. Here, we convert this permutation
+ * to a nonnegative 0-based permutation and store it in tailIndices. This is used to index
+ * the incoming DerivationState items, which are ordered by the source side.
+ */
+ ArrayList<Integer> tailIndices = new ArrayList<Integer>();
+ int[] englishInts = rule.getEnglish();
+ for (int i = 0; i < englishInts.length; i++)
+ if (englishInts[i] < 0)
+ tailIndices.add(-(englishInts[i] + 1));
+
+ /*
+ * We now have the tree's yield. The substitution points on the yield should match the
+ * nonterminals of the heads of the derivation states. Since we don't know which of the tree's
+ * frontier items are terminals and which are nonterminals, we walk through the tail nodes,
+ * and then match the label of each against the frontier node labels until we have a match.
+ */
+ // System.err.println(String.format("WORDS: %s\nTREE: %s", rule.getEnglishWords(), tree));
+ for (int i = 0; i < rule.getArity(); i++) {
+
+ Tree frontierTree = frontier.get(tailIndices.get(i));
+ frontierTree.setBoundary(true);
+
+ DerivationState childState = derivationState.getChildDerivationState(derivationState.edge, i);
+ Tree childTree = buildTree(childState, maxDepth - 1);
+
+ /* This can be null if there is no entry for the rule in the map */
+ if (childTree != null)
+ frontierTree.children = childTree.children;
+ }
+ }
+
+ return tree;
+ }
+
+ /**
+ * Takes a rule and its tail pointers and recursively constructs a tree (up to maxDepth).
+ *
+ * This could be implemented by using the other buildTree() function and using the 1-best
+ * DerivationState.
+ *
+ * @param rule {@link org.apache.joshua.decoder.ff.tm.Rule} to be used whilst building the tree
+ * @param tailNodes {@link java.util.List} of {@link org.apache.joshua.decoder.hypergraph.HGNode}'s
+ * @param maxDepth to go in the tree
+ * @return shallow clone of the Tree object
+ */
+ public static Tree buildTree(Rule rule, List<HGNode> tailNodes, int maxDepth) {
+ Tree tree = getFragmentFromYield(rule.getEnglishWords());
+
+ if (tree == null) {
+ tree = new Tree(String.format("(%s %s)", Vocabulary.word(rule.getLHS()), rule.getEnglishWords()));
+ // System.err.println("COULDN'T FIND " + rule.getEnglishWords());
+ // System.err.println("RULE " + rule);
+ // for (Entry<String, Tree> pair: rulesToFragments.entrySet())
+ // System.err.println(" FOUND " + pair.getKey());
+
+// return null;
+ } else {
+ tree = tree.shallowClone();
+ }
+
+ if (tree != null && tailNodes != null && tailNodes.size() > 0 && maxDepth > 0) {
+ List<Tree> frontier = tree.getNonterminalYield();
+
+ ArrayList<Integer> tailIndices = new ArrayList<Integer>();
+ int[] englishInts = rule.getEnglish();
+ for (int i = 0; i < englishInts.length; i++)
+ if (englishInts[i] < 0)
+ tailIndices.add(-1 * englishInts[i] - 1);
+
+ /*
+ * We now have the tree's yield. The substitution points on the yield should match the
+ * nonterminals of the tail nodes. Since we don't know which of the tree's frontier items are
+ * terminals and which are nonterminals, we walk through the tail nodes, and then match the
+ * label of each against the frontier node labels until we have a match.
+ */
+ // System.err.println(String.format("WORDS: %s\nTREE: %s", rule.getEnglishWords(), tree));
+ for (int i = 0; i < tailNodes.size(); i++) {
+
+ // String lhs = tailNodes.get(i).getLHS().replaceAll("[\\[\\]]", "");
+ // System.err.println(String.format(" %d: %s", i, lhs));
+ try {
+ Tree frontierTree = frontier.get(tailIndices.get(i).intValue());
+ frontierTree.setBoundary(true);
+
+ HyperEdge edge = tailNodes.get(i).bestHyperedge;
+ if (edge != null) {
+ Tree childTree = buildTree(edge.getRule(), edge.getTailNodes(), maxDepth - 1);
+ /* This can be null if there is no entry for the rule in the map */
+ if (childTree != null)
+ frontierTree.children = childTree.children;
+ } else {
+ frontierTree.children = tree.children;
+ }
+ } catch (IndexOutOfBoundsException e) {
+ LOG.error("ERROR at index {}", i);
+ LOG.error("RULE: {} TREE: {}", rule.getEnglishWords(), tree);
+ LOG.error(" FRONTIER:");
+ for (Tree kid : frontier) {
+ LOG.error(" {}", kid);
+ }
+ throw new RuntimeException(String.format("ERROR at index %d", i), e);
+ }
+ }
+ }
+
+ return tree;
+ }
+
+ public static void main(String[] args) {
+ LineReader reader = new LineReader(System.in);
+
+ for (String line : reader) {
+ try {
+ Tree tree = Tree.fromString(line);
+ tree.insertSentenceMarkers();
+ System.out.println(tree);
+ } catch (Exception e) {
+ System.out.println("");
+ }
+ }
+
+ /*
+ * Tree fragment = Tree
+ * .fromString("(TOP (S (NP (DT the) (NN boy)) (VP (VBD ate) (NP (DT the) (NN food)))))");
+ * fragment.insertSentenceMarkers("<s>", "</s>");
+ *
+ * System.out.println(fragment);
+ *
+ * ArrayList<Tree> trees = new ArrayList<Tree>(); trees.add(Tree.fromString("(NN \"mat\")"));
+ * trees.add(Tree.fromString("(S (NP DT NN) VP)"));
+ * trees.add(Tree.fromString("(S (NP (DT \"the\") NN) VP)"));
+ * trees.add(Tree.fromString("(S (NP (DT the) NN) VP)"));
+ *
+ * for (Tree tree : trees) { System.out.println(String.format("TREE %s DEPTH %d LEX? %s", tree,
+ * tree.getDepth(), tree.isLexicalized())); }
+ */
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Trees.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Trees.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Trees.java
new file mode 100644
index 0000000..d06388c
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/fragmentlm/Trees.java
@@ -0,0 +1,270 @@
+/*
+ * 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.ff.fragmentlm;
+
+import java.io.IOException;
+import java.io.PushbackReader;
+import java.io.Reader;
+import java.io.StringReader;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+import org.apache.joshua.corpus.Vocabulary;
+/**
+ * Tools for displaying, reading, and modifying trees. Borrowed from the Berkeley Parser.
+ *
+ * @author Dan Klein
+ */
+public class Trees {
+
+ public static class PennTreeReader implements Iterator<Tree> {
+ public static String ROOT_LABEL = "ROOT";
+
+ PushbackReader in;
+ Tree nextTree;
+
+ public boolean hasNext() {
+ return (nextTree != null);
+ }
+
+ public Tree next() {
+ if (!hasNext())
+ throw new NoSuchElementException();
+ Tree tree = nextTree;
+ nextTree = readRootTree();
+ // System.out.println(nextTree);
+ return tree;
+ }
+
+ private Tree readRootTree() {
+ try {
+ readWhiteSpace();
+ if (!isLeftParen(peek()))
+ return null;
+ return readTree(true);
+ } catch (IOException e) {
+ throw new RuntimeException("Error reading tree.");
+ }
+ }
+
+ private Tree readTree(boolean isRoot) throws IOException {
+ if (!isLeftParen(peek())) {
+ return readLeaf();
+ } else {
+ readLeftParen();
+ String label = readLabel();
+ if (label.length() == 0 && isRoot)
+ label = ROOT_LABEL;
+ List<Tree> children = readChildren();
+ readRightParen();
+ return new Tree(label, children);
+ }
+ }
+
+ private String readLabel() throws IOException {
+ readWhiteSpace();
+ return readText();
+ }
+
+ private String readText() throws IOException {
+ StringBuilder sb = new StringBuilder();
+ int ch = in.read();
+ while (!isWhiteSpace(ch) && !isLeftParen(ch) && !isRightParen(ch)) {
+ sb.append((char) ch);
+ ch = in.read();
+ }
+ in.unread(ch);
+ // System.out.println("Read text: ["+sb+"]");
+ return sb.toString().intern();
+ }
+
+ private List<Tree> readChildren() throws IOException {
+ readWhiteSpace();
+ // if (!isLeftParen(peek()))
+ // return Collections.singletonList(readLeaf());
+ return readChildList();
+ }
+
+ private int peek() throws IOException {
+ int ch = in.read();
+ in.unread(ch);
+ return ch;
+ }
+
+ private Tree readLeaf() throws IOException {
+ String label = readText();
+ return new Tree(label);
+ }
+
+ private List<Tree> readChildList() throws IOException {
+ List<Tree> children = new ArrayList<Tree>();
+ readWhiteSpace();
+ while (!isRightParen(peek())) {
+ children.add(readTree(false));
+ readWhiteSpace();
+ }
+ return children;
+ }
+
+ private void readLeftParen() throws IOException {
+ // System.out.println("Read left.");
+ readWhiteSpace();
+ int ch = in.read();
+ if (!isLeftParen(ch))
+ throw new RuntimeException("Format error reading tree. (leftParen)");
+ }
+
+ private void readRightParen() throws IOException {
+ // System.out.println("Read right.");
+ readWhiteSpace();
+ int ch = in.read();
+
+ if (!isRightParen(ch)) {
+ System.out.println((char) ch);
+ throw new RuntimeException("Format error reading tree. (rightParen)");
+ }
+ }
+
+ private void readWhiteSpace() throws IOException {
+ int ch = in.read();
+ while (isWhiteSpace(ch)) {
+ ch = in.read();
+ }
+ in.unread(ch);
+ }
+
+ private boolean isWhiteSpace(int ch) {
+ return (ch == ' ' || ch == '\t' || ch == '\f' || ch == '\r' || ch == '\n');
+ }
+
+ private boolean isLeftParen(int ch) {
+ return ch == '(';
+ }
+
+ private boolean isRightParen(int ch) {
+ return ch == ')';
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ public PennTreeReader(Reader in) {
+ this.in = new PushbackReader((java.io.Reader) in);
+ nextTree = readRootTree();
+ // System.out.println(nextTree);
+ }
+ }
+
+ /**
+ * Renderer for pretty-printing trees according to the Penn Treebank indenting guidelines
+ * (mutliline). Adapted from code originally written by Dan Klein and modified by Chris Manning.
+ */
+ public static class PennTreeRenderer {
+
+ /**
+ * Print the tree as done in Penn Treebank merged files. The formatting should be exactly the
+ * same, but we don't print the trailing whitespace found in Penn Treebank trees. The basic
+ * deviation from a bracketed indented tree is to in general collapse the printing of adjacent
+ * preterminals onto one line of tags and words. Additional complexities are that conjunctions
+ * (tag CC) are not collapsed in this way, and that the unlabeled outer brackets are collapsed
+ * onto the same line as the next bracket down.
+ *
+ * @param tree you wish to render and print
+ * @return a rendered String representation of the tree
+ */
+ public static String render(Tree tree) {
+ StringBuilder sb = new StringBuilder();
+ renderTree(tree, 0, false, false, false, true, sb);
+ sb.append('\n');
+ return sb.toString();
+ }
+
+ /**
+ * Display a node, implementing Penn Treebank style layout
+ */
+ private static void renderTree(Tree tree, int indent, boolean parentLabelNull,
+ boolean firstSibling, boolean leftSiblingPreTerminal, boolean topLevel, StringBuilder sb) {
+ // the condition for staying on the same line in Penn Treebank
+ boolean suppressIndent = (parentLabelNull || (firstSibling && tree.isPreTerminal()) || (leftSiblingPreTerminal
+ && tree.isPreTerminal()));
+ if (suppressIndent) {
+ sb.append(' ');
+ } else {
+ if (!topLevel) {
+ sb.append('\n');
+ }
+ for (int i = 0; i < indent; i++) {
+ sb.append(" ");
+ }
+ }
+ if (tree.isLeaf() || tree.isPreTerminal()) {
+ renderFlat(tree, sb);
+ return;
+ }
+ sb.append('(');
+ sb.append(tree.getLabel());
+ renderChildren(tree.getChildren(), indent + 1, false, sb);
+ sb.append(')');
+ }
+
+ private static void renderFlat(Tree tree, StringBuilder sb) {
+ if (tree.isLeaf()) {
+ sb.append(Vocabulary.word(tree.getLabel()));
+ return;
+ }
+ sb.append('(');
+ sb.append(Vocabulary.word(tree.getLabel()));
+ sb.append(' ');
+ sb.append(Vocabulary.word(tree.getChildren().get(0).getLabel()));
+ sb.append(')');
+ }
+
+ private static void renderChildren(List<Tree> children, int indent,
+ boolean parentLabelNull, StringBuilder sb) {
+ boolean firstSibling = true;
+ boolean leftSibIsPreTerm = true; // counts as true at beginning
+ for (Tree child : children) {
+ renderTree(child, indent, parentLabelNull, firstSibling, leftSibIsPreTerm, false, sb);
+ leftSibIsPreTerm = child.isPreTerminal();
+ firstSibling = false;
+ }
+ }
+ }
+
+ public static void main(String[] args) {
+ String ptbTreeString = "((S (NP (DT the) (JJ quick) (JJ brown) (NN fox)) (VP (VBD jumped) (PP (IN over) (NP (DT the) (JJ lazy) (NN dog)))) (. .)))";
+
+ if (args.length > 0) {
+ String tree = "";
+ for (String str : args) {
+ tree += " " + str;
+ }
+ ptbTreeString = tree.substring(1);
+ }
+
+ PennTreeReader reader = new PennTreeReader(new StringReader(ptbTreeString));
+
+ Tree tree = reader.next();
+ System.out.println(PennTreeRenderer.render(tree));
+ System.out.println(tree);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-joshua/blob/e2734396/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/AbstractLM.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/AbstractLM.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/AbstractLM.java
new file mode 100644
index 0000000..e8225dc
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/AbstractLM.java
@@ -0,0 +1,122 @@
+/*
+ * 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.ff.lm;
+
+import org.apache.joshua.decoder.Support;
+import java.util.List;
+
+/**
+ * This class implements NGramLanguageModel by creating wrappers
+ * around the necessary functions to capture common errors. Most
+ * methods are declared final, in an attempt to limit what subclasses
+ * may be defined.
+ *
+ * @author Zhifei Li, zhifei.work@gmail.com
+ * @version $LastChangedDate: 2009-12-30 10:10:38 -0600 (Wed, 30 Dec 2009) $
+ */
+public abstract class AbstractLM extends DefaultNGramLanguageModel {
+
+ public AbstractLM(int symbolTable, int order) {
+ super(symbolTable, order);
+ }
+
+ @SuppressWarnings("null")
+ public final double sentenceLogProbability(
+ List<Integer> sentence, int order, int startIndex
+ ) {
+ //return super.sentenceLogProbability(sentence.stream().toArray(int[]::new) , order, startIndex);
+ return (Double) null;
+ }
+
+ public final float ngramLogProbability(int[] ngram) {
+ return super.ngramLogProbability(ngram);
+ }
+
+ public final float ngramLogProbability(int[] ngram, int order) {
+ if (ngram.length > order) {
+ throw new RuntimeException("ngram length is greather than the max order");
+ }
+ // if (ngram.length==1 && "we".equals(symbolTable.getWord(ngram[0]))) {
+ // System.err.println("Something weird is about to happen");
+ // }
+
+ int historySize = ngram.length - 1;
+ if (historySize >= order || historySize < 0) {
+ // BUG: use logger or exception. Don't zero default
+ throw new RuntimeException("Error: history size is " + historySize);
+ // return 0;
+ }
+ double probability = ngramLogProbability_helper(ngram, order);
+// if (probability < -JoshuaConfiguration.lm_ceiling_cost) {
+// probability = -JoshuaConfiguration.lm_ceiling_cost;
+// }
+ return (float) probability;
+ }
+
+ protected abstract float ngramLogProbability_helper(int[] ngram, int order);
+
+ @Deprecated
+ public final double logProbOfBackoffState(List<Integer> ngram, int order, int qtyAdditionalBackoffWeight) {
+ return logProbabilityOfBackoffState(
+ Support.subIntArray(ngram, 0, ngram.size()),
+ order, qtyAdditionalBackoffWeight);
+ }
+
+
+ public final double logProbabilityOfBackoffState(int[] ngram, int order, int qtyAdditionalBackoffWeight) {
+ if (ngram.length > order) {
+ throw new RuntimeException("ngram length is greather than the max order");
+ }
+ if (ngram[ngram.length-1] != LanguageModelFF.LM_INDEX) {
+ throw new RuntimeException("last wrd is not <bow>");
+ }
+ if (qtyAdditionalBackoffWeight > 0) {
+ return logProbabilityOfBackoffState_helper(
+ ngram, order, qtyAdditionalBackoffWeight);
+ } else {
+ return 0.0;
+ }
+ }
+
+
+ protected abstract double logProbabilityOfBackoffState_helper(
+ int[] ngram, int order, int qtyAdditionalBackoffWeight);
+
+
+ // BUG: We should have different classes based on the configuration in use
+ public int[] leftEquivalentState(int[] originalState, int order,
+ double[] cost
+ ) {
+// if (JoshuaConfiguration.use_left_equivalent_state)
+// throw new UnsupportedOperationException("getLeftEquivalentState is not overwritten by a concrete class");
+
+ return originalState;
+ }
+
+
+ // BUG: We should have different classes based on the configuration in use
+ public int[] rightEquivalentState(int[] originalState, int order) {
+// if ( !JoshuaConfiguration.use_right_equivalent_state
+// || originalState.length != this.ngramOrder-1) {
+ return originalState;
+// } else {
+// throw new UnsupportedOperationException("getRightEquivalentState is not overwritten by a concrete class");
+// }
+ }
+}
\ 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/ff/lm/ArpaFile.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/ArpaFile.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/ArpaFile.java
new file mode 100644
index 0000000..01d2f39
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/ArpaFile.java
@@ -0,0 +1,328 @@
+/*
+ * 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.ff.lm;
+
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Scanner;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
+import java.util.zip.GZIPInputStream;
+
+import org.apache.joshua.corpus.Vocabulary;
+import org.apache.joshua.util.Regex;
+import org.apache.joshua.util.io.LineReader;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Utility class for reading ARPA language model files.
+ *
+ * @author Lane Schwartz
+ */
+public class ArpaFile implements Iterable<ArpaNgram> {
+
+ private static final Logger LOG = LoggerFactory.getLogger(ArpaFile.class);
+
+ /** Regular expression representing a blank line. */
+ public static final Regex BLANK_LINE = new Regex("^\\s*$");
+
+ /**
+ * Regular expression representing a line
+ * starting a new section of n-grams in an ARPA language model file.
+ */
+ public static final Regex NGRAM_HEADER = new Regex("^\\\\\\d-grams:\\s*$");
+
+ /**
+ * Regular expression representing a line
+ * ending an ARPA language model file.
+ */
+ public static final Regex NGRAM_END = new Regex("^\\\\end\\\\s*$");
+
+ /** ARPA file for this object. */
+ private final File arpaFile;
+
+ /** The vocabulary associated with this object. */
+ private final Vocabulary vocab;
+
+ /**
+ * Constructs an object that represents an ARPA language model file.
+ *
+ * @param arpaFileName File name of an ARPA language model file
+ * @param vocab Symbol table to be used by this object
+ */
+ public ArpaFile(String arpaFileName, Vocabulary vocab) {
+ this.arpaFile = new File(arpaFileName);
+ this.vocab = vocab;
+ }
+
+ public ArpaFile(String arpaFileName) throws IOException {
+ this.arpaFile = new File(arpaFileName);
+ this.vocab = new Vocabulary();
+
+ // final Scanner scanner = new Scanner(arpaFile);
+
+ // // Eat initial header lines
+ // while (scanner.hasNextLine()) {
+ // String line = scanner.nextLine();
+ // logger.finest("Discarding line: " + line);
+ // if (NGRAM_HEADER.matches(line)) {
+ // break;
+ // }
+ // }
+
+ // int ngramOrder = 1;
+
+ LineReader grammarReader = new LineReader(arpaFileName);
+
+ try {
+ for (String line : grammarReader) {
+
+
+ // while (scanner.hasNext()) {
+ //
+ // String line = scanner.nextLine();
+
+ String[] parts = Regex.spaces.split(line);
+ if (parts.length > 1) {
+ String[] words = Regex.spaces.split(parts[1]);
+
+ for (String word : words) {
+ LOG.debug("Adding to vocab: {}", word);
+ Vocabulary.addAll(word);
+ }
+ } else {
+ LOG.info(line);
+ }
+
+ }
+ } finally {
+ grammarReader.close();
+ }
+
+ //
+ // boolean lineIsHeader = NGRAM_HEADER.matches(line);
+ //
+ // while (lineIsHeader || BLANK_LINE.matches(line)) {
+ //
+ // if (lineIsHeader) {
+ // ngramOrder++;
+ // }
+ //
+ // if (scanner.hasNext()) {
+ // line = scanner.nextLine().trim();
+ // lineIsHeader = NGRAM_HEADER.matches(line);
+ // } else {
+ // logger.severe("Ran out of lines!");
+ // return;
+ // }
+ // }
+
+
+ //
+ // // Add word to vocab
+ // if (logger.isLoggable(Level.FINE)) logger.fine("Adding word to vocab: " + parts[ngramOrder]);
+ // vocab.addTerminal(parts[ngramOrder]);
+ //
+ // // Add context words to vocab
+ // for (int i=1; i<ngramOrder; i++) {
+ // if (logger.isLoggable(Level.FINE)) logger.fine("Adding context word to vocab: " + parts[i]);
+ // vocab.addTerminal(parts[i]);
+ // }
+
+ // }
+
+ LOG.info("Done constructing ArpaFile");
+
+ }
+
+ /**
+ * Gets the {@link org.apache.joshua.corpus.Vocabulary}
+ * associated with this object.
+ *
+ * @return the symbol table associated with this object
+ */
+ public Vocabulary getVocab() {
+ return vocab;
+ }
+
+ /**
+ * Gets the total number of n-grams
+ * in this ARPA language model file.
+ *
+ * @return total number of n-grams
+ * in this ARPA language model file
+ */
+ @SuppressWarnings("unused")
+ public int size() {
+
+ LOG.debug("Counting n-grams in ARPA file");
+ int count=0;
+
+ for (ArpaNgram ngram : this) {
+ count++;
+ }
+ LOG.debug("Done counting n-grams in ARPA file");
+
+ return count;
+ }
+
+ public int getOrder() throws FileNotFoundException {
+
+ Pattern pattern = Pattern.compile("^ngram (\\d+)=\\d+$");
+ LOG.debug("Pattern is {}", pattern);
+ @SuppressWarnings("resource")
+ final Scanner scanner = new Scanner(arpaFile);
+
+ int order = 0;
+
+ // Eat initial header lines
+ while (scanner.hasNextLine()) {
+ String line = scanner.nextLine();
+
+ if (NGRAM_HEADER.matches(line)) {
+ break;
+ } else {
+ Matcher matcher = pattern.matcher(line);
+ if (matcher.matches()) {
+ LOG.debug("DOES match: '{}'", line);
+ order = Integer.valueOf(matcher.group(1));
+ } else {
+ LOG.debug("Doesn't match: '{}'", line);
+ }
+ }
+ }
+
+ return order;
+ }
+
+ /**
+ * Gets an iterator capable of iterating
+ * over all n-grams in the ARPA file.
+ *
+ * @return an iterator capable of iterating
+ * over all n-grams in the ARPA file
+ */
+ @SuppressWarnings("resource")
+ public Iterator<ArpaNgram> iterator() {
+
+ try {
+ final Scanner scanner;
+
+ if (arpaFile.getName().endsWith("gz")) {
+ InputStream in = new GZIPInputStream(
+ new FileInputStream(arpaFile));
+ scanner = new Scanner(in);
+ } else {
+ scanner = new Scanner(arpaFile);
+ }
+
+ // Eat initial header lines
+ while (scanner.hasNextLine()) {
+ String line = scanner.nextLine();
+ LOG.debug("Discarding line: {}", line);
+ if (NGRAM_HEADER.matches(line)) {
+ break;
+ }
+ }
+
+ return new Iterator<ArpaNgram>() {
+
+ String nextLine = null;
+ int ngramOrder = 1;
+ // int id = 0;
+
+ public boolean hasNext() {
+
+ if (scanner.hasNext()) {
+
+ String line = scanner.nextLine();
+
+ boolean lineIsHeader = NGRAM_HEADER.matches(line) || NGRAM_END.matches(line);
+
+ while (lineIsHeader || BLANK_LINE.matches(line)) {
+
+ if (lineIsHeader) {
+ ngramOrder++;
+ }
+
+ if (scanner.hasNext()) {
+ line = scanner.nextLine().trim();
+ lineIsHeader = NGRAM_HEADER.matches(line) || NGRAM_END.matches(line);
+ } else {
+ nextLine = null;
+ return false;
+ }
+ }
+
+ nextLine = line;
+ return true;
+
+ } else {
+ nextLine = null;
+ return false;
+ }
+
+ }
+
+ public ArpaNgram next() {
+ if (nextLine!=null) {
+
+ String[] parts = Regex.spaces.split(nextLine);
+
+ float value = Float.valueOf(parts[0]);
+
+ int word = Vocabulary.id(parts[ngramOrder]);
+
+ int[] context = new int[ngramOrder-1];
+ for (int i=1; i<ngramOrder; i++) {
+ context[i-1] = Vocabulary.id(parts[i]);
+ }
+
+ float backoff;
+ if (parts.length > ngramOrder+1) {
+ backoff = Float.valueOf(parts[parts.length-1]);
+ } else {
+ backoff = ArpaNgram.DEFAULT_BACKOFF;
+ }
+
+ nextLine = null;
+ return new ArpaNgram(word, context, value, backoff);
+
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ };
+ } catch (IOException e) {
+ LOG.error(e.getMessage(), e);
+ return null;
+ }
+ }
+}
\ 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/ff/lm/ArpaNgram.java
----------------------------------------------------------------------
diff --git a/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/ArpaNgram.java b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/ArpaNgram.java
new file mode 100644
index 0000000..d0077d1
--- /dev/null
+++ b/joshua-core/src/main/java/org/apache/joshua/decoder/ff/lm/ArpaNgram.java
@@ -0,0 +1,73 @@
+/*
+ * 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.ff.lm;
+
+/**
+ * Represents a single n-gram line
+ * from an ARPA language model file.
+ *
+ * @author Lane Schwartz
+ */
+public class ArpaNgram {
+
+
+ /** Indicates an invalid probability value. */
+ public static final float INVALID_VALUE = Float.NaN;
+
+ /** Default backoff value. */
+ public static final float DEFAULT_BACKOFF = 0.0f;
+
+ private final int word;
+ private final int[] context;
+ private final float value;
+ private final float backoff;
+ // private final int id;
+
+ public ArpaNgram(int word, int[] context, float value, float backoff) {
+ this.word = word;
+ this.context = context;
+ this.value = value;
+ this.backoff = backoff;
+ // this.id = id;
+ }
+
+ // public int getID() {
+ // return id;
+ // }
+
+ public int order() {
+ return context.length + 1;
+ }
+
+ public int getWord() {
+ return word;
+ }
+
+ public int[] getContext() {
+ return context;
+ }
+
+ public float getValue() {
+ return value;
+ }
+
+ public float getBackoff() {
+ return backoff;
+ }
+}
\ No newline at end of file