proto/Source/ngram.cpp

Go to the documentation of this file.

// We use std::copy() here.
#include <algorithm>
// We use numeric_limits<> here.
#include <limits>

// Self header
#include "ngram.h"

namespace ace {


/* Static members initialization.
 */

bool NGram::_context_tracing_on = false;

// Const - independent on N.

const freq_counter_t NGram::_max_frequency = std::numeric_limits<freq_counter_t>::max() >> (sizeof(ngram_type_t)*constants::bits_per_char);

const ngram_type_t NGram::_overflow_flag_mask = static_cast<ngram_type_t>(1 << (sizeof(ngram_type_t)*constants::bits_per_char - 1));

const size_t NGram::_last_bit_index = sizeof(freq_counter_t) / sizeof(ngram_type_t) - 1;
// Type mask must omit most significant bit used for overflow flag.
const ngram_type_t NGram::_type_mask = ff<ngram_type_t>() >> 1;

// Non const statics - N-dependent.

ngram_type_t NGram::_full_ngram_type = 0;

std::vector<ngram_size_t> NGram::_members_count;

std::vector<size_t> NGram::_ngrams_memory_sizes;

NGram::_overflows_map_t NGram::_overflows;

ngram_type_t NGram::_types_count = 0;

void  NGram::_type(ngram_type_t ngram_type) {
    bool overflow = _overflow();
    _frequency_bits[_last_bit_index] = ngram_type;
    if ( overflow ) {
        _frequency_bits[_last_bit_index] |= _overflow_flag_mask;
    }
}

/*  Interface item implementation - for info see description in header file.
 */
void NGram::init(void) {
    // Context tracing on?
    _context_tracing_on = settings::context_tracing_on();
    // Num = 2 to power of N.
    _types_count = static_cast<ngram_type_t>(1 << n());
    // Initialize members count table.
    for ( ngram_type_t type = 0; type < _types_count; ++type ) {
        _members_count.push_back(static_cast<ngram_size_t>(bits_in(type)));
    }
    // Initialize full N-gram infos.
    _full_ngram_type = static_cast<ngram_type_t>(~(ff<ngram_type_t>() << n()));
    // Initialize members size_of table.
    for ( ngram_size_t degree = 0; degree <= n(); ++degree ) {
        _ngrams_memory_sizes.push_back(sizeof(NGram) + degree*sizeof(Member));
    }
    if ( _context_tracing_on ) {
        // Skip zero typed N-gram!
        for ( ngram_size_t degree = 1; degree <= n(); ++degree ) {
            // 
            _ngrams_memory_sizes[degree] += sizeof(context_t);
        }
    }
}

/*  Interface item implementation - for info see description in header file.
 */
NGram::NGram(const raw_ngram_t& raw_ngram, ngram_type_t ngram_type): _frequency(1) {
    // Store N-gram type within frequency.
    _type(ngram_type);
    // 
    unsigned s = 0, i = n(); // i gets decremented.
    for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem ) {
        // If i-th bit set, then store the member, otherwise do nothing.
        if ( ith_bit(ngram_type, --i) ) { // i must starts at n()-1 and decrements every loop!
#ifdef _DEPENDENCY_MODE
            new (get(s)) Member( i_mem->second->lemma(), i_mem->second->tag(), i_mem->first, (i_mem->first == 0) ? dependency::head : i_mem->second->dependency() );
#else
            new (get(s)) Member((*i_mem)->lemma(), (*i_mem)->tag());
#endif
            ++s; // !
        }
    }
    if ( _context_tracing_on ) {
        new (context()) context_t();
    }
}

/*  Interface item implementation - for info see description in header file.
 */
NGram::NGram(const NGram& source): _frequency(source._frequency) {
    // Note, that we can't init _frequency by calling frequency() getter, because we would lost
    // type info.
    // 
    std::copy(source.begin(), source.end(), this->begin());
    // Don't copy context, make new (the only copy of context should be within pooled instance).
    if ( _context_tracing_on ) {
        new (context()) context_t();
    }
}

/*  Interface item implementation - for info see description in header file.
 */
NGram::NGram(const NGram& source, ngram_type_t ngram_type): _frequency(source._frequency) {
    // Store N-gram type within frequency.
    _type(ngram_type);
    for ( ngram_size_t i = 0, j = n(), s = 0; i < n(); ++i ) {
        // If j-th bit set, then copy member, otherwise do nothing.
        if ( ith_bit(ngram_type, --j) ) { // !
            new (get(s)) Member(*source.get(i)); // Use implicitly created default constructor.
            ++s; // !
        }
    }
    // Don't copy context, make new (the only copy of context should be within pooled instance).
    if ( _context_tracing_on ) {
        new (context()) context_t();
    }
}

