📄 alphaset.h

📁 Amis - A maximum entropy estimator 一个最大熵模型统计工具
💻 H
字号:
////////////////////////////////////////////////////////////////////////////  Copyright (c) 2000, Yusuke Miyao///  You may distribute under the terms of the Artistic License.//////  <id>$Id: AlphaSet.h,v 1.6 2003/05/16 13:03:46 yusuke Exp $</id>///  <collection>Maximum Entropy Estimator</collection>///  <name>AlphaSet.h</name>///  <overview>Implementation of a set of alpha products</overview>///  <desc>///  Implementation of a set of alpha products///  used by feature forest models.///  </desc>/////////////////////////////////////////////////////////////////////////#ifndef Amis_AlphaSet_h_#define Amis_AlphaSet_h_#include <amis/configure.h>#include <amis/Real.h>#include <map>#include <vector>//#include <queue>#include <iostream>AMIS_NAMESPACE_BEGIN	///////////////////////////////////////////////////////////////////////// <classdef>/// <name>AlphaValue</name>/// <overview>A simple implementation of AlphaSet</overview>/// <desc>/// Alpha value is stored./// Addition and product operations are defined./// </desc>/// <body>class AlphaValue {private:  Real data;public:  AlphaValue() : data() {}  /// Constructor;  Real getValue() const {    return data;  }  /// Get the alpha value  template < class FeatureFreq >  void reserve( FeatureFreq ) {    // do nothing  }  /// Reserve the space (do nothing)  void clear() {    data = 0.0;  }  /// Clear the value  template < class FeatureFreq >  void init( FeatureFreq, Real alpha ) {    data = alpha;  }  /// Initialize the value with alpha  void incProduct( AlphaValue arg1, AlphaValue arg2 ) {    data += arg1.data * arg2.data;  }  /// Increment the value by the product of arg1 and arg2  void product( AlphaValue arg1, AlphaValue arg2 ) {    data = arg1.data * arg2.data;  }  /// Set the value to the product of arg1 and arg2  AlphaValue& operator*=( AlphaValue x ) {    data *= x.data;    return *this;  }  /// Same as *=  AlphaValue& operator*=( Real x ) {    data *= x;    return *this;  }  /// Same as *=  template < class ID, class FeatureFreq >  void accumulate( const std::vector< AlphaValue >& map_list, const std::vector< ID >& index_list,                   FeatureFreq ) {    data = 0.0;    for ( typename std::vector< ID >::const_iterator index = index_list.begin();          index != index_list.end();          ++index ) {      data += map_list[ *index ].data;    }  }  /// Set the value to the summation of alphas corresponding to the members of index_list  AlphaValue& operator+=( AlphaValue x ) {    data += x.data;    return *this;  }  /// Same as +=  Real sumProduct() const {    return data;  }  /// Get the sum of the product (just return the value)  ////////////////////////////////////////////////////////////  template < class FeatureFreqArray, class FeatureFreq >  void incFeatureFreqArray( FeatureFreqArray& array, FeatureFreq freq ) const {    array.add( 0, data * freq );  }  /// Increment the feature frequency array};inline std::ostream& operator<<( std::ostream& os, AlphaValue x ) {  os << x.getValue();  return os;}/// Print the value/// </body>/// </classdef>///////////////////////////////////////////////////////////////////////// <classdef>/// <name>AlphaMap</name>/// <overview>A set of (freq, alpha)</overview>/// <desc>/// A set of alpha values classified by the feature count index./// Internally, this class is a "map"./// Addition and product operations are defined./// </desc>/// <body>template < class Feature >class AlphaMap {public:  typedef typename Feature::FeatureFreq FeatureFreq;  typedef typename std::map< FeatureFreq, Real >::iterator iterator;  typedef typename std::map< FeatureFreq, Real >::const_iterator const_iterator;protected:  iterator begin() {    return data.begin();  }  iterator end() {    return data.end();  }  const_iterator begin() const {    return data.begin();  }  const_iterator end() const {    return data.end();  }private:  std::map< FeatureFreq, Real > data;public:  AlphaMap() : data() {}  /// Constructor  void reserve( FeatureFreq ) {    // do nothing  }  /// Reserve the space to store the values (do nothing)  void clear() {    data.clear();  }  /// Clear the values  void init( FeatureFreq index, Real alpha ) {    data.clear();    data[ index ] = alpha;  }  /// Initialize the data with alpha  void incProduct( const AlphaMap& arg1, const AlphaMap& arg2 ) {    for ( const_iterator it1 = arg1.data.begin(); it1 != arg1.data.end(); ++it1 ) {      for ( const_iterator it2 = arg2.data.begin(); it2 != arg2.data.end(); ++it2 ) {        data[ it1->first + it2->first ] += it1->second * it2->second;      }    }  }  /// Increment the data by the products of arg1 and arg2  void product( const AlphaMap& arg1, const AlphaMap& arg2 ) {    data.clear();    incProduct( arg1, arg2 );  }  /// Set the data by the products of arg1 and arg2  AlphaMap& operator*=( const AlphaMap& x ) {    std::map< FeatureFreq, Real > new_map;    for ( const_iterator it1 = data.begin(); it1 != data.end(); ++it1 ) {      for ( const_iterator it2 = x.data.begin(); it2 != x.data.end(); ++it2 ) {	new_map[ it1->first + it2->first ] += it1->second * it2->second;      }    }    data.swap( new_map );    return *this;  }  /// Intuitively, same as *=.  Store the products to the place indexed by the sum of the indices of arguments  AlphaMap& operator*=( Real x ) {    for ( iterator it = data.begin(); it != data.end(); ++it ) {      it->second *= x;    }    return *this;  }  /// Intuitively, same as *=.  Multiply each element in the data by x.  template < class ID >  void accumulate( const std::vector< AlphaMap >& map_list, const std::vector< ID >& index_list,                   FeatureFreq ) {    data.clear();    for ( typename std::vector< ID >::const_iterator index = index_list.begin();          index != index_list.end();          ++index ) {      const AlphaMap& map = map_list[ *index ];      for ( const_iterator it = map.data.begin();            it != map.data.end();            ++it ) {        data[ it->first ] += it->second;      }    }  }  /// Set the data to the summation of alphas corresponding to the members of index_list  AlphaMap& operator+=( const AlphaMap& x ) {    for ( const_iterator it = x.data.begin(); it != x.data.end(); ++it ) {      data[ it->first ] += it->second;    }    return *this;  }  /// Add the values of x to the corresponding place of this  Real sumProduct() const {    Real sum = 0.0;    for ( const_iterator it = data.begin(); it != data.end(); ++it ) {      sum += it->second;    }    return sum;  }  /// Get the summation of all values  ////////////////////////////////////////////////////////////  template < class FeatureFreqArray >  void incFeatureFreqArray( FeatureFreqArray& array, FeatureFreq freq ) const {    for ( const_iterator it = data.begin(); it != data.end(); ++it ) {      array.add( it->first, it->second * freq );    }  }  /// Increment the feature frequency array by this data  ////////////////////////////////////////////////////////////  friend std::ostream& operator<<<>( std::ostream&, const AlphaMap< Feature >& );};template < class Feature >inline std::ostream& operator<<( std::ostream& os, const AlphaMap< Feature >& x ) {  for ( typename AlphaMap< Feature >::const_iterator it = x.begin(); it != x.end(); ++it ) {      os << '(' << it->first << ',' << it->second << ") ";  }  return os;}/// Print the values/// </body>/// </classdef>///////////////////////////////////////////////////////////////////////// <classdef>/// <name>AlphaQueue</name>/// <overview>A set of (freq, alpha)</overview>/// <desc>/// A set of alpha values classified by the feature count index./// Internally, this class is a vector of pairs (freq, alpha)./// Addition and product operations are defined./// </desc>/// <body>template < class Feature >class AlphaQueue {public:  typedef typename Feature::FeatureFreq FeatureFreq;protected:  struct AlphaElem {    FeatureFreq first;    Real second;  };public:  typedef typename std::vector< AlphaElem >::iterator iterator;  typedef typename std::vector< AlphaElem >::const_iterator const_iterator;protected:  iterator begin() {    return data.begin();  }  iterator end() {    return data.end();  }  const_iterator begin() const {    return data.begin();  }  const_iterator end() const {    return data.end();  }private:  std::vector< AlphaElem > data;  static std::vector< Real > index_vector;  /// Temporal storageprotected:  static void initIndexVector( FeatureFreq size ) {    index_vector.resize( size );    index_vector.assign( size, 0.0 );  }  /// Initialize the temporal storage  static void addIndexVector( FeatureFreq index, Real value ) {    index_vector[ index ] += value;  }  /// Add the value to the temporal storage  static Real indexVector( FeatureFreq index ) {    return index_vector[ index ];  }  /// Get the value of temporal storagepublic:  AlphaQueue() : data() {}  /// Constructorprotected:  void addElem( FeatureFreq index, Real value ) {    AMIS_PROF5( "addElem" );    data.push_back( AlphaElem() );    data.back().first = index;    data.back().second = value;  }  /// Add new element to the queuepublic:  void reserve( FeatureFreq ) {    // do nothing  }  /// Reserve the space (do nothing)  void clear() {    data.resize( 0 );  }  /// Clear the data  void init( FeatureFreq index, Real value ) {    data.resize( 1 );    data[ 0 ].first = index;    data[ 0 ].second = value;  }  /// Initialize the data with valuepublic:  void incProduct( const AlphaQueue& arg1, const AlphaQueue& arg2 ) {    AMIS_PROF4( "AlphaQueue::incProduct" );    FeatureFreq max_freq = arg1.data.back().first + arg2.data.back().first;    if ( ! data.empty() ) max_freq = std::max( data.back().first, max_freq );    ++max_freq;    initIndexVector( max_freq );    for ( const_iterator it = data.begin(); it != data.end(); ++it ) {      addIndexVector( it->first, it->second );    }    for ( const_iterator it1 = arg1.data.begin(); it1 != arg1.data.end(); ++it1 ) {      for ( const_iterator it2 = arg2.data.begin(); it2 != arg2.data.end(); ++it2 ) {        addIndexVector( it1->first + it2->first, it1->second * it2->second );      }    }    data.resize( 0 );    for ( int i = 0; i < max_freq; ++i ) {      AMIS_PROF4( "Copying in AlphaQueue::product" );      if ( indexVector( i ) != 0.0 ) {        addElem( i, indexVector( i ) );      }    }  }  /// Increment the data with the products of arg1 and arg2  void product( const AlphaQueue& arg1, const AlphaQueue& arg2 ) {    AMIS_PROF4( "AlphaQueue::product" );    FeatureFreq max_freq = arg1.data.back().first + arg2.data.back().first + 1;    initIndexVector( max_freq );    for ( const_iterator it1 = arg1.data.begin(); it1 != arg1.data.end(); ++it1 ) {      for ( const_iterator it2 = arg2.data.begin(); it2 != arg2.data.end(); ++it2 ) {        addIndexVector( it1->first + it2->first, it1->second * it2->second );      }    }    data.resize( 0 );    for ( int i = 0; i < max_freq; ++i ) {      AMIS_PROF4( "Copying in AlphaQueue::product" );      if ( indexVector( i ) != 0.0 ) {        addElem( i, indexVector( i ) );      }    }  }  /// Set the data with the products of arg1 and arg2  AlphaQueue& operator*=( const AlphaQueue& x ) {    AMIS_PROF4( "AlphaQueue::operator*=" );    product( *this, x );    return *this;  }  /// Intuitively, same as *=.  Just set the product of this and x  AlphaQueue& operator*=( Real x ) {    for ( iterator it = data.begin(); it != data.end(); ++it ) {      it->second *= x;    }    return *this;  }  /// Intuitively, same as *=.  Multiply each value by x.  template < class ID >  void accumulate( const std::vector< AlphaQueue >& queue_list, const std::vector< ID >& index_list,                   FeatureFreq max_freq ) {    AMIS_PROF4( "AlphaQueue::accumulate" );    ++max_freq;    initIndexVector( max_freq );    for ( typename std::vector< ID >::const_iterator index = index_list.begin();          index != index_list.end();          ++index ) {      const AlphaQueue& queue = queue_list[ *index ];      for ( const_iterator it = queue.data.begin(); it != queue.data.end(); ++it ) {        addIndexVector( it->first, it->second );      }    }    data.resize( 0 );    for ( int i = 0; i < max_freq; ++i ) {      AMIS_PROF4( "Copying in AlphaQueue::accumulate" );      if ( indexVector( i ) != 0.0 ) {        addElem( i, indexVector( i ) );      }    }  }  /// Set the data to the summation of alphas corresponding to the members of index_list  AlphaQueue& operator+=( const AlphaQueue& x ) {    AMIS_PROF4( "AlphaQueue::operator+=" );    FeatureFreq max_freq = Feature::MIN_FEATURE_FREQ;    if ( ! data.empty() ) max_freq = data.back().first;    if ( ! x.data.empty() ) max_freq = std::max( max_freq, x.data.back().first );    ++max_freq;    initIndexVector( max_freq );    for ( const_iterator it = data.begin(); it != data.end(); ++it ) {      addIndexVector( it->first, it->second );    }    for ( const_iterator it = x.data.begin(); it != x.data.end(); ++it ) {      addIndexVector( it->first, it->second );    }    data.resize( 0 );    for ( int i = 0; i < max_freq; ++i ) {      AMIS_PROF4( "Copying in AlphaQueue::operator+=" );      if ( indexVector( i ) != 0.0 ) {        addElem( i, indexVector( i ) );      }    }    return *this;  }  /// Add the values of x to the corresponding place of this  Real sumProduct() const {    Real sum = 0.0;    for ( const_iterator it = data.begin(); it != data.end(); ++it ) {      sum += it->second;    }    return sum;  }  /// Get the sum of values  ////////////////////////////////////////////////////////////  template < class FeatureFreqArray >  void incFeatureFreqArray( FeatureFreqArray& array, FeatureFreq freq ) const {    for ( const_iterator it = data.begin(); it != data.end(); ++it ) {      array.add( it->first, it->second * freq );    }  }  /// Increment feature frequency array by this  ////////////////////////////////////////////////////////////  friend std::ostream& operator<<<>( std::ostream&, const AlphaQueue< Feature >& );};template < class Feature >inline std::ostream& operator<<( std::ostream& os, const AlphaQueue< Feature >& x ) {  for ( typename AlphaQueue< Feature >::const_iterator it = x.begin(); it != x.end(); ++it ) {      os << '(' << it->first << ',' << it->second << ") ";  }  return os;}/// Print the values/// </body>/// </classdef>AMIS_NAMESPACE_END#endif // Amis_AlphaSet_h_// end of AlphaSet.h
⌨️ 快捷键说明

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