mosesdecoder/mert/Hypergraph.cpp

/***********************************************************************
Moses - factored phrase-based language decoder
Copyright (C) 2014- 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 <iostream>
#include <set>

#include <boost/lexical_cast.hpp>

#include "util/double-conversion/double-conversion.h"
#include "util/string_piece.hh"
#include "util/tokenize_piece.hh"

#include "Hypergraph.h"

using namespace std;
static const string kBOS = "<s>";
static const string kEOS = "</s>";

namespace MosesTuning
{

StringPiece NextLine(util::FilePiece& from)
{
  StringPiece line;
  while ((line = from.ReadLine()).starts_with("#"));
  return line;
}

Vocab::Vocab() :  eos_( FindOrAdd(kEOS)), bos_(FindOrAdd(kBOS))
{
}

const Vocab::Entry &Vocab::FindOrAdd(const StringPiece &str)
{
#if BOOST_VERSION >= 104200
  Map::const_iterator i= map_.find(str, Hash(), Equals());
#else
  std::string copied_str(str.data(), str.size());
  Map::const_iterator i = map_.find(copied_str.c_str());
#endif
  if (i != map_.end()) return *i;
  char *copied = static_cast<char*>(piece_backing_.Allocate(str.size() + 1));
  memcpy(copied, str.data(), str.size());
  copied[str.size()] = 0;
  return *map_.insert(Entry(copied, map_.size())).first;
}

double_conversion::StringToDoubleConverter converter(double_conversion::StringToDoubleConverter::NO_FLAGS, NAN, NAN, "inf", "nan");


/**
 * Reads an incoming edge. Returns edge and source words covered.
**/
static pair<Edge*,size_t> ReadEdge(util::FilePiece &from, Graph &graph)
{
  Edge* edge = graph.NewEdge();
  StringPiece line = from.ReadLine(); //Don't allow comments within edge lists
  util::TokenIter<util::MultiCharacter> pipes(line, util::MultiCharacter(" ||| "));
  //Target
  for (util::TokenIter<util::SingleCharacter, true> i(*pipes, util::SingleCharacter(' ')); i; ++i) {
    StringPiece got = *i;
    if ('[' == *got.data() && ']' == got.data()[got.size() - 1]) {
      // non-terminal
      char *end_ptr;
      unsigned long int child = std::strtoul(got.data() + 1, &end_ptr, 10);
      UTIL_THROW_IF(end_ptr != got.data() + got.size() - 1, HypergraphException, "Bad non-terminal" << got);
      UTIL_THROW_IF(child >= graph.VertexSize(), HypergraphException, "Reference to vertex " << child << " but we only have " << graph.VertexSize() << " vertices.  Is the file in bottom-up format?");
      edge->AddWord(NULL);
      edge->AddChild(child);
    } else {
      const Vocab::Entry &found = graph.MutableVocab().FindOrAdd(got);
      edge->AddWord(&found);
    }
  }

  //Features
  ++pipes;
  for (util::TokenIter<util::SingleCharacter, true> i(*pipes, util::SingleCharacter(' ')); i; ++i) {
    StringPiece fv = *i;
    if (!fv.size()) break;
    size_t equals = fv.find_last_of("=");
    UTIL_THROW_IF(equals == fv.npos, HypergraphException, "Failed to parse feature '" << fv << "'");
    StringPiece name = fv.substr(0,equals);
    StringPiece value = fv.substr(equals+1);
    int processed;
    float score = converter.StringToFloat(value.data(), value.length(), &processed);
    UTIL_THROW_IF(isnan(score), HypergraphException, "Failed to parse weight '" << value << "'");
    edge->AddFeature(name,score);
  }
  //Covered words
  ++pipes;
  size_t sourceCovered = boost::lexical_cast<size_t>(*pipes);
  return pair<Edge*,size_t>(edge,sourceCovered);
}

