proto/Source/extractor.cpp

Go to the documentation of this file.

#include <algorithm>
#include <utility>
#include <vector>

// Buffer interface.
#include "buffer.h"
// Basic typedefs.
#include "config.h"
// Self header.
#include "extractor.h"
// NGrams.
#include "ngram.h"
// Progress display.
#include "notifier.h"
#ifdef _DEPENDENCY_MODE
// N-trees extraction.
#include "ntree.h"
#endif
// Parsing.
#include "parser.h"
// Global stores.
#include "persistent.h"
// ith_bit() needed.
#include "utils.h"
// Word store and range types.
#include "word.h"

namespace ace {

#ifdef _DEPENDENCY_MODE

void _build_tree(const words_range_t& sentence, ntree_t& nodes) {   

    words_range_t::first_type word = sentence.first;

    // Init with nodes.
    while ( word != sentence.second ) {
        nodes.push_back(NTreeNode(word->order(), word->parent()));
        ++word;
    }

    // Add childs to nodes. 
    for ( word_order_t i = 1; i < nodes.size(); ++i ) {
        nodes[nodes[i].parent()].add_child(i);
    }
}


words_store_t::const_iterator _extract_ngram(words_store_t::const_iterator sentence_start, const subtree_t& subtree, raw_ngram_t& raw_ngram) {
    //
    words_store_t::const_iterator word, head;

    // 1. Loop through subtree members, store raw N-gram data
    for ( subtree_t::const_iterator i_subtree = subtree.begin(); i_subtree != subtree.end(); ++i_subtree ) {
        // Word coresponding to current member.
        word = sentence_start + *i_subtree - 1; // -1 => indices within subtree_t goes from 1, not 0.
        // Find position of word parent node in `subtree` - we need to know its (new) index in n-gram tree.
        std::pair<subtree_t::const_iterator, subtree_t::const_iterator> i_parent = std::equal_range(subtree.begin(), subtree.end(), word->parent());
        if ( i_parent.first == i_parent.second ) {
            // The only node whom parent isn't in subtree, is root (head) node of n-gram.
            // Store ngram member - use 0 to indicate root member.
            raw_ngram.push_back(raw_ngram_t::value_type(0, word));
            // Store the iterator to N-gram head for output.
            head = word;
        } else {
            // Store ngram member - count its new parent index on the base of subtree form.
            raw_ngram.push_back(raw_ngram_t::value_type(static_cast<ngram_size_t>(i_parent.second - subtree.begin()), word));
        }
    }

    return head;
}
#endif // _DEPENDENCY_MODE

NGram * _store_ngram(const raw_ngram_t& raw_ngram, ngram_type_t type) {     

    // Apply morphologic filter, if on. 
    // Note: 0 typed N-gram will always pass, so don't waste your time with types like him.
    if ( persistent::morphologic_filter.is_on() && (type != 0) ) {
        // Once initialized, stays of the same size (only contents changes)
        static multirule_t tags(NGram::n());
        static std::string empty;               
        
        ngram_type_t i = NGram::n() - 1;
        
        // Raw N-gram contains all N members, but the N-gram type specifies which members are realy significant.
        for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem, --i) {
#ifdef _DEPENDENCY_MODE
            tags[i] = ith_bit(type, i) ? persistent::tags.get(i_mem->second->tag()) : empty;
#else
            tags[i] = ith_bit(type, i) ? persistent::tags.get((*i_mem)->tag()) : empty;
#endif
        }
        // Count filter stats for full N-grams only.
        if ( !persistent::morphologic_filter.match(tags, type == NGram::full_ngram_type()) ) {
            return NULL;
        }
    }

    // Construct NGram by specially crafted static method, insert and...
    NGramStore::insert_status_t pb = persistent::ngrams.insert(NGramToken::get(raw_ngram, type));
    // ...check insertion status.
    if ( !pb.second ) {
        // N-gram already present in the store, so increment its counter.
        pb.first->inc();
    }
    // Return pointer to stored instance.
    return pb.first;
}

