📄 eventtree.h

📁 Amis - A maximum entropy estimator 一个最大熵模型统计工具
💻 H
字号:
////////////////////////////////////////////////////////////////////////////  Copyright (c) 2000, Yusuke Miyao///  You may distribute under the terms of the Artistic License.//////  <id>$Id: EventTree.h,v 1.9 2003/05/16 13:03:46 yusuke Exp $</id>///  <collection>Maximum Entropy Estimator</collection>///  <name>EventTree.h</name>///  <overview>An event with tree structure</overview>/////////////////////////////////////////////////////////////////////////#ifndef Amis_EventTree_h_#define Amis_EventTree_h_#include <amis/configure.h>#include <amis/Event.h>#include <amis/FeatureList.h>#include <amis/objstream.h>#include <vector>AMIS_NAMESPACE_BEGINtypedef unsigned int EventTreeNodeID;///////////////////////////////////////////////////////////////////////// <classdef>/// <name>EventTreeNode</name>/// <overview>A node of an event tree</overview>/// <desc>/// A node in an event tree (conjunctive/disjunctive)./// if 'feature_list' is NULL, it is a disjunctive node./// </desc>/// <body>template < class Feature >class EventTreeNode {private:  FeatureList< Feature >* feature_list;  std::vector< EventTreeNodeID > daughter_list;  std::vector< EventTreeNodeID > mother_list;  public:  typedef typename FeatureList<Feature>::const_iterator const_iterator;    const_iterator begin() const {    return feature_list->begin();  }  const_iterator end() const {    return feature_list->end();  }  public:  EventTreeNode() {    feature_list = NULL;  }  EventTreeNode( const EventTreeNode< Feature >& n )    : daughter_list( n.daughter_list ), mother_list( n.mother_list ) {    if ( n.feature_list == NULL ) {      feature_list = NULL;    } else {      feature_list = new FeatureList< Feature >( *n.feature_list );    }  }  EventTreeNode< Feature >& operator=( const EventTreeNode< Feature >& n ) {    daughter_list = n.daughter_list;    mother_list = n.mother_list;    if ( feature_list != NULL ) delete feature_list;    if ( n.feature_list == NULL ) {      feature_list = NULL;    } else {      feature_list = new FeatureList< Feature >( *n.feature_list );    }    return (*this);  }  EventTreeNode( const std::vector< Feature >& fl, const std::vector< EventTreeNodeID >& dl )    : daughter_list( dl ), mother_list() {    // conjunctive node    feature_list = new FeatureList< Feature >( fl, 1 );  }  EventTreeNode( const std::vector< EventTreeNodeID >& dl )    : daughter_list( dl ), mother_list() {    // disjunctive node    feature_list = NULL;  }  ~EventTreeNode() {    if ( feature_list != NULL ) {      delete feature_list;    }  }public:  bool isDisjunctiveNode() const {    return feature_list == NULL;  }  const FeatureList< Feature >& featureList() const {    return *feature_list;  }  const std::vector< EventTreeNodeID >& daughterList() const {    return daughter_list;  }  const std::vector< EventTreeNodeID >& motherList() const {    return mother_list;  }  std::vector< EventTreeNodeID >& motherList() {    return mother_list;  }public:  void writeObject( objstream& os ) const {    if ( feature_list == NULL ) {      // Disjunctive node      os << false;    } else {      // Conjunctive node      os << true;      feature_list->writeObject( os );    }    os << static_cast< EventTreeNodeID >( daughter_list.size() );    for ( typename std::vector< EventTreeNodeID >::const_iterator it = daughter_list.begin();          it != daughter_list.end();          ++it ) {      os << *it;    }    os << static_cast< EventTreeNodeID >( mother_list.size() );    for ( typename std::vector< EventTreeNodeID >::const_iterator it = mother_list.begin();          it != mother_list.end();          ++it ) {      os << *it;    }  }  void readObject( objstream& is ) {    bool is_conj;    is >> is_conj;    if ( is_conj ) {      // Conjunctive node      if ( feature_list == NULL ) feature_list = new FeatureList< Feature >();      feature_list->readObject( is );    } else {      if ( feature_list != NULL ) delete feature_list;      feature_list = NULL;    }    EventTreeNodeID max, id;    is >> max;    daughter_list.resize( max );    for ( typename std::vector< EventTreeNodeID >::iterator it = daughter_list.begin();          it != daughter_list.end();          ++it ) {      is >> id;      *it = id;    }    is >> max;    mother_list.resize( max );    for ( typename std::vector< EventTreeNodeID >::iterator it = mother_list.begin();          it != mother_list.end();          ++it ) {      is >> id;      *it = id;    }  }};/// </body>/// </classdef>///////////////////////////////////////////////////////////////////////// <classdef>/// <name>EventTree</name>/// <overview>An event with tree structure</overview>/// <desc>/// An event (list of list of features) is described with packed tree structure/// (a feature forest)./// A forest is represented with a set of nodes, and relations from a node/// to daughters./// Since 'newEventTreeNode' is called with DaughterList (a relation from a node/// to daughters), a new ID is assigned after all daughters are registered./// This means that a node list is sorted in a bottom-up manner./// When you traverse a forest in a bottom-up manner, you should just /// scan the node list from the beginning to the end./// At the same time, the node list is stored in the order of "last visit",/// so the node list is 'topological-sort'ed./// When you traverse a forest in a top-down manner, you should just/// scan the node list from the end to the beginning./// </desc>/// <body>template < class Feature >class EventTree {public:  typedef Feature FeatureType;  typedef typename Feature::FeatureFreq FeatureFreq;  typedef typename std::vector< EventTreeNode< Feature > >::const_iterator const_iterator;  typedef typename std::vector< EventTreeNode< Feature > >::const_reverse_iterator const_reverse_iterator;private:#ifdef AMIS_JOINT_PROB  Real prob;#endif // AMIS_JOINT_PROB  EventFreq freq;  FeatureList< Feature > observed_feature_list;  std::vector< EventTreeNode< Feature > > node_list;public:  const_iterator begin() const {    return node_list.begin();  }  const_iterator end() const {    return node_list.end();  }  const_reverse_iterator rbegin() const {    return node_list.rbegin();  }  const_reverse_iterator rend() const {    return node_list.rend();  }public:  EventTree() {#ifdef AMIS_JOINT_PROB    prob = 1.0;#endif // AMIS_JOINT_PROB    freq = 0;  }  void swap( EventTree< Feature >& event ) {#ifdef AMIS_JOINT_PROB    ::swap( prob, event.prob );#endif // AMIS_JOINT_PROB    ::swap( freq, event.freq );    observed_feature_list.swap( event.observed_feature_list );    node_list.swap( event.node_list );  }  bool isValid() const {    return freq != 0;  }  const EventFreq eventFrequency() const {    return freq;  }  const FeatureListFreq frequency() const {    return freq;  }  Real eventProbability() const {#ifdef AMIS_JOINT_PROB    return prob;#else // AMIS_JOINT_PROB    return 1.0;#endif // AMIS_JOINT_PROB  }  void setEventProbability( Real p ) {#ifdef AMIS_JOINT_PROB    prob = p;#else // AMIS_JOINT_PROB    // do nothing#endif // AMIS_JOINT_PROB  }  ////////////////////////////////////////////////////////////  void addObservedEvent( EventFreq f, const std::vector< Feature >& fl ) {    if ( freq != 0 ) throw IllegalEventError( "Observed feature list is already added" );    freq = f;    observed_feature_list = FeatureList< Feature >( fl, 1 );  }  EventTreeNodeID newConjunctiveNode( const std::vector< Feature >& fl, const std::vector< EventTreeNodeID >& dl ) {    EventTreeNodeID new_id = node_list.size();    node_list.push_back( EventTreeNode< Feature >( fl, dl ) );    for ( typename std::vector< EventTreeNodeID >::const_iterator it = dl.begin();          it != dl.end();          ++it ) {      node_list[ *it ].motherList().push_back( new_id );    }    return new_id;  }  EventTreeNodeID newDisjunctiveNode( const std::vector< EventTreeNodeID >& dl ) {    EventTreeNodeID new_id = node_list.size();    node_list.push_back( EventTreeNode< Feature >( dl ) );    for ( typename std::vector< EventTreeNodeID >::const_iterator it = dl.begin();          it != dl.end();          ++it ) {      node_list[ *it ].motherList().push_back( new_id );    }    return new_id;  }  void clear() {#ifdef AMIS_JOINT_PROB    prob = 1.0;#endif // AMIS_JOINT_PROB    freq = 0;    node_list.resize( 0 );  }  const FeatureList< Feature >& observedEvent() const {    return observed_feature_list;  }  int numEventTreeNodes() const {    return node_list.size();  }  int numFeatureList() const {    // Since # feature lists is meaningless in this model,    // so return # tree nodes.    return numEventTreeNodes();  }  const EventTreeNode< Feature >& operator[]( EventTreeNodeID id ) const {    return node_list[ id ];  }  ////////////////////////////////////////////////////////////  FeatureFreq maxFeatureCount() const {    std::vector< FeatureFreq > max_count_list( numEventTreeNodes() );    typename std::vector< EventTreeNode< Feature > >::const_iterator node = begin();    typename std::vector< FeatureFreq >::iterator max_count = max_count_list.begin();    for ( ; node != end(); ++node, ++max_count ) {      if ( node->isDisjunctiveNode() ) {        // disjunctive node        FeatureFreq count = Feature::MIN_FEATURE_FREQ;        for ( typename std::vector< EventTreeNodeID >::const_iterator dtr = node->daughterList().begin();              dtr != node->daughterList().end();              ++dtr ) {          count = std::max( count, max_count_list[ *dtr ] );        }        *max_count = count;      } else {        // conjunctive node        FeatureFreq count = node->featureList().featureCount();        for ( typename std::vector< EventTreeNodeID >::const_iterator dtr = node->daughterList().begin();              dtr != node->daughterList().end();              ++dtr ) {          count += max_count_list[ *dtr ];        }        *max_count = count;      }    }    return max_count_list.back();  }  //////////////////////////////////////////////////////////////////////  void setEmpiricalExpectation( const ModelBase& model, std::vector< Real >& empirical_expectation,				bool EnableJointProb = false ) const {    AMIS_DEBUG_MESSAGE( 5, "Feature loop\n" );    const FeatureList< Feature >& fl = observedEvent();    Real freq = frequency();    if ( EnableJointProb ) freq *= eventProbability();    for ( typename FeatureList< Feature >::const_iterator feature = fl.begin();	  feature != fl.end();	  ++feature ) {      AMIS_DEBUG_MESSAGE( 5, "feature=" << feature->id() << '\n' );      empirical_expectation[ feature->id() ] += static_cast< Real >( feature->freq() * freq );    }  }  //////////////////////////////////////////////////////////////////////public:  void writeObject( objstream& os ) const {#ifdef AMIS_JOINT_PROB    os << prob;#endif // AMIS_JOINT_PROB    os << freq;    observed_feature_list.writeObject( os );    os << static_cast< EventTreeNodeID >( node_list.size() );    for ( typename std::vector< EventTreeNode< Feature > >::const_iterator it = node_list.begin();          it != node_list.end();          ++it ) {      it->writeObject( os );    }  }  void readObject( objstream& is ) {#ifdef AMIS_JOINT_PROB    is >> prob;#endif // AMIS_JOINT_PROB    is >> freq;    observed_feature_list.readObject( is );    EventTreeNodeID max;    is >> max;    node_list.resize( max );    for ( typename std::vector< EventTreeNode< Feature > >::iterator it = node_list.begin();          it != node_list.end();          ++it ) {      it->readObject( is );    }  }};/// </body>/// </classdef>AMIS_NAMESPACE_END#endif // EventTree_h_// end of EventTree.h
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -