moses_chart: speed up n-best list generation by deferring creation of

ChartTrellisPath objects until a detour is selected.  The output
should be unchanged except in the case of ties and rounding differences
in score calculations.

This doesn't make much difference at n = 100 but helps for larger lists:
example real times for decoding the first 100 sentences of the
new-test2008 tuning set with four threads:

  n            before       after
  1         4m32.955s   4m28.584s
  100       4m42.375s   4m36.311s
  1500     13m17.681s   4m34.807s

And with the 'distinct' option:

               before       after
  1         4m36.656s   4m32.883s
  100      11m04.236s   4m35.221s
  1500    129m21.593s   5m06.320s

14 files changed, 427 insertions, 394 deletions

diff --git a/moses/src/ChartManager.cpp b/moses/src/ChartManager.cpp
index a370858d7..7bcaf80af 100644
--- a/moses/src/ChartManager.cpp
+++ b/moses/src/ChartManager.cpp
@@ -23,9 +23,10 @@
 #include "ChartManager.h"
 #include "ChartCell.h"
 #include "ChartHypothesis.h"
+#include "ChartTrellisDetourQueue.h"
+#include "ChartTrellisNode.h"
 #include "ChartTrellisPath.h"
 #include "ChartTrellisPathList.h"
-#include "ChartTrellisPathCollection.h"
 #include "StaticData.h"
 #include "DecodeStep.h"
 
@@ -146,48 +147,78 @@ void ChartManager::CalcNBest(size_t count, ChartTrellisPathList &ret,bool onlyDi
   if (count == 0 || size == 0)
     return;
 
-  ChartTrellisPathCollection contenders;
-  set<Phrase> distinctHyps;
-
-  // add all pure paths
+  // Build a ChartTrellisPath for the 1-best path, if any.
   WordsRange range(0, size-1);
   const ChartCell &lastCell = m_hypoStackColl.Get(range);
   const ChartHypothesis *hypo = lastCell.GetBestHypothesis();
-
   if (hypo == NULL) {
     // no hypothesis
     return;
   }
+  boost::shared_ptr<ChartTrellisPath> basePath(new ChartTrellisPath(*hypo));
+
+  // Add it to the n-best list.
+  ret.Add(basePath);
+  if (count == 1) {
+    return;
+  }
+
+  // Record the output phrase if distinct translations are required.
+  set<Phrase> distinctHyps;
+  if (onlyDistinct) {
+    distinctHyps.insert(basePath->GetOutputPhrase());
+  }
+
+  // Set a limit on the number of detours to pop.  If the n-best list is
+  // restricted to distinct translations then this limit should be bigger
+  // than n.  The n-best factor determines how much bigger the limit should be.
+  const size_t nBestFactor = StaticData::Instance().GetNBestFactor();
+  size_t popLimit;
+  if (!onlyDistinct) {
+    popLimit = count-1;
+  } else if (nBestFactor == 0) {
+    // 0 = 'unlimited.'  This actually sets a large-ish limit in case too many
+    // translations are identical.
+    popLimit = count * 1000;
+  } else {
+    popLimit = count * nBestFactor;
+  }
 
-  ChartTrellisPath *purePath = new ChartTrellisPath(hypo);
-  contenders.Add(purePath);
+  // Create an empty priority queue of detour objects.  It is bounded to
+  // contain no more than popLimit items.
+  ChartTrellisDetourQueue contenders(popLimit);
 
-  // factor defines stopping point for distinct n-best list if too many candidates identical
-  size_t nBestFactor = StaticData::Instance().GetNBestFactor();
-  if (nBestFactor < 1) nBestFactor = 1000; // 0 = unlimited
+  // Create a ChartTrellisDetour for each single-point deviation from basePath
+  // and add them to the queue.
+  CreateDeviantPaths(basePath, contenders);
 
   // MAIN loop
-  for (size_t iteration = 0 ; (onlyDistinct ? distinctHyps.size() : ret.GetSize()) < count && contenders.GetSize() > 0 && (iteration < count * nBestFactor) ; iteration++) {
-    // get next best from list of contenders
-    ChartTrellisPath *path = contenders.pop();
-    assert(path);
-
-    // create deviations from current best
-    path->CreateDeviantPaths(contenders);
-
-    if(onlyDistinct) {
-      Phrase tgtPhrase = path->GetOutputPhrase();
-      if (distinctHyps.insert(tgtPhrase).second)
-        ret.Add(path);
-      else
-        delete path;
-
-      const size_t nBestFactor = StaticData::Instance().GetNBestFactor();
-      if (nBestFactor > 0)
-        contenders.Prune(count * nBestFactor);
+  for (size_t i = 0;
+       ret.GetSize() < count && !contenders.Empty() && i < popLimit;
+       ++i) {
+    // Get the best detour from the queue.
+    std::auto_ptr<const ChartTrellisDetour> detour(contenders.Pop());
+    assert(detour.get());
+
+    // Create a full base path from the chosen detour.
+    basePath.reset(new ChartTrellisPath(*detour));
+
+    // Generate new detours from this base path and add them to the queue of
+    // contenders.  The new detours deviate from the base path by a single
+    // replacement along the previous detour sub-path.
+    assert(basePath->GetDeviationPoint());
+    CreateDeviantPaths(basePath, *(basePath->GetDeviationPoint()), contenders);
+
+    // If the n-best list is allowed to contain duplicate translations (at the
+    // surface level) then add the new path unconditionally, otherwise check
+    // whether the translation has seen before.
+    if (!onlyDistinct) {
+      ret.Add(basePath);
     } else {
-      ret.Add(path);
-      contenders.Prune(count);
+      Phrase tgtPhrase = basePath->GetOutputPhrase();
+      if (distinctHyps.insert(tgtPhrase).second) {
+        ret.Add(basePath);
+      }
     }
   }
 }
@@ -251,5 +282,34 @@ void ChartManager::FindReachableHypotheses( const ChartHypothesis *hypo, std::ma
 	}
 }
 
-} // namespace
+void ChartManager::CreateDeviantPaths(
+    boost::shared_ptr<const ChartTrellisPath> basePath,
+    ChartTrellisDetourQueue &q)
+{
+  CreateDeviantPaths(basePath, basePath->GetFinalNode(), q);
+}
+
+void ChartManager::CreateDeviantPaths(
+    boost::shared_ptr<const ChartTrellisPath> basePath,
+    const ChartTrellisNode &substitutedNode,
+    ChartTrellisDetourQueue &queue)
+{
+  const ChartArcList *arcList = substitutedNode.GetHypothesis().GetArcList();
+  if (arcList) {
+    for (ChartArcList::const_iterator iter = arcList->begin();
+         iter != arcList->end(); ++iter) {
+      const ChartHypothesis &replacement = **iter;
+      queue.Push(new ChartTrellisDetour(basePath, substitutedNode,
+                                        replacement));
+    }
+  }
+  // recusively create deviant paths for child nodes
+  const ChartTrellisNode::NodeChildren &children = substitutedNode.GetChildren();
+  ChartTrellisNode::NodeChildren::const_iterator iter;
+  for (iter = children.begin(); iter != children.end(); ++iter) {
+    const ChartTrellisNode &child = **iter;
+    CreateDeviantPaths(basePath, child, queue);
+  }
+}
 