void _store_wide_context(NGram *ngram, const raw_ngram_t& raw_ngram, words_range_t context_range) {
    // 
    size_t found_so_far = 0;
    // Loop through the given range and store the words within, but don't store the N-gram members itself.
    for ( words_store_t::const_iterator w = context_range.first; w != context_range.second; ++w ) {
next_loop:
        if ( found_so_far < raw_ngram.size() ) {
            // Not all members founded yet.
            ngram_type_t i = NGram::n(); // Should start on n-1, but gets "predecremented" every loop.
            for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem ) {
                // Check, if current N-gram type contains this word.
                if ( ith_bit(ngram->type(), --i) ) {
                    // Don't store the members themself.
#ifdef _DEPENDENCY_MODE
                    // raw_ngram_member_t is a pair and we are interested in second value.
                    if ( w == i_mem->second ) {
#else
                    // raw_ngram_member_t is another name for words_store_t::const_iterator.
                    if ( w == *i_mem ) {
#endif
                        ++found_so_far; // One more member founded.
                        ++w; // Go to next word - required, because of:
                        if ( w != context_range.second ) {
                            goto next_loop;
                        } else {
                            goto end;
                        }
                    }
                }
                // Else not a member (discarded by *).
            }
        }
        
        if ( persistent::context_filter.is_on()
                && !persistent::context_filter.match(persistent::tags.get(w->tag()), false) ) {
            // Don't store the words that doesn't pass the context filter.
            continue;
        }

        ngram->add_to_context(PartOfContext(w->lemma(), w->tag()));
    }
end:
    ;
}

#ifdef _DEPENDENCY_MODE
void _store_raw_ngram(const raw_ngram_t& raw_ngram, const Buffer& buffer, NamedDataFileStats& stats, words_store_t::const_iterator head)
#else
void _store_raw_ngram(const raw_ngram_t& raw_ngram, const Buffer& buffer, NamedDataFileStats& stats)
#endif
{
    NGram * ngram = NULL;
    // Store the raw N-gram as NGram instances of all kinds.
    for ( ngram_type_t type = 0; type <= NGram::full_ngram_type(); ++type ) {

        // Store the N-gram (function performs morphologic check, if required).
        ngram = _store_ngram(raw_ngram, type);

        if ( type == NGram::full_ngram_type() ) {
            // Update datafile stats (count only full N-grams).
            ++stats.ngrams.extracted;
            if ( ngram == NULL ) {
                ++stats.ngrams.filtered;
            } else {
                ++stats.ngrams.passed;
            }
        }
        
        if ( (ngram != NULL) && settings::context_tracing_on() ) {
            // Store context.
            if ( (type != 0) ) {
                // Zero-typed N-grams are contextless and so are the "I didn't make it through filter" N-grams :)
                if ( settings::context_window.mode == ContextWindow::SENTENCE_MODE ) {
                    _store_wide_context(ngram, raw_ngram, buffer.context_range());
                } else {
#ifdef _DEPENDENCY_MODE
                    _store_wide_context(ngram, raw_ngram, buffer.context_range(head));
#else
                    _store_wide_context(ngram, raw_ngram, buffer.context_range(raw_ngram.front(), raw_ngram.back()));
#endif
                }
            }
            
            if ( type == NGram::full_ngram_type() ) {
                // Full N-grams need their narrow context to be traced.
                // Front and back members of current N-gram.
#ifdef _DEPENDENCY_MODE
                words_store_t::const_iterator front = raw_ngram.front().second, back = raw_ngram.back().second;
#else
                words_store_t::const_iterator front = raw_ngram.front(), back = raw_ngram.back();
#endif
                if ( front != buffer.current().first ) {
                    ngram->add_to_context(PartOfContext((front - 1)->lemma(), (front - 1)->tag(), true));
                }
                if ( (back + 1) != buffer.current().second ) { // current().second is already pointing behind!
                    ngram->add_to_context(PartOfContext((back + 1)->lemma(), (back + 1)->tag(), true));
                }
            }
        }
    }
}

/*  Interface item implementation - for info see description in header file.
 */