void Graph::Prune(Graph* pNewGraph, const SparseVector& weights, size_t minEdgeCount) const
{

  Graph& newGraph = *pNewGraph;
  //TODO: Optimise case where no pruning required

  //For debug


  /*
  map<const Edge*, string> edgeIds;
  for (size_t i = 0; i < edges_.Size(); ++i) {
    stringstream str;
    size_t childId = 0;
    for (size_t j = 0; j < edges_[i].Words().size(); ++j) {
      if (edges_[i].Words()[j]) {
        str << edges_[i].Words()[j]->first << " ";
      } else {
        str << "[" << edges_[i].Children()[childId++] << "] ";
      }
    }
    edgeIds[&(edges_[i])] = str.str();
  }
  */

  //end For debug

  map<const Edge*, FeatureStatsType> edgeBackwardScores;
  map<const Edge*, size_t> edgeHeads;
  vector<FeatureStatsType> vertexBackwardScores(vertices_.Size(), kMinScore);
  vector<vector<const Edge*> > outgoing(vertices_.Size());

  //Compute backward scores
  for (size_t vi = 0; vi < vertices_.Size(); ++vi) {
    // cerr << "Vertex " << vi << endl;
    const Vertex& vertex = vertices_[vi];
    const vector<const Edge*>& incoming = vertex.GetIncoming();
    if (!incoming.size()) {
      vertexBackwardScores[vi] = 0;
    } else {
      for (size_t ei = 0; ei < incoming.size(); ++ei) {
        //cerr << "Edge " << edgeIds[incoming[ei]] << endl;
        edgeHeads[incoming[ei]]= vi;
        FeatureStatsType incomingScore = incoming[ei]->GetScore(weights);
        for (size_t i = 0; i < incoming[ei]->Children().size(); ++i) {
          //cerr << "\tChild " << incoming[ei]->Children()[i] << endl;
          size_t childId = incoming[ei]->Children()[i];
          UTIL_THROW_IF(vertexBackwardScores[childId] == kMinScore,
                        HypergraphException, "Graph was not topologically sorted. curr=" << vi << " prev=" << childId);
          outgoing[childId].push_back(incoming[ei]);
          incomingScore += vertexBackwardScores[childId];
        }
        edgeBackwardScores[incoming[ei]]= incomingScore;
        //cerr << "Backward score: " << incomingScore << endl;
        if (incomingScore > vertexBackwardScores[vi]) vertexBackwardScores[vi] = incomingScore;
      }
    }
  }

  //Compute forward scores
  vector<FeatureStatsType> vertexForwardScores(vertices_.Size(), kMinScore);
  map<const Edge*, FeatureStatsType> edgeForwardScores;
  for (size_t i = 1; i <= vertices_.Size(); ++i) {
    size_t vi = vertices_.Size() - i;
    //cerr << "Vertex " << vi << endl;
    if (!outgoing[vi].size()) {
      vertexForwardScores[vi] = 0;
    } else {
      for (size_t ei = 0; ei < outgoing[vi].size(); ++ei) {
        //cerr << "Edge " << edgeIds[outgoing[vi][ei]] << endl;
        FeatureStatsType outgoingScore = 0;
        //add score of head
        outgoingScore += vertexForwardScores[edgeHeads[outgoing[vi][ei]]];
        //cerr << "Forward score " << outgoingScore << endl;
        edgeForwardScores[outgoing[vi][ei]] = outgoingScore;
        //sum scores of siblings
        for (size_t i = 0; i < outgoing[vi][ei]->Children().size(); ++i) {
          size_t siblingId = outgoing[vi][ei]->Children()[i];
          if (siblingId != vi) {
            //cerr << "\tSibling " << siblingId << endl;
            outgoingScore += vertexBackwardScores[siblingId];
          }
        }
        outgoingScore += outgoing[vi][ei]->GetScore(weights);
        if (outgoingScore > vertexForwardScores[vi]) vertexForwardScores[vi] = outgoingScore;
        //cerr << "Vertex " << vi << " forward score " << outgoingScore << endl;
      }
    }
  }



  multimap<FeatureStatsType, const Edge*> edgeScores;
  for (size_t i = 0; i < edges_.Size(); ++i) {
    const Edge* edge = &(edges_[i]);
    if (edgeForwardScores.find(edge) == edgeForwardScores.end()) {
      //This edge has no children, so didn't get a forward score. Its forward score
      //is that of its head
      edgeForwardScores[edge] = vertexForwardScores[edgeHeads[edge]];
    }
    FeatureStatsType score = edgeForwardScores[edge] + edgeBackwardScores[edge];
    edgeScores.insert(pair<FeatureStatsType, const Edge*>(score,edge));
    //  cerr << edgeIds[edge] << " " << score << endl;
  }



  multimap<FeatureStatsType, const Edge*>::const_reverse_iterator ei = edgeScores.rbegin();
  size_t edgeCount = 1;
  while(edgeCount < minEdgeCount && ei != edgeScores.rend()) {
    ++ei;
    ++edgeCount;
  }
  multimap<FeatureStatsType, const Edge*>::const_iterator lowest = edgeScores.begin();
  if (ei != edgeScores.rend())  lowest = edgeScores.lower_bound(ei->first);

  //cerr << "Retained edges" << endl;
  set<size_t> retainedVertices;
  set<const Edge*> retainedEdges;
  for (; lowest != edgeScores.end(); ++lowest) {
    //cerr << lowest->first << " " << edgeIds[lowest->second] << endl;
    retainedEdges.insert(lowest->second);
    retainedVertices.insert(edgeHeads[lowest->second]);
    for (size_t i = 0; i < lowest->second->Children().size(); ++i) {
      retainedVertices.insert(lowest->second->Children()[i]);
    }
  }
  newGraph.SetCounts(retainedVertices.size(), retainedEdges.size());

  //cerr << "Retained vertices" << endl;
  map<size_t,size_t> oldIdToNew;
  size_t vi = 0;
  for (set<size_t>::const_iterator i = retainedVertices.begin(); i != retainedVertices.end(); ++i, ++vi) {
//   cerr << *i << " New: " << vi << endl;
    oldIdToNew[*i] = vi;
    Vertex* vertex = newGraph.NewVertex();
    vertex->SetSourceCovered(vertices_[*i].SourceCovered());
  }

  for (set<const Edge*>::const_iterator i = retainedEdges.begin(); i != retainedEdges.end(); ++i) {
    Edge* newEdge = newGraph.NewEdge();
    const Edge* oldEdge = *i;
    for (size_t j = 0; j < oldEdge->Words().size(); ++j) {
      newEdge->AddWord(oldEdge->Words()[j]);
    }
    for (size_t j = 0; j < oldEdge->Children().size(); ++j) {
      newEdge->AddChild(oldIdToNew[oldEdge->Children()[j]]);
    }
    newEdge->SetFeatures(oldEdge->Features());
    Vertex& newHead = newGraph.vertices_[oldIdToNew[edgeHeads[oldEdge]]];
    newHead.AddEdge(newEdge);
  }


  /*
  cerr << "New graph" << endl;
  for (size_t vi = 0; vi < newGraph.VertexSize(); ++vi) {
    cerr << "Vertex " << vi << endl;
    const vector<const Edge*> incoming = newGraph.GetVertex(vi).GetIncoming();
    for (size_t ei = 0; ei < incoming.size(); ++ei) {
      size_t childId = 0;
      for (size_t wi = 0; wi < incoming[ei]->Words().size(); ++wi) {
        const Vocab::Entry* word = incoming[ei]->Words()[wi];
        if (word) {
          cerr << word->first << " ";
        } else {
          cerr << "[" << incoming[ei]->Children()[childId++] << "] ";
        }
      }
      cerr << " Score: " << incoming[ei]->GetScore(weights) <<  endl;
    }
    cerr << endl;
  }

  */

}