+} // namespace Moses
diff --git a/moses/src/ChartManager.h b/moses/src/ChartManager.h
index 6c380aa40..dbcd42b6c 100644
--- a/moses/src/ChartManager.h
+++ b/moses/src/ChartManager.h
@@ -27,20 +27,31 @@
 #include "ChartCellCollection.h"
 #include "InputType.h"
 #include "WordsRange.h"
-#include "ChartTrellisPathList.h"
 #include "SentenceStats.h"
 #include "TranslationSystem.h"
 #include "ChartRuleLookupManager.h"
 
+#include <boost/shared_ptr.hpp>
+
 namespace Moses
 {
 
 class ChartHypothesis;
+class ChartTrellisDetourQueue;
+class ChartTrellisNode;
+class ChartTrellisPath;
 class ChartTrellisPathList;
 
 class ChartManager
 {
 private:
+  static void CreateDeviantPaths(boost::shared_ptr<const ChartTrellisPath>,
+                                 ChartTrellisDetourQueue &);
+
+  static void CreateDeviantPaths(boost::shared_ptr<const ChartTrellisPath>,
+                                 const ChartTrellisNode &,
+                                 ChartTrellisDetourQueue &);
+
   InputType const& m_source; /**< source sentence to be translated */
   ChartCellCollection m_hypoStackColl;
   ChartTranslationOptionCollection m_transOptColl; /**< pre-computed list of translation options for the phrases in this sentence */
diff --git a/moses/src/ChartTrellisPathList.cpp b/moses/src/ChartTrellisDetour.cpp
index 1d76ab21a..550a44a2c 100644
--- a/moses/src/ChartTrellisPathList.cpp
+++ b/moses/src/ChartTrellisDetour.cpp
@@ -1,37 +1,42 @@
-// $Id$
-// vim:tabstop=2
 /***********************************************************************
- Moses - factored phrase-based language decoder
- Copyright (C) 2010 Hieu Hoang
-
+ Moses - statistical machine translation system
+ Copyright (C) 2006-2011 University of Edinburgh
+ 
  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
-
+ 
  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.
-
+ 
  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- ***********************************************************************/
+***********************************************************************/
 
-#include "ChartTrellisPathList.h"
-#include "ChartTrellisPath.h"
-#include "Util.h"
+#include "ChartTrellisDetour.h"
 
-using namespace std;
+#include "ChartHypothesis.h"
+#include "ChartTrellisNode.h"
+#include "ChartTrellisPath.h"
 
 namespace Moses
 {
-ChartTrellisPathList::~ChartTrellisPathList()
+
+ChartTrellisDetour::ChartTrellisDetour(
+    boost::shared_ptr<const ChartTrellisPath> basePath,
+    const ChartTrellisNode &substitutedNode,
+    const ChartHypothesis &replacementHypo)
+  : m_basePath(basePath)
+  , m_substitutedNode(substitutedNode)
+  , m_replacementHypo(replacementHypo)
 {
-  // clean up
-  RemoveAllInColl(m_collection);
+  float diff = replacementHypo.GetTotalScore()
+             - substitutedNode.GetHypothesis().GetTotalScore();
+  m_totalScore = basePath->GetTotalScore() + diff;
 }
 
-} // namespace
-
+}  // namespace Moses
diff --git a/moses/src/ChartTrellisDetour.h b/moses/src/ChartTrellisDetour.h
new file mode 100644
index 000000000..a3b07ad00
--- /dev/null
+++ b/moses/src/ChartTrellisDetour.h
@@ -0,0 +1,52 @@
+/***********************************************************************
+ Moses - statistical machine translation system
+ Copyright (C) 2006-2011 University of Edinburgh
+ 
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+ 
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ Lesser General Public License for more details.
+ 
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+***********************************************************************/
+
+#pragma once
+
+#include <boost/shared_ptr.hpp>
+
+namespace Moses
+{
+class ChartHypothesis;
+class ChartTrellisNode;
+class ChartTrellisPath;
+
+class ChartTrellisDetour
+{
+ public:
+  ChartTrellisDetour(boost::shared_ptr<const ChartTrellisPath>,
+                     const ChartTrellisNode &, const ChartHypothesis &);
+
+  const ChartTrellisPath &GetBasePath() const { return *m_basePath; }
+  const ChartTrellisNode &GetSubstitutedNode() const {
+    return m_substitutedNode;
+  }
+  const ChartHypothesis &GetReplacementHypo() const {
+    return m_replacementHypo;
+  }
+  float GetTotalScore() const { return m_totalScore; }
+
+ private:
+  boost::shared_ptr<const ChartTrellisPath> m_basePath;
+  const ChartTrellisNode &m_substitutedNode;
+  const ChartHypothesis &m_replacementHypo;
+  float m_totalScore;
+};
+
+}  // namespace Moses
diff --git a/moses/src/ChartTrellisDetourQueue.cpp b/moses/src/ChartTrellisDetourQueue.cpp
new file mode 100644
index 000000000..9b359ca43
--- /dev/null
+++ b/moses/src/ChartTrellisDetourQueue.cpp
@@ -0,0 +1,53 @@
+/***********************************************************************
+ Moses - statistical machine translation system
+ Copyright (C) 2006-2011 University of Edinburgh
+ 
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+ 
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ Lesser General Public License for more details.
+ 
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+***********************************************************************/
+
+#include "ChartTrellisDetourQueue.h"
+
+#include "Util.h"
+
+namespace Moses {
+
+ChartTrellisDetourQueue::~ChartTrellisDetourQueue() {
+  RemoveAllInColl(m_queue);
+}
+
+void ChartTrellisDetourQueue::Push(const ChartTrellisDetour *detour) {
+  if (m_capacity == 0 || m_queue.size() < m_capacity) {
+    m_queue.insert(detour);
+  } else if (detour->GetTotalScore() > (*m_queue.rbegin())->GetTotalScore()) {
+    // Remove the worst-scoring item from the queue and insert detour.
+    QueueType::iterator p = m_queue.end();
+    delete *--p;
+    m_queue.erase(p);
+    m_queue.insert(detour);
+  } else {
+    // The detour is unusable: the queue is full and detour has a worse (or
+    // equal) score than the worst-scoring item already held.
+    delete detour;
+  }
+}
+
+const ChartTrellisDetour *ChartTrellisDetourQueue::Pop() {
+  QueueType::iterator p = m_queue.begin();
+  const ChartTrellisDetour *top = *p;
+  m_queue.erase(p);
+  return top;
+}
+
+}  // namespace Moses
diff --git a/moses/src/ChartTrellisDetourQueue.h b/moses/src/ChartTrellisDetourQueue.h
new file mode 100644
index 000000000..f679708e4
--- /dev/null
+++ b/moses/src/ChartTrellisDetourQueue.h
@@ -0,0 +1,62 @@
+/***********************************************************************
+ Moses - statistical machine translation system
+ Copyright (C) 2006-2011 University of Edinburgh
+ 
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+ 
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ Lesser General Public License for more details.
+ 
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+***********************************************************************/
+
+#pragma once
+
+#include "ChartTrellisDetour.h"
+
+#include <set>
+
+namespace Moses {
+
+// A bounded priority queue of ChartTrellisDetour pointers.  The top item is
+// the best scoring detour.  The queue assumes ownership of pushed items and
+// relinquishes ownership when they are popped.  Any remaining items at the
+// time of the queue's destruction are deleted.
+class ChartTrellisDetourQueue {
+ public:
+  // Create empty queue with fixed capacity of c.  Capacity 0 means unbounded.
+  ChartTrellisDetourQueue(size_t c) : m_capacity(c) {}
+  ~ChartTrellisDetourQueue();
+
+  bool Empty() const { return m_queue.empty(); }
+
+  // Add the detour to the queue or delete it if the queue is full and the
+  // score is no better than the queue's worst score.
+  void Push(const ChartTrellisDetour *detour);
+
+  // Remove the best-scoring detour from the queue and return it.  The
+  // caller is responsible for deleting the object.
+  const ChartTrellisDetour *Pop();
+
+ private:
+  struct DetourOrderer {
+    bool operator()(const ChartTrellisDetour* a,
+                    const ChartTrellisDetour* b) const {
+      return (a->GetTotalScore() > b->GetTotalScore());
+    }
+  };
+
+  typedef std::multiset<const ChartTrellisDetour *, DetourOrderer> QueueType;
+
+  QueueType m_queue;
+  const size_t m_capacity;
+};
+
+}  // namespace Moses
diff --git a/moses/src/ChartTrellisNode.cpp b/moses/src/ChartTrellisNode.cpp
index eb65120a7..725886c68 100644
--- a/moses/src/ChartTrellisNode.cpp
+++ b/moses/src/ChartTrellisNode.cpp
@@ -20,81 +20,57 @@
  ***********************************************************************/
 
 #include "ChartTrellisNode.h"
+
 #include "ChartHypothesis.h"
-#include "DotChart.h"
-#include "ScoreComponentCollection.h"
+#include "ChartTrellisDetour.h"
+#include "ChartTrellisPath.h"
 #include "StaticData.h"
-
-using namespace std;
+#include "DotChart.h"
 
 namespace Moses
 {
 
-ChartTrellisNode::ChartTrellisNode(const ChartHypothesis *hypo)
-  :m_hypo(hypo)
+ChartTrellisNode::ChartTrellisNode(const ChartHypothesis &hypo)
+    : m_hypo(hypo)
 {
-  const std::vector<const ChartHypothesis*> &prevHypos = hypo->GetPrevHypos();
+  CreateChildren();
+}
 
-  m_edge.reserve(prevHypos.size());
-  for (size_t ind = 0; ind < prevHypos.size(); ++ind) {
-    const ChartHypothesis *prevHypo = prevHypos[ind];
-    ChartTrellisNode *child = new ChartTrellisNode(prevHypo);
-    m_edge.push_back(child);
+ChartTrellisNode::ChartTrellisNode(const ChartTrellisDetour &detour,
+                                   ChartTrellisNode *&deviationPoint)
+    : m_hypo((&detour.GetBasePath().GetFinalNode() == &detour.GetSubstitutedNode())
+             ? detour.GetReplacementHypo()
+             : detour.GetBasePath().GetFinalNode().GetHypothesis())
+{
+  if (&m_hypo == &detour.GetReplacementHypo()) {
+    deviationPoint = this;
+    CreateChildren();
+  } else {
+    CreateChildren(detour.GetBasePath().GetFinalNode(),
+                   detour.GetSubstitutedNode(), detour.GetReplacementHypo(),
+                   deviationPoint);
   }
-
-  assert(m_hypo);
 }
 
-ChartTrellisNode::ChartTrellisNode(const ChartTrellisNode &origNode
-                         , const ChartTrellisNode &soughtNode
-                         , const ChartHypothesis &replacementHypo
-                         , ScoreComponentCollection	&scoreChange
-                         , const ChartTrellisNode *&nodeChanged)
+ChartTrellisNode::ChartTrellisNode(const ChartTrellisNode &root,
+                                   const ChartTrellisNode &substitutedNode,
+                                   const ChartHypothesis &replacementHypo,
+                                   ChartTrellisNode *&deviationPoint)
+    : m_hypo((&root == &substitutedNode)
+             ? replacementHypo
+             : root.GetHypothesis())
 {
-  if (&origNode.GetHypothesis() == &soughtNode.GetHypothesis()) {
-    // this node should be replaced
-    m_hypo = &replacementHypo;
-    nodeChanged = this;
-
-    // scores
-    assert(scoreChange.GetWeightedScore() == 0); // should only be changing 1 node
-
-    scoreChange = replacementHypo.GetScoreBreakdown();
-    scoreChange.MinusEquals(origNode.GetHypothesis().GetScoreBreakdown());
-
-    float deltaScore = scoreChange.GetWeightedScore();
-    assert(deltaScore <= 0.005);
-
-    // follow prev hypos back to beginning
-    const std::vector<const ChartHypothesis*> &prevHypos = replacementHypo.GetPrevHypos();
-    vector<const ChartHypothesis*>::const_iterator iter;
-    assert(m_edge.empty());
-    m_edge.reserve(prevHypos.size());
-    for (iter = prevHypos.begin(); iter != prevHypos.end(); ++iter) {
-      const ChartHypothesis *prevHypo = *iter;
-      ChartTrellisNode *prevNode = new ChartTrellisNode(prevHypo);
-      m_edge.push_back(prevNode);
-    }
-
+  if (&root == &substitutedNode) {
+    deviationPoint = this;
+    CreateChildren();
   } else {
-    // not the node we're looking for. Copy as-is and continue finding node
-    m_hypo = &origNode.GetHypothesis();
-    NodeChildren::const_iterator iter;
-    assert(m_edge.empty());
-    m_edge.reserve(origNode.m_edge.size());
-    for (iter = origNode.m_edge.begin(); iter != origNode.m_edge.end(); ++iter) {
-      const ChartTrellisNode &prevNode = **iter;
-      ChartTrellisNode *newPrevNode = new ChartTrellisNode(prevNode, soughtNode, replacementHypo, scoreChange, nodeChanged);
-      m_edge.push_back(newPrevNode);
-    }
+    CreateChildren(root, substitutedNode, replacementHypo, deviationPoint);
   }
-
-  assert(m_hypo);
 }
 
 ChartTrellisNode::~ChartTrellisNode()
 {
-  RemoveAllInColl(m_edge);
+  RemoveAllInColl(m_children);
 }
 
 Phrase ChartTrellisNode::GetOutputPhrase() const
@@ -102,13 +78,13 @@ Phrase ChartTrellisNode::GetOutputPhrase() const
   // exactly like same fn in hypothesis, but use trellis nodes instead of prevHypos pointer
   Phrase ret(Output, ARRAY_SIZE_INCR);
 
-  const ChartTranslationOption &transOpt = m_hypo->GetTranslationOption();
-  
-  VERBOSE(3, "Trans Opt:" << transOpt.GetDottedRule() << ": " << m_hypo->GetCurrTargetPhrase().GetTargetLHS() << "->" << m_hypo->GetCurrTargetPhrase() << std::endl);
+  const ChartTranslationOption &transOpt = m_hypo.GetTranslationOption();
 
-  const Phrase &currTargetPhrase = m_hypo->GetCurrTargetPhrase();
+  VERBOSE(3, "Trans Opt:" << transOpt.GetDottedRule() << ": " << m_hypo.GetCurrTargetPhrase().GetTargetLHS() << "->" << m_hypo.GetCurrTargetPhrase() << std::endl);
+
+  const Phrase &currTargetPhrase = m_hypo.GetCurrTargetPhrase();
   const AlignmentInfo::NonTermIndexMap &nonTermIndexMap =
-    m_hypo->GetCurrTargetPhrase().GetAlignmentInfo().GetNonTermIndexMap();
+    m_hypo.GetCurrTargetPhrase().GetAlignmentInfo().GetNonTermIndexMap();
   for (size_t pos = 0; pos < currTargetPhrase.GetSize(); ++pos) {
     const Word &word = currTargetPhrase.GetWord(pos);
     if (word.IsNonTerminal()) {
@@ -125,17 +101,33 @@ Phrase ChartTrellisNode::GetOutputPhrase() const
   return ret;
 }
 
-std::ostream& operator<<(std::ostream &out, const ChartTrellisNode &node)
+void ChartTrellisNode::CreateChildren()
 {
-  out << "*   " << node.GetHypothesis() << endl;
-
-  ChartTrellisNode::NodeChildren::const_iterator iter;
-  for (iter = node.GetChildren().begin(); iter != node.GetChildren().end(); ++iter) {
-    out << **iter;
+  assert(m_children.empty());
+  const std::vector<const ChartHypothesis*> &prevHypos = m_hypo.GetPrevHypos();
+  m_children.reserve(prevHypos.size());
+  for (size_t ind = 0; ind < prevHypos.size(); ++ind) {
+    const ChartHypothesis *prevHypo = prevHypos[ind];
+    ChartTrellisNode *child = new ChartTrellisNode(*prevHypo);
+    m_children.push_back(child);
   }
-
-  return out;
 }
 
+void ChartTrellisNode::CreateChildren(const ChartTrellisNode &rootNode,
+                                      const ChartTrellisNode &substitutedNode,
+                                      const ChartHypothesis &replacementHypo,
+                                      ChartTrellisNode *&deviationPoint)
+{
+  assert(m_children.empty());
+  const NodeChildren &children = rootNode.GetChildren();
+  m_children.reserve(children.size());
+  for (size_t ind = 0; ind < children.size(); ++ind) {
+    const ChartTrellisNode *origChild = children[ind];
+    ChartTrellisNode *child = new ChartTrellisNode(*origChild, substitutedNode,
+                                                   replacementHypo,
+                                                   deviationPoint);
+    m_children.push_back(child);
+  }
 }
 
+}
diff --git a/moses/src/ChartTrellisNode.h b/moses/src/ChartTrellisNode.h
index e8d6b55ac..7b81ff4b2 100644
--- a/moses/src/ChartTrellisNode.h
+++ b/moses/src/ChartTrellisNode.h
@@ -28,39 +28,39 @@ namespace Moses
 {
 class ScoreComponentCollection;
 class ChartHypothesis;
+class ChartTrellisDetour;
 
 class ChartTrellisNode
 {
-  friend std::ostream& operator<<(std::ostream&, const ChartTrellisNode&);
-public:
+ public:
   typedef std::vector<ChartTrellisNode*> NodeChildren;
 
-protected:
-  const ChartHypothesis *m_hypo;
-  NodeChildren m_edge;
-
-public:
-  ChartTrellisNode(const ChartHypothesis *hypo);
-  ChartTrellisNode(const ChartTrellisNode &origNode
-              , const ChartTrellisNode &soughtNode
-              , const ChartHypothesis &replacementHypo
-              , ScoreComponentCollection	&scoreChange
-              , const ChartTrellisNode *&nodeChanged);
+  ChartTrellisNode(const ChartHypothesis &hypo);
+  ChartTrellisNode(const ChartTrellisDetour &, ChartTrellisNode *&);
+
   ~ChartTrellisNode();
 
-  const ChartHypothesis &GetHypothesis() const {
-    return *m_hypo;
-  }
+  const ChartHypothesis &GetHypothesis() const { return m_hypo; }
 
-  const NodeChildren &GetChildren() const {
-    return m_edge;
-  }
+  const NodeChildren &GetChildren() const { return m_children; }
 
-  const ChartTrellisNode &GetChild(size_t ind) const {
-    return *m_edge[ind];
-  }
+  const ChartTrellisNode &GetChild(size_t i) const { return *m_children[i]; }
 
   Phrase GetOutputPhrase() const;
+
+ private:
+  ChartTrellisNode(const ChartTrellisNode &);  // Not implemented
+  ChartTrellisNode& operator=(const ChartTrellisNode &);  // Not implemented
+
+  ChartTrellisNode(const ChartTrellisNode &, const ChartTrellisNode &,
+                   const ChartHypothesis &, ChartTrellisNode *&);
+
+  void CreateChildren();
+  void CreateChildren(const ChartTrellisNode &, const ChartTrellisNode &,
+                      const ChartHypothesis &, ChartTrellisNode *&);
+
+  const ChartHypothesis &m_hypo;
+  NodeChildren m_children;
 };
 
 }
diff --git a/moses/src/ChartTrellisPath.cpp b/moses/src/ChartTrellisPath.cpp
index fb73827a9..de8803da3 100644
--- a/moses/src/ChartTrellisPath.cpp
+++ b/moses/src/ChartTrellisPath.cpp
@@ -20,40 +20,33 @@
  ***********************************************************************/
 
 #include "ChartTrellisPath.h"
-#include "ChartHypothesis.h"
-#include "ChartTrellisPathCollection.h"
-#include "StaticData.h"
-#include "Word.h"
 
-using namespace std;
+#include "ChartHypothesis.h"
+#include "ChartTrellisDetour.h"
+#include "ChartTrellisDetourQueue.h"
+#include "ChartTrellisNode.h"
 
 namespace Moses
 {
 
-ChartTrellisPath::ChartTrellisPath(const ChartHypothesis *hypo)
-  :m_finalNode(new ChartTrellisNode(hypo))
-  ,m_scoreBreakdown(hypo->GetScoreBreakdown())
-  ,m_totalScore(hypo->GetTotalScore())
-  ,m_prevNodeChanged(NULL)
-  ,m_prevPath(NULL)
+ChartTrellisPath::ChartTrellisPath(const ChartHypothesis &hypo)
+    : m_finalNode(new ChartTrellisNode(hypo))
+    , m_deviationPoint(NULL)
+    , m_scoreBreakdown(hypo.GetScoreBreakdown())
+    , m_totalScore(hypo.GetTotalScore())
 {
 }
 
-ChartTrellisPath::ChartTrellisPath(const ChartTrellisPath &origPath
-                         , const ChartTrellisNode &soughtNode
-                         , const ChartHypothesis &replacementHypo
-                         , ScoreComponentCollection	&scoreChange)
-  :m_scoreBreakdown(origPath.GetScoreBreakdown())
-  ,m_prevPath(&origPath)
+ChartTrellisPath::ChartTrellisPath(const ChartTrellisDetour &detour)
+   : m_finalNode(new ChartTrellisNode(detour, m_deviationPoint))
+   , m_scoreBreakdown(detour.GetBasePath().m_scoreBreakdown)
+   , m_totalScore(0)
 {
-  m_finalNode = new ChartTrellisNode(origPath.GetFinalNode()
-                                , soughtNode
-                                , replacementHypo
-                                , scoreChange
-                                , m_prevNodeChanged);
-
+  assert(m_deviationPoint);
+  ScoreComponentCollection scoreChange;
+  scoreChange = detour.GetReplacementHypo().GetScoreBreakdown();
+  scoreChange.MinusEquals(detour.GetSubstitutedNode().GetHypothesis().GetScoreBreakdown());
   m_scoreBreakdown.PlusEquals(scoreChange);
-
   m_totalScore = m_scoreBreakdown.GetWeightedScore();
 }
 
@@ -68,61 +61,4 @@ Phrase ChartTrellisPath::GetOutputPhrase() const
   return ret;
 }
 
-void ChartTrellisPath::CreateDeviantPaths(ChartTrellisPathCollection &pathColl, const ChartTrellisNode &soughtNode) const
-{
-  // copy this path but replace startHypo with its arc
-  const ChartArcList *arcList = soughtNode.GetHypothesis().GetArcList();
-
-  if (arcList) {
-    ChartArcList::const_iterator iterChartArcList;
-    for (iterChartArcList = arcList->begin(); iterChartArcList != arcList->end(); ++iterChartArcList) {
-      ScoreComponentCollection	scoreChange;
-
-      const ChartHypothesis &replacementHypo = **iterChartArcList;
-      ChartTrellisPath *newPath = new ChartTrellisPath(*this, soughtNode, replacementHypo, scoreChange);
-      pathColl.Add(newPath);
-    }
-  }
-
-  // recusively create deviant paths for child nodes
-  const ChartTrellisNode::NodeChildren &children = soughtNode.GetChildren();
-
-  ChartTrellisNode::NodeChildren::const_iterator iter;
-  for (iter = children.begin(); iter != children.end(); ++iter) {
-    const ChartTrellisNode &child = **iter;
-    CreateDeviantPaths(pathColl, child);
-  }
-}
-
-void ChartTrellisPath::CreateDeviantPaths(ChartTrellisPathCollection &pathColl) const
-{
-  if (m_prevNodeChanged == NULL) {
-    // initial enumeration from a pure hypo
-    CreateDeviantPaths(pathColl, GetFinalNode());
-  } else {
-    // don't change m_prevNodeChanged, just it's children
-    const ChartTrellisNode::NodeChildren &children = m_prevNodeChanged->GetChildren();
-
-    ChartTrellisNode::NodeChildren::const_iterator iter;
-    for (iter = children.begin(); iter != children.end(); ++iter) {
-      const ChartTrellisNode &child = **iter;
-      CreateDeviantPaths(pathColl, child);
-    }
-  }
-}
-
-std::ostream& operator<<(std::ostream &out, const ChartTrellisPath &path)
-{
-  out << &path << "  " << path.m_prevPath << "  " << path.GetOutputPhrase() << endl;
-
-  if (path.m_prevNodeChanged) {
-    out << "changed " << path.m_prevNodeChanged->GetHypothesis() << endl;
-  }
-
-  out << path.GetFinalNode() << endl;
-
-  return out;
-}
-
-};
-
+}  // namespace Moses
diff --git a/moses/src/ChartTrellisPath.h b/moses/src/ChartTrellisPath.h
index 69aadb15b..4dee018c3 100644
--- a/moses/src/ChartTrellisPath.h
+++ b/moses/src/ChartTrellisPath.h
@@ -21,60 +21,49 @@
 
 #pragma once
 
-#include "ChartTrellisNode.h"
 #include "ScoreComponentCollection.h"
 #include "Phrase.h"
 
+#include <boost/shared_ptr.hpp>
+
 namespace Moses
 {
+
 class ChartHypothesis;
-class ChartTrellisPathCollection;
+class ChartTrellisDetour;
+class ChartTrellisDetourQueue;
+class ChartTrellisNode;
 
 class ChartTrellisPath
 {
-  friend std::ostream& operator<<(std::ostream&, const ChartTrellisPath&);
-
-protected:
-  // recursively point backwards
-  ChartTrellisNode *m_finalNode;
-  const ChartTrellisNode *m_prevNodeChanged;
-  const ChartTrellisPath *m_prevPath;
+ public:
+  ChartTrellisPath(const ChartHypothesis &hypo);
+  ChartTrellisPath(const ChartTrellisDetour &detour);
 
-  ScoreComponentCollection	m_scoreBreakdown;
-  float m_totalScore;
-
-  // deviate by 1 hypo
-  ChartTrellisPath(const ChartTrellisPath &origPath
-              , const ChartTrellisNode &soughtNode
-              , const ChartHypothesis &replacementHypo
-              , ScoreComponentCollection	&scoreChange);
-
-  void CreateDeviantPaths(ChartTrellisPathCollection &pathColl, const ChartTrellisNode &soughtNode) const;
+  ~ChartTrellisPath();
 
-  const ChartTrellisNode &GetFinalNode() const {
-    assert (m_finalNode);
-    return *m_finalNode;
-  }
+  const ChartTrellisNode &GetFinalNode() const { return *m_finalNode; }
 
-public:
-  ChartTrellisPath(const ChartHypothesis *hypo);
-  ~ChartTrellisPath();
+  const ChartTrellisNode *GetDeviationPoint() const { return m_deviationPoint; }
 
   //! get score for this path throught trellis
-  inline float GetTotalScore() const {
-    return m_totalScore;
-  }
+  float GetTotalScore() const { return m_totalScore; }
 
   Phrase GetOutputPhrase() const;
 
   /** returns detailed component scores */
-  inline const ScoreComponentCollection &GetScoreBreakdown() const {
+  const ScoreComponentCollection &GetScoreBreakdown() const {
     return m_scoreBreakdown;
   }
 
-  void CreateDeviantPaths(ChartTrellisPathCollection &pathColl) const;
-};
-
+ private:
+  ChartTrellisPath(const ChartTrellisPath &);  // Not implemented
+  ChartTrellisPath &operator=(const ChartTrellisPath &);  // Not implemented
 
-}
+  ChartTrellisNode *m_finalNode;
+  ChartTrellisNode *m_deviationPoint;
+  ScoreComponentCollection m_scoreBreakdown;
+  float m_totalScore;
+};
 
+}  // namespace Moses
diff --git a/moses/src/ChartTrellisPathCollection.cpp b/moses/src/ChartTrellisPathCollection.cpp
deleted file mode 100644
index 5e05d1eaa..000000000
--- a/moses/src/ChartTrellisPathCollection.cpp
+++ /dev/null
@@ -1,65 +0,0 @@
-// $Id$
-// vim:tabstop=2
-/***********************************************************************
- Moses - factored phrase-based language decoder
- Copyright (C) 2010 Hieu Hoang
-
- This library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public
- License as published by the Free Software Foundation; either
- version 2.1 of the License, or (at your option) any later version.
-
- This library is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- License along with this library; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- ***********************************************************************/
-
-#include "ChartTrellisPathCollection.h"
-#include "ChartTrellisPath.h"
-
-namespace Moses
-{
-
-ChartTrellisPathCollection::~ChartTrellisPathCollection()
-{
-  // clean up
-  RemoveAllInColl(m_collection);
-}
-
-void ChartTrellisPathCollection::Add(ChartTrellisPath *path)
-{
-  m_collection.insert(path);
-}
-
-void ChartTrellisPathCollection::Prune(size_t newSize)
-{
-  size_t currSize = m_collection.size();
-
-  if (currSize <= newSize)
-    return; // don't need to prune
-
-  CollectionType::reverse_iterator iterRev;
-  for (iterRev = m_collection.rbegin() ; iterRev != m_collection.rend() ; ++iterRev) {
-    ChartTrellisPath *trellisPath = *iterRev;
-    delete trellisPath;
-
-    currSize--;
-    if (currSize == newSize)
-      break;
-  }
-
-  // delete path in m_collection
-  CollectionType::iterator iter = m_collection.begin();
-  for (size_t i = 0 ; i < newSize ; ++i)
-    iter++;
-
-  m_collection.erase(iter, m_collection.end());
-}
-
-}
-
diff --git a/moses/src/ChartTrellisPathCollection.h b/moses/src/ChartTrellisPathCollection.h
deleted file mode 100644
index b1fbd3a65..000000000
--- a/moses/src/ChartTrellisPathCollection.h
+++ /dev/null
@@ -1,65 +0,0 @@
-// $Id$
-// vim:tabstop=2
-/***********************************************************************
- Moses - factored phrase-based language decoder
- Copyright (C) 2010 Hieu Hoang
-
- This library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public
- License as published by the Free Software Foundation; either
- version 2.1 of the License, or (at your option) any later version.
-
- This library is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- License along with this library; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- ***********************************************************************/
-#pragma once
-
-#include <set>
-#include "ChartTrellisPath.h"
-
-namespace Moses
-{
-
-class ChartTrellisPath;
-
-struct CompareChartTrellisPathCollection {
-  bool operator()(const ChartTrellisPath* pathA, const ChartTrellisPath* pathB) const {
-    return (pathA->GetTotalScore() > pathB->GetTotalScore());
-  }
-};
-
-class ChartTrellisPathCollection
-{
-protected:
-  typedef std::multiset<ChartTrellisPath*, CompareChartTrellisPathCollection> CollectionType;
-  CollectionType m_collection;
-
-public:
-  ~ChartTrellisPathCollection();
-
-  size_t GetSize() const {
-    return m_collection.size();
-  }
-
-  void Add(ChartTrellisPath *path);
-  void Prune(size_t newSize);
-
-  ChartTrellisPath *pop() {
-    ChartTrellisPath *top = *m_collection.begin();
-
-    // Detach
-    m_collection.erase(m_collection.begin());
-    return top;
-  }
-
-};
-
-
-}
-
diff --git a/moses/src/ChartTrellisPathList.h b/moses/src/ChartTrellisPathList.h
index 4f7076366..5b811d621 100644
--- a/moses/src/ChartTrellisPathList.h
+++ b/moses/src/ChartTrellisPathList.h
@@ -21,6 +21,8 @@
 
 #pragma once
 
+#include <boost/shared_ptr.hpp>
+
 #include <vector>
 
 namespace Moses
@@ -30,7 +32,7 @@ class ChartTrellisPath;
 class ChartTrellisPathList
 {
 protected:
-  typedef std::vector<const ChartTrellisPath*> CollType;
+  typedef std::vector<boost::shared_ptr<const ChartTrellisPath> > CollType;
   CollType m_collection;
 
 public:
@@ -54,14 +56,14 @@ public:
     m_collection.clear();
   }
 
-  virtual ~ChartTrellisPathList();
+  virtual ~ChartTrellisPathList() {}
 
   std::size_t GetSize() const {
     return m_collection.size();
   }
 
   //! add a new entry into collection
-  void Add(ChartTrellisPath *trellisPath) {
+  void Add(boost::shared_ptr<const ChartTrellisPath> trellisPath) {
     m_collection.push_back(trellisPath);
   }
 };
diff --git a/moses/src/Makefile.am b/moses/src/Makefile.am
index 32fe1cb4b..ecbe11925 100644
--- a/moses/src/Makefile.am
+++ b/moses/src/Makefile.am
@@ -20,9 +20,10 @@ libmoses_la_HEADERS = \
         ChartTranslationOption.h \
 	ChartTranslationOptionCollection.h \
         ChartTranslationOptionList.h \
+	ChartTrellisDetour.h \
+	ChartTrellisDetourQueue.h \
 	ChartTrellisNode.h \
 	ChartTrellisPath.h \
-	ChartTrellisPathCollection.h \
 	ChartTrellisPathList.h \
         ConfusionNet.h \
         DecodeFeature.h \
@@ -179,10 +180,10 @@ libmoses_la_SOURCES = \
         ChartTranslationOption.cpp \
 	ChartTranslationOptionCollection.cpp \
         ChartTranslationOptionList.cpp \
+	ChartTrellisDetour.cpp \
+	ChartTrellisDetourQueue.cpp \
 	ChartTrellisNode.cpp \
 	ChartTrellisPath.cpp \
-	ChartTrellisPathCollection.cpp \
-	ChartTrellisPathList.cpp \
         ConfusionNet.cpp \
         DecodeFeature.cpp \
         DecodeGraph.cpp \