size_t extract(std::ifstream& input_file, NamedDataFileStats& stats) {
        
    // Count file length.
    input_file.seekg(0, std::ios::end);
    std::streampos pos = input_file.tellg();
    input_file.seekg(0, std::ios::beg);

    size_t file_size = (pos < 0) ? static_cast<std::streampos>(0) : pos;

#ifdef _BOOST_ON

    bool progress_bar_on = true;
    
    // Progress display. If tellg failed, show 0 sized progress bar.
    progress_display_t display(static_cast<unsigned long>(file_size), notifier::progress.output_stream(), "");
    
    if ( pos < 0 ) {
        notifier::error.warning("Progress bar initialization failed! Going on without progress bar display...");
        progress_bar_on = false;
    }
    // 
    size_t processed_so_far = 0;
#endif


    // Extracted N-gram (raw).
    raw_ngram_t raw_ngram;

#ifdef _DEPENDENCY_MODE
    // Vector for NTreeNodes.
    ntree_t nodes;
    NTreeNode abstract_root_node = NTreeNode();
    nodes.push_back(abstract_root_node);

    // Extracted subtrees.
    mapped_subtrees_t subtrees;
#else
    static bools_table_t decomps = bools_table(settings::n - 1, settings::collocation_window_size);
    //
    words_range_t sentence;
    words_store_t::const_iterator word, current_word;
    // Resize raw N-gram (stores items with default constructor).
    raw_ngram.resize(settings::n);
#endif


    // Parser for current file.
    Parser parser(input_file);
    Buffer buffer(parser, settings::context_window);

    
    if ( buffer.empty() ) {
        // Buffer initialization failed, probably file is corrupted.
        return 0;
    }
    
    do {
#ifdef _DEPENDENCY_MODE
        // 1. Build grammar dependency tree from sentence.
        _build_tree(buffer.current(), nodes);

        // 2. Pass the tree to ntree subtree extractor coupled with size of subtrees (which is N)
        extract_subtrees(nodes, NGram::n(), subtrees);

        // 3. Loop through extracted subtrees.
        for ( mapped_subtrees_t::const_iterator i_subtree = subtrees.begin(); i_subtree != subtrees.end(); ++i_subtree ) {      
            // Get related N-gram (as raw).
            words_store_t::const_iterator head = _extract_ngram(buffer.current().first, i_subtree->second, raw_ngram);
            // Store N-gram (also stores context, if needed).
            _store_raw_ngram(raw_ngram, buffer, stats, head);
            // Clear N-gram container for next loop.
            raw_ngram.clear();
        }           
#else
        // Get whole sentence.
        sentence = buffer.current();
        if ( (sentence.second - sentence.first) < settings::n ) {
            // Sentence is too short, go to next one.
            continue;
        }
        current_word = sentence.first;
        do {            
            size_t rn = 0;
            raw_ngram[rn] = current_word;

            // Extract raw N-grams.
            for ( size_t i = 0; i < decomps.size(); ++i ) {
                // !
                rn = 0;
                // Loop through tables.
                size_t stop_at = std::min(decomps[i].size(), static_cast<size_t>((sentence.second - current_word) - 1));
                // We want to stop before range end!
                for ( size_t j = 0; j < stop_at; ++j ) {
                    // For every i: decomps[i].size() == collocation_window_size !
                    // Loop through each table.
                    if ( decomps[i][j] ) {
                        // Add (j+1)-th item after current word.
                        raw_ngram[++rn] = current_word + j + 1; // j is zero indexed!
                    }
                }
                // If all N members are freshly included (may be not true, if sentence end is near).
                if ( ++rn == settings::n ) {
                    // Also stores context, if needed.
                    _store_raw_ngram(raw_ngram, buffer, stats);
                }
            }

            ++current_word;

        // Stop when there is less than N words between current word (inclusive) and end of sentence.
        } while ( current_word <= (sentence.second - settings::n) );

#endif
#ifdef _BOOST_ON
        // 4. Progress bar update (set, if it's possible to retrieve current pointer position within the ifstream)
        if ( progress_bar_on ) {
            if ( parser.eof() ) {
                // Ok, we're done. Let progress bar reach its end.s
                display += display.expected_count() - display.count();
                // And leave.
                break;
            }
            pos = input_file.tellg();
            if ( (pos < 0) ) {
                // Current pointer position within the stream cannot be retrieved!
                notifier::progress.info("\n"); // Finish progress bar display.
                notifier::error.warning("Progress bar update failed! Stopping progress bar display..."); // Warn.
                progress_bar_on = false;
            } else {
                // Ok, update progress bar (add only as much as have been processed since last update)
                display += static_cast<unsigned long>(static_cast<size_t>(pos) - processed_so_far);
                processed_so_far = static_cast<size_t>(pos);
            }
        }
#endif
#ifdef _DEPENDENCY_MODE
        // 5. Get prepared for the next loop.
        // Keep only root node, drop anything else.
        nodes.resize(1);
        nodes[0] = abstract_root_node; // Re-assignment clears the child nodes of abstract tree node.
        // Clear containers for the next loop.
        subtrees.clear();
#endif
    // Advance buffer to the next sentence.
    } while ( buffer.next() );

    // Add buffer file statistics (words, sentences parsed) to extractor statistics (N-grams extracted).
    stats += buffer.stats();

    return file_size;
    
}

} // namespace ace

---