/*  Interface item implementation - for info see description in header file.
 */
void NGram::inc(void) {
    if ( frequency() == _max_frequency ) {
        // Store type.
        ngram_type_t t = type();
        // Store frequency.
        _overflows.add(this, frequency());
        // Reset counter.
        _frequency = 0;
        // Restore type.
        _type(t);
        // Set overflow flag bit on.
        _frequency_bits[_last_bit_index] |= _overflow_flag_mask;
    }
    // Std way.
    ++_frequency;
}

/*  Interface item implementation - for info see description in header file.
 */
void NGram::add_to_context(const PartOfContext& part_of_context) {
    if ( !_context_tracing_on ) {
        return;
    }

    context_t *ctx = context();
    context_t::iterator i_part_of_context = std::find(ctx->begin(), ctx->end(), part_of_context);
    if ( i_part_of_context != ctx->end() ) {
        i_part_of_context->inc(); // This may throw!
        if ( i_part_of_context != ctx->begin() ) {
            // Keep context sorted by their frequency (DESC).
            context_t::iterator prev = i_part_of_context - 1;
            while ( prev->frequency() < i_part_of_context->frequency() ) {
                // Swap values.
                std::swap(*prev, *i_part_of_context);
                i_part_of_context = prev;
                if ( i_part_of_context == ctx->begin() ) {
                    break;
                } else {
                    prev = i_part_of_context - 1;
                }
            }
        }   
        return;
    }
    // Otherwise needs to be stored...
    ctx->push_back(part_of_context);
}

/*  Interface item implementation - for info see description in header file.
 */
bool operator==(const NGram& lhs, const NGram& rhs) {
    
    // Types needed to be checked first.
    if ( lhs.type() != rhs.type() ) {
        return false;
    }
    
    // N-gram types are equal => both N-grams have to have the same degree.
    ngram_size_t mc = lhs.degree(); 

    for ( ngram_size_t i = 0; i < mc; ++i ) {   
        // Compare lemmas first, then parent indices, dependency and tags in the end.
        if ( lhs.lemma(i) != rhs.lemma(i) ) {
            return false;
        }
#ifdef _DEPENDENCY_MODE
        if ( lhs.parent(i) != rhs.parent(i) ) {
            return false;
        }
        if ( lhs.dependency(i) != rhs.dependency(i) ) {
            return false;
        }
#endif
        if ( lhs.tag(i) != rhs.tag(i) ) {
            return false;
        }
    }
    // R == L
    return true;

}

/*  Interface item implementation - for info see description in header file.
 */
bool operator<(const NGram& lhs, const NGram& rhs) {

    // Types needed to be checked first.
    if ( lhs.type() < rhs.type() ) {
        return true;
    }
    if ( rhs.type() < lhs.type() ) {
        return false;
    }
    // N-gram types are equal => both N-grams have to have the same degree.
    ngram_size_t mc = lhs.degree();
    
    for ( ngram_size_t i = 0; i < mc; ++i ) {
        // Compare lemmas first, then parent indices, dependency and tags in the end.
        if ( lhs.lemma(i) < rhs.lemma(i) ) {
            // L < R
            return true;
        }
        if ( rhs.lemma(i) < lhs.lemma(i) ) {
            // R < L
            return false;
        }
#ifdef _DEPENDENCY_MODE
        if ( lhs.parent(i) < rhs.parent(i) ) {
            // L < R
            return true;
        }
        if ( rhs.parent(i) < lhs.parent(i) ) {
            // R < L
            return false;
        }
        if ( lhs.dependency(i) < rhs.dependency(i) ) {
            // L < R
            return true;
        }
        if ( rhs.dependency(i) < lhs.dependency(i) ) {
            // R < L
            return false;
        }
#endif
        if ( lhs.tag(i) < rhs.tag(i) ) {
            // L < R
            return true;
        }
        if ( rhs.tag(i) < lhs.tag(i) ) {
            // R < L
            return false;
        }
    }
    // R == L
    return false;
}


void *NGramToken::_ngram_space = 0;

/*  Interface item implementation - for info see description in header file.
 */
void NGramToken::init(void) {   
    // Space big enough to store full N-gram type.
    _ngram_space = operator new(NGram::size_of(NGram::n()));
}

/*  Interface item implementation - for info see description in header file.
 */
NGram * NGramToken::get(const raw_ngram_t& raw_ngram, ngram_type_t ngram_type) {
    return new (_ngram_space) NGram(raw_ngram, ngram_type);
}

/*  Interface item implementation - for info see description in header file.
 */
NGram * NGramToken::get(const NGram *source, ngram_type_t ngram_type) {
    return new (_ngram_space) NGram(*source, ngram_type);
}

} // namespace ace

---