- Main Page
- Namespaces
- Classes
- Files

# proto/Source/extractor.cpp

Go to the documentation of this file.

    00001
    00011 #include <algorithm>
    00012 #include <utility>
    00013 #include <vector>
    00014
    00015 // Buffer interface.
    00016 #include "buffer.h"
    00017 // Basic typedefs.
    00018 #include "config.h"
    00019 // Self header.
    00020 #include "extractor.h"
    00021 // NGrams.
    00022 #include "ngram.h"
    00023 // Progress display.
    00024 #include "notifier.h"
    00025 #ifdef _DEPENDENCY_MODE
    00026 // N-trees extraction.
    00027 #include "ntree.h"
    00028 #endif
    00029 // Parsing.
    00030 #include "parser.h"
    00031 // Global stores.
    00032 #include "persistent.h"
    00033 // ith_bit() needed.
    00034 #include "utils.h"
    00035 // Word store and range types.
    00036 #include "word.h"
    00037
    00038 namespace ace {
    00039
    00040 #ifdef _DEPENDENCY_MODE
    00041
    00047 void _build_tree(const words_range_t& sentence, ntree_t& nodes) {
    00048
    00049     words_range_t::first_type word = sentence.first;
    00050
    00051     // Init with nodes.
    00052     while ( word != sentence.second ) {
    00053         nodes.push_back(NTreeNode(word->order(), word->parent()));
    00054         ++word;
    00055     }
    00056
    00057     // Add childs to nodes.
    00058     for ( word_order_t i = 1; i < nodes.size(); ++i ) {
    00059         nodes[nodes[i].parent()].add_child(i);
    00060     }
    00061 }
    00062
    00063
    00070 words_store_t::const_iterator _extract_ngram(words_store_t::const_iterator sentence_start, const subtree_t& subtree, raw_ngram_t& raw_ngram) {
    00071     //
    00072     words_store_t::const_iterator word, head;
    00073
    00074     // 1. Loop through subtree members, store raw N-gram data
    00075     for ( subtree_t::const_iterator i_subtree = subtree.begin(); i_subtree != subtree.end(); ++i_subtree ) {
    00076         // Word coresponding to current member.
    00077         word = sentence_start + *i_subtree - 1; // -1 => indices within subtree_t goes from 1, not 0.
    00078         // Find position of word parent node in `subtree` - we need to know its (new) index in n-gram tree.
    00079         std::pair<subtree_t::const_iterator, subtree_t::const_iterator> i_parent = std::equal_range(subtree.begin(), subtree.end(), word->parent());
    00080         if ( i_parent.first == i_parent.second ) {
    00081             // The only node whom parent isn't in subtree, is root (head) node of n-gram.
    00082             // Store ngram member - use 0 to indicate root member.
    00083             raw_ngram.push_back(raw_ngram_t::value_type(0, word));
    00084             // Store the iterator to N-gram head for output.
    00085             head = word;
    00086         } else {
    00087             // Store ngram member - count its new parent index on the base of subtree form.
    00088             raw_ngram.push_back(raw_ngram_t::value_type(static_cast<ngram_size_t>(i_parent.second - subtree.begin()), word));
    00089         }
    00090     }
    00091
    00092     return head;
    00093 }
    00094 #endif // _DEPENDENCY_MODE
    00095
    00103 NGram * _store_ngram(const raw_ngram_t& raw_ngram, ngram_type_t type) {
    00104
    00105     // Apply morphologic filter, if on.
    00106     // Note: 0 typed N-gram will always pass, so don't waste your time with types like him.
    00107     if ( persistent::morphologic_filter.is_on() && (type != 0) ) {
    00108         // Once initialized, stays of the same size (only contents changes)
    00109         static multirule_t tags(NGram::n());
    00110         static std::string empty;
    00111
    00112         ngram_type_t i = NGram::n() - 1;
    00113
    00114         // Raw N-gram contains all N members, but the N-gram type specifies which members are realy significant.
    00115         for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem, --i) {
    00116 #ifdef _DEPENDENCY_MODE
    00117             tags[i] = ith_bit(type, i) ? persistent::tags.get(i_mem->second->tag()) : empty;
    00118 #else
    00119             tags[i] = ith_bit(type, i) ? persistent::tags.get((*i_mem)->tag()) : empty;
    00120 #endif
    00121         }
    00122         // Count filter stats for full N-grams only.
    00123         if ( !persistent::morphologic_filter.match(tags, type == NGram::full_ngram_type()) ) {
    00124             return NULL;
    00125         }
    00126     }
    00127
    00128     // Construct NGram by specially crafted static method, insert and...
    00129     NGramStore::insert_status_t pb = persistent::ngrams.insert(NGramToken::get(raw_ngram, type));
    00130     // ...check insertion status.
    00131     if ( !pb.second ) {
    00132         // N-gram already present in the store, so increment its counter.
    00133         pb.first->inc();
    00134     }
    00135     // Return pointer to stored instance.
    00136     return pb.first;
    00137 }
    00138
    00144 void _store_wide_context(NGram *ngram, const raw_ngram_t& raw_ngram, words_range_t context_range) {
    00145     //
    00146     size_t found_so_far = 0;
    00147     // Loop through the given range and store the words within, but don't store the N-gram members itself.
    00148     for ( words_store_t::const_iterator w = context_range.first; w != context_range.second; ++w ) {
    00149 next_loop:
    00150         if ( found_so_far < raw_ngram.size() ) {
    00151             // Not all members founded yet.
    00152             ngram_type_t i = NGram::n(); // Should start on n-1, but gets "predecremented" every loop.
    00153             for ( raw_ngram_t::const_iterator i_mem = raw_ngram.begin(); i_mem != raw_ngram.end(); ++i_mem ) {
    00154                 // Check, if current N-gram type contains this word.
    00155                 if ( ith_bit(ngram->type(), --i) ) {
    00156                     // Don't store the members themself.
    00157 #ifdef _DEPENDENCY_MODE
    00158                     // raw_ngram_member_t is a pair and we are interested in second value.
    00159                     if ( w == i_mem->second ) {
    00160 #else
    00161                     // raw_ngram_member_t is another name for words_store_t::const_iterator.
    00162                     if ( w == *i_mem ) {
    00163 #endif
    00164                         ++found_so_far; // One more member founded.
    00165                         ++w; // Go to next word - required, because of:
    00166                         if ( w != context_range.second ) {
    00167                             goto next_loop;
    00168                         } else {
    00169                             goto end;
    00170                         }
    00171                     }
    00172                 }
    00173                 // Else not a member (discarded by *).
    00174             }
    00175         }
    00176
    00177         if ( persistent::context_filter.is_on()
    00178                 && !persistent::context_filter.match(persistent::tags.get(w->tag()), false) ) {
    00179             // Don't store the words that doesn't pass the context filter.
    00180             continue;
    00181         }
    00182
    00183         ngram->add_to_context(PartOfContext(w->lemma(), w->tag()));
    00184     }
    00185 end:
    00186     ;
    00187 }
    00188
    00195 #ifdef _DEPENDENCY_MODE
    00196 void _store_raw_ngram(const raw_ngram_t& raw_ngram, const Buffer& buffer, NamedDataFileStats& stats, words_store_t::const_iterator head)
    00197 #else
    00198 void _store_raw_ngram(const raw_ngram_t& raw_ngram, const Buffer& buffer, NamedDataFileStats& stats)
    00199 #endif
    00200 {
    00201     NGram * ngram = NULL;
    00202     // Store the raw N-gram as NGram instances of all kinds.
    00203     for ( ngram_type_t type = 0; type <= NGram::full_ngram_type(); ++type ) {
    00204
    00205         // Store the N-gram (function performs morphologic check, if required).
    00206         ngram = _store_ngram(raw_ngram, type);
    00207
    00208         if ( type == NGram::full_ngram_type() ) {
    00209             // Update datafile stats (count only full N-grams).
    00210             ++stats.ngrams.extracted;
    00211             if ( ngram == NULL ) {
    00212                 ++stats.ngrams.filtered;
    00213             } else {
    00214                 ++stats.ngrams.passed;
    00215             }
    00216         }
    00217
    00218         if ( (ngram != NULL) && settings::context_tracing_on() ) {
    00219             // Store context.
    00220             if ( (type != 0) ) {
    00221                 // Zero-typed N-grams are contextless and so are the "I didn't make it through filter" N-grams :)
    00222                 if ( settings::context_window.mode == ContextWindow::SENTENCE_MODE ) {
    00223                     _store_wide_context(ngram, raw_ngram, buffer.context_range());
    00224                 } else {
    00225 #ifdef _DEPENDENCY_MODE
    00226                     _store_wide_context(ngram, raw_ngram, buffer.context_range(head));
    00227 #else
    00228                     _store_wide_context(ngram, raw_ngram, buffer.context_range(raw_ngram.front(), raw_ngram.back()));
    00229 #endif
    00230                 }
    00231             }
    00232
    00233             if ( type == NGram::full_ngram_type() ) {
    00234                 // Full N-grams need their narrow context to be traced.
    00235                 // Front and back members of current N-gram.
    00236 #ifdef _DEPENDENCY_MODE
    00237                 words_store_t::const_iterator front = raw_ngram.front().second, back = raw_ngram.back().second;
    00238 #else
    00239                 words_store_t::const_iterator front = raw_ngram.front(), back = raw_ngram.back();
    00240 #endif
    00241                 if ( front != buffer.current().first ) {
    00242                     ngram->add_to_context(PartOfContext((front - 1)->lemma(), (front - 1)->tag(), true));
    00243                 }
    00244                 if ( (back + 1) != buffer.current().second ) { // current().second is already pointing behind!
    00245                     ngram->add_to_context(PartOfContext((back + 1)->lemma(), (back + 1)->tag(), true));
    00246                 }
    00247             }
    00248         }
    00249     }
    00250 }
    00251
    00252 /*  Interface item implementation - for info see description in header file.
    00253  */
    00254 size_t extract(std::ifstream& input_file, NamedDataFileStats& stats) {
    00255
    00256     // Count file length.
    00257     input_file.seekg(0, std::ios::end);
    00258     std::streampos pos = input_file.tellg();
    00259     input_file.seekg(0, std::ios::beg);
    00260
    00261     size_t file_size = (pos < 0) ? static_cast<std::streampos>(0) : pos;
    00262
    00263 #ifdef _BOOST_ON
    00265
    00266     bool progress_bar_on = true;
    00267
    00268     // Progress display. If tellg failed, show 0 sized progress bar.
    00269     progress_display_t display(static_cast<unsigned long>(file_size), notifier::progress.output_stream(), "");
    00270
    00271     if ( pos < 0 ) {
    00272         notifier::error.warning("Progress bar initialization failed! Going on without progress bar display...");
    00273         progress_bar_on = false;
    00274     }
    00275     //
    00276     size_t processed_so_far = 0;
    00277 #endif
    00278
    00280
    00281     // Extracted N-gram (raw).
    00282     raw_ngram_t raw_ngram;
    00283
    00284 #ifdef _DEPENDENCY_MODE
    00285     // Vector for NTreeNodes.
    00286     ntree_t nodes;
    00287     NTreeNode abstract_root_node = NTreeNode();
    00288     nodes.push_back(abstract_root_node);
    00289
    00290     // Extracted subtrees.
    00291     mapped_subtrees_t subtrees;
    00292 #else
    00293     static bools_table_t decomps = bools_table(settings::n - 1, settings::collocation_window_size);
    00294     //
    00295     words_range_t sentence;
    00296     words_store_t::const_iterator word, current_word;
    00297     // Resize raw N-gram (stores items with default constructor).
    00298     raw_ngram.resize(settings::n);
    00299 #endif
    00300
    00302
    00303     // Parser for current file.
    00304     Parser parser(input_file);
    00305     Buffer buffer(parser, settings::context_window);
    00306
    00308
    00309     if ( buffer.empty() ) {
    00310         // Buffer initialization failed, probably file is corrupted.
    00311         return 0;
    00312     }
    00313
    00314     do {
    00315 #ifdef _DEPENDENCY_MODE
    00316         // 1. Build grammar dependency tree from sentence.
    00317         _build_tree(buffer.current(), nodes);
    00318
    00319         // 2. Pass the tree to ntree subtree extractor coupled with size of subtrees (which is N)
    00320         extract_subtrees(nodes, NGram::n(), subtrees);
    00321
    00322         // 3. Loop through extracted subtrees.
    00323         for ( mapped_subtrees_t::const_iterator i_subtree = subtrees.begin(); i_subtree != subtrees.end(); ++i_subtree ) {
    00324             // Get related N-gram (as raw).
    00325             words_store_t::const_iterator head = _extract_ngram(buffer.current().first, i_subtree->second, raw_ngram);
    00326             // Store N-gram (also stores context, if needed).
    00327             _store_raw_ngram(raw_ngram, buffer, stats, head);
    00328             // Clear N-gram container for next loop.
    00329             raw_ngram.clear();
    00330         }
    00331 #else
    00332         // Get whole sentence.
    00333         sentence = buffer.current();
    00334         if ( (sentence.second - sentence.first) < settings::n ) {
    00335             // Sentence is too short, go to next one.
    00336             continue;
    00337         }
    00338         current_word = sentence.first;
    00339         do {
    00340             size_t rn = 0;
    00341             raw_ngram[rn] = current_word;
    00342
    00343             // Extract raw N-grams.
    00344             for ( size_t i = 0; i < decomps.size(); ++i ) {
    00345                 // !
    00346                 rn = 0;
    00347                 // Loop through tables.
    00348                 size_t stop_at = std::min(decomps[i].size(), static_cast<size_t>((sentence.second - current_word) - 1));
    00349                 // We want to stop before range end!
    00350                 for ( size_t j = 0; j < stop_at; ++j ) {
    00351                     // For every i: decomps[i].size() == collocation_window_size !
    00352                     // Loop through each table.
    00353                     if ( decomps[i][j] ) {
    00354                         // Add (j+1)-th item after current word.
    00355                         raw_ngram[++rn] = current_word + j + 1; // j is zero indexed!
    00356                     }
    00357                 }
    00358                 // If all N members are freshly included (may be not true, if sentence end is near).
    00359                 if ( ++rn == settings::n ) {
    00360                     // Also stores context, if needed.
    00361                     _store_raw_ngram(raw_ngram, buffer, stats);
    00362                 }
    00363             }
    00364
    00365             ++current_word;
    00366
    00367         // Stop when there is less than N words between current word (inclusive) and end of sentence.
    00368         } while ( current_word <= (sentence.second - settings::n) );
    00369
    00370 #endif
    00371 #ifdef _BOOST_ON
    00372         // 4. Progress bar update (set, if it's possible to retrieve current pointer position within the ifstream)
    00373         if ( progress_bar_on ) {
    00374             if ( parser.eof() ) {
    00375                 // Ok, we're done. Let progress bar reach its end.s
    00376                 display += display.expected_count() - display.count();
    00377                 // And leave.
    00378                 break;
    00379             }
    00380             pos = input_file.tellg();
    00381             if ( (pos < 0) ) {
    00382                 // Current pointer position within the stream cannot be retrieved!
    00383                 notifier::progress.info("\n"); // Finish progress bar display.
    00384                 notifier::error.warning("Progress bar update failed! Stopping progress bar display..."); // Warn.
    00385                 progress_bar_on = false;
    00386             } else {
    00387                 // Ok, update progress bar (add only as much as have been processed since last update)
    00388                 display += static_cast<unsigned long>(static_cast<size_t>(pos) - processed_so_far);
    00389                 processed_so_far = static_cast<size_t>(pos);
    00390             }
    00391         }
    00392 #endif
    00393 #ifdef _DEPENDENCY_MODE
    00394         // 5. Get prepared for the next loop.
    00395         // Keep only root node, drop anything else.
    00396         nodes.resize(1);
    00397         nodes[0] = abstract_root_node; // Re-assignment clears the child nodes of abstract tree node.
    00398         // Clear containers for the next loop.
    00399         subtrees.clear();
    00400 #endif
    00401     // Advance buffer to the next sentence.
    00402     } while ( buffer.next() );
    00403
    00404     // Add buffer file statistics (words, sentences parsed) to extractor statistics (N-grams extracted).
    00405     stats += buffer.stats();
    00406
    00407     return file_size;
    00408
    00409 }
    00410
    00411 } // namespace ace