/**
  * Read from "Kenneth's hypergraph" aka cdec target_graph format (with comments)
**/
void ReadGraph(util::FilePiece &from, Graph &graph)
{

  //First line should contain field names
  StringPiece line = from.ReadLine();
  UTIL_THROW_IF(line.compare("# target ||| features ||| source-covered") != 0, HypergraphException, "Incorrect format spec on first line: '" << line << "'");
  line = NextLine(from);

  //Then expect numbers of vertices
  util::TokenIter<util::SingleCharacter, false> i(line, util::SingleCharacter(' '));
  unsigned long int vertices = boost::lexical_cast<unsigned long int>(*i);
  ++i;
  unsigned long int edges = boost::lexical_cast<unsigned long int>(*i);
  graph.SetCounts(vertices, edges);
  //cerr << "vertices: " << vertices << "; edges: " << edges << endl;
  for (size_t i = 0; i < vertices; ++i) {
    line = NextLine(from);
    unsigned long int edge_count = boost::lexical_cast<unsigned long int>(line);
    Vertex* vertex = graph.NewVertex();
    for (unsigned long int e = 0; e < edge_count; ++e) {
      pair<Edge*,size_t> edge = ReadEdge(from, graph);
      vertex->AddEdge(edge.first);
      //Note: the file format attaches this to the edge, but it's really a property
      //of the vertex.
      if (!e) {
        vertex->SetSourceCovered(edge.second);
      }
    }
  }
}

};