proto/Source/ngrams.cpp

Go to the documentation of this file.

// Self header.
#include "ngrams.h"

namespace ace {

const ngram_size_t _max_n = 8;

#ifdef _64_BIT
const size_t _lemma_bitmasks[_max_n+1] = {
    0x00, // 0: 0......0
    0xFFFFFFFF, // 1: last (whole) 32 bits
    0x00FFFFFF, // 2: last 24 bits
    0x0000FFFF, // 3: last 16 bits
    0x000003FF, // 4: last 10 bits
    0x000000FF, // 5: last 8 bits
    0x000000FF, // 6: dtto
    0x000000FF, // 7: dtto
    0x000000FF, // 8: dtto
};
#ifdef _DEPENDENCY_MODE
const size_t _dependency_bitmasks[_max_n+1] = { 
    0x00, // 0: 0......0
    0x7C, // 1: 01111100 (whole significant part)
    0x7C, // 2: 01111100 (dtto)
    0x3C, // 3: 00111100
    0x3C, // 4: 00111100
    0x1C, // 5: 00011100
    0x1C, // 6: 00011100
    0x0C, // 7: 00001100
    0x04 //  8: 00000000
};
const size_t _parent_bitmasks[_max_n+1] = {
    0x00, // 0: 0......0
    0x03, // 1: 00000011 (whole significant part)
    0x03, // 2: 00000011 (dtto)
    0x03, // 3: 00000011 (dtto)
    0x03, // 4: 00000011 (dtto)
    0x03, // 5: 00000011 (dtto)
    0x00, 0x00, 0x00 // 6-8: 0......0
};
const size_t _dp_shift[_max_n+1] = {
    0, // 0: see lemma bitmask
    32, // 1: dtto
    24, // 2: dtto
    16, // 3: dtto
    10, // 4: dtto
    8, // 5: dtto
    6, // 6: |lemma bitmask| - |no of trailing zero digits in dependency bitmask|
    6, // dtto
    0 // 8: dependency and parent bitmask are 0-length
};
#endif
// Rounded up.
const size_t _bits_per_member[_max_n+1] = { 0, 64, 32, 22, 16, 13, 11, 10, 8 };

#else // 32-bit
const size_t _lemma_bitmasks[_max_n+1] = {
    0x00, // 0: 0......0
    0x00FFFFFF, // 1: last 24 bits
    0x00000FFF, // 2: last 12 bits
    0x000000FF, // 3: last 8 bits
    0x0000003F, // 4: last 6 bits
    0x0000003F, // 5: last 6 bits
    0x0000003F, // 6: last 6 bits
    0x0000001F, // 7: last 5 bits
    0x0000000F, // 8: last 4 bits
};

#ifdef _DEPENDENCY_MODE
const size_t _dependency_bitmasks[_max_n+1] = { 
    0x00, // 0: 0......0
    0x7C, // 1: 01111100
    0x0C, // 2: 00001100
    0x1C, // 3: 00011100
    0x0C, // 4: 00001100
    0x04, // 5: 00000100
    0x00, 0x00, 0x00 // 6-8: 0......0
};
const size_t _parent_bitmasks[_max_n+1] = {
    0x00, // 0: 0......0
    0x03, // 1: 00000011
    0x03, // 2: 00000011
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00 // 3-8: 0......0
};
const size_t _dp_shift[_max_n+1] = {
    0, // 0: see lemma bitmask
    24, // 1: dtto
    12, // 2: dtto
    6, // 3: |lemma bitmask| - |no of trailing zero digits in dependency bitmask|
    4, // 4: dtto
    4, // 5: dtto
    0, 0, 0 // 6-8: dependency and parent bitmask are 0-length
};
#endif
// Rounded up.
const size_t _bits_per_member[_max_n+1] = { 0, 32, 16, 11, 8, 7, 6, 5, 4 };

#endif // 64-bit vs. 32-bit

/*  Interface item implementation - for info see description in header file.
 */
size_t NGramHashCounter::count_hash(const NGram *gram) {

    // Hash, loop counter.
    size_t hash = _seed, loop = 0;
    // How many loops to perform?
    ngram_size_t mc = gram->degree();
#ifndef _SURFACE_MODE
    size_t db = _dependency_bitmasks[mc], pb = _parent_bitmasks[mc], lb = _lemma_bitmasks[mc], dp_s = _dp_shift[mc], bpm = _bits_per_member[mc];
#else
    size_t lb = _lemma_bitmasks[mc], bpm = _bits_per_member[mc];
#endif

    for ( const NGram::Member * i_mem = gram->begin(); i_mem != gram->end(); ++i_mem, ++loop ) {
        hash ^=
            (
#ifndef _SURFACE_MODE
                (
                    (
                        // Dependency and parent bitmasks didn't overlap, so we can use them all in one expression.
                        (i_mem->dependency() & db) | (i_mem->parent() & pb)
                    )
                    // The result is shifted to gain room for lemma bitmask.
                    << dp_s
                )
                |
#endif
                // Apply and add lemma bitmask.
                (i_mem->lemma() & lb)
            )
            // Shift the l-th loop (member) related bits to their position in final hash.
            << loop * bpm;
    }
    return hash;

}

/*  Interface item implementation - for info see description in header file.
 */
bool NGramHashCounter::check(ngram_size_t n) {
    return _max_n >= n;
}

#ifdef _USE_HASHSET

#if defined(__GNUC__)

/*  Interface item implementation - for info see description in header file.
 */
bool NGramEqualComparator::operator()(const NGram *lhs, const NGram *rhs) const {
    return *lhs == *rhs;
}

#elif defined(_MSC_VER)

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

/* Static members initialization.
 */
NGramHasher NGramHashCompare::_hasher;
NGramLessComparator NGramHashCompare::_comparator;

#endif

#endif // _USE_HASHSET



/*  Interface item implementation - for info see description in header file.
 */
NGramStore::NGramStore(size_t memory_pool_block_size): _memory_pools(), _hash_tables() {
    if ( memory_pool_block_size ) {
        init(memory_pool_block_size);
    }
    // Otherwise postpone initialization process (explicit call to init() will be needed).
}

/*  Interface item implementation - for info see description in header file.
 */
const NGram * NGramStore::get(const NGram *ngram) const {   
    if ( ngram->is_zero() ) {
        return &zero_ngram;
    }
    // Search for N-gram in hash tables using _find().
    _hash_table_pair_cib_t pair_cib = _find(ngram);

    if ( pair_cib.second ) {
        // Founded!
        return *(pair_cib.first);
    }
    // Otherwise => not found.
    return NULL;
}

/*  Interface item implementation - for info see description in header file.
 */
void NGramStore::init(size_t memory_pool_block_size) {
    if ( memory_pool_block_size && _hash_tables.empty() && _memory_pools.empty() ) {
        // Hash tables - separate table for each type.
#ifdef _USE_HASHSET
        // Create hash tables by use of default constructor.
        _hash_tables.resize(NGram::types_count());
#else
        // Create hash tables - pass appropriate settings values.
        _hash_tables.push_back(hash_table_t(0, 0, 0)); // Zero-index padding.
        for ( ngram_type_t type = 1; type < NGram::types_count(); ++type ) {
            // TODO: Literal!
            _hash_tables.push_back(hash_table_t(8, settings::bucket_size, settings::crop_ratio));
        }
#endif
        // Pools - separate pool for each degree.
        _memory_pools.push_back(VoidPool(0)); // Zero-index padding.
        for ( ngram_size_t degree = 1; degree <= NGram::n(); ++degree ) {
            // Make each pool contain exactly `memory_pool_block_size` units.
            _memory_pools.push_back(VoidPool(memory_pool_block_size*NGram::size_of(degree)));
        }
    }
}

/*  Interface item implementation - for info see description in header file.
 */
NGramStore::insert_status_t NGramStore::insert(const NGram *ngram) {
    if ( ngram->is_zero() ) {           
        return insert_status_t(&zero_ngram, false);
    }
    // Search for N-gram in hash tables using _find().
    _hash_table_pair_cib_t pair_cib = _find(ngram);

    if ( pair_cib.second ) {
        // Founded!
        return insert_status_t(*pair_cib.first, false);
    }

    // Note: we cannot insert ngram directly, because we DO want its copy
    // to be inserted eventually.

    // New object - new memory needed...
    void *mem = _memory_pools[ngram->degree()].get_raw_memory(ngram->size_of()); // This may throw.
    
    // Copy passed word to new memory using copy constructor and placement new,
    // insert pointer to hash table and return dereferenced iterator.
    return insert_status_t(*_hash_tables[ngram->type()].insert(new (mem) NGram(*ngram)).first, true);
}

/*  Interface item implementation - for info see description in header file.
 */
NGramStore::_hash_table_pair_cib_t NGramStore::_find(const NGram *ngram) const {
    //
    std::pair<hash_table_t::const_iterator, hash_table_t::const_iterator> ip = _hash_tables[ngram->type()].equal_range(const_cast<NGram *>(ngram));
    // If iterators are different, we found what we looked for.
    return _hash_table_pair_cib_t(ip.first, ip.first != ip.second);
}

#ifndef _USE_HASHSET
void NGramStore::sort(ngram_type_t type) {
    if ( type == 0 ) {
        // 0 means sort all (except 0 itself:)
        for ( type = 1; type <= NGram::full_ngram_type(); ++type ) {
            _hash_tables[type].sort();
        }
    } else {
        _hash_tables[type].sort();
    }
}
#endif



/*  Interface item implementation - for info see description in header file.
 */
bool NGramsProcessor::next(void) {
    if ( _next == _end ) {
        return false;
    }
    // Otherwise...
    _ngram_frequencies.ngram = *_next;

    // Full N-gram frequency needs to be stored too.
    _ngram_frequencies.frequencies[NGram::full_ngram_type()] = _ngram_frequencies.ngram->frequency();
    
    for ( ngram_type_t type = 0; type < NGram::full_ngram_type(); ++type ) {
        // Create instance of N-gram downcasted to `type` and get frequency of his hash-stored alter ego.
        _ngram_frequencies.frequencies[type] = _ngram_store.get(NGramToken::get(*_next, type))->frequency();;
    }
    // Advance to next...
    ++_next;

    return true;
}

} // namespace ace

---