PLearn 0.1
NGramTree.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // NGramTree.cc
00004 //
00005 // Copyright (C) 2004 Hugo Larochelle
00006 //
00007 // Redistribution and use in source and binary forms, with or without
00008 // modification, are permitted provided that the following conditions are met:
00009 //
00010 //  1. Redistributions of source code must retain the above copyright
00011 //     notice, this list of conditions and the following disclaimer.
00012 //
00013 //  2. Redistributions in binary form must reproduce the above copyright
00014 //     notice, this list of conditions and the following disclaimer in the
00015 //     documentation and/or other materials provided with the distribution.
00016 //
00017 //  3. The name of the authors may not be used to endorse or promote
00018 //     products derived from this software without specific prior written
00019 //     permission.
00020 //
00021 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00022 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00023 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00024 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00025 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00026 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00027 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00028 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00029 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00030 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031 //
00032 // This file is part of the PLearn library. For more information on the PLearn
00033 // library, go to the PLearn Web site at www.plearn.org
00034 
00035 /* *******************************************************
00036  * $Id: NGramTree.cc 5865 2006-06-14 18:13:50Z larocheh $
00037  ******************************************************* */
00038 
00039 // Authors: Hugo Larochelle
00040 
00044 #include "NGramTree.h"
00045 
00046 namespace PLearn {
00047 using namespace std;
00048 
00049 NGramTree::NGramTree()
00050 {
00051     forget();
00052 }
00053 
00054 NGramTree::NGramTree(PP<SymbolNode> root_)
00055 {
00056     setRoot(root_);
00057 }
00058 
00059 PLEARN_IMPLEMENT_OBJECT(NGramTree,
00060                         "NGram tree that counts frequencies",
00061                         "NGramTree uses a suffix tree on the context ( i.e. the (n-1)gram) to count frequencies of ngrams and\n"
00062                         "and their suffixes with their corresponding normalization factor for probability estimation.");
00063 
00064 
00065 void NGramTree::declareOptions(OptionList& ol)
00066 {
00067     // ### Declare all of this object's options here
00068     // ### For the "flags" of each option, you should typically specify
00069     // ### one of OptionBase::buildoption, OptionBase::learntoption or
00070     // ### OptionBase::tuningoption. Another possible flag to be combined with
00071     // ### is OptionBase::nosave
00072 
00073     declareOption(ol, "root", &NGramTree::root, OptionBase::learntoption,
00074                   "root of the NGramTree");
00075 
00076     inherited::declareOptions(ol);
00077 }
00078 
00079 void NGramTree::build_(){}
00080 
00081 // ### Nothing to add here, simply calls build_
00082 void NGramTree::build()
00083 {
00084     inherited::build();
00085     build_();
00086 }
00087 
00088 void NGramTree::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00089 {
00090     inherited::makeDeepCopyFromShallowCopy(copies);
00091 
00092     //PLERROR("NGramTree::makeDeepCopyFromShallowCopy not fully (correctly) implemented yet!");
00093 }
00094 
00095 void NGramTree::add(TVec<int> ngram)
00096 {
00097     if(ngram.length() == 0)
00098         return;
00099     PP<SymbolNode> it = root;
00100     it->incr(ngram[ngram.length()-1]);
00101     for(int i=ngram.length()-2; i>=0; i--)
00102     {
00103         it = it->add(ngram[i]);
00104         it->incr(ngram[ngram.length()-1]);
00105     }
00106 }
00107 
00108 TVec<int> NGramTree::freq(TVec<int> ngram)
00109 {
00110     TVec<int> ret(ngram.length());
00111     ret.fill(0);
00112     ret[0] = root->freq(ngram[ngram.length()-1]);
00113 
00114     int n=1;
00115     PP<SymbolNode> it = root;
00116     for(int i=ngram.length()-2; i>=0; i--)
00117     {
00118         it = it->child(ngram[i]);
00119         if(!it)
00120             break;
00121         ret[n] = it->freq(ngram[ngram.length()-1]);
00122         n++;
00123     }
00124     return ret;
00125 }
00126 
00127 TVec<map<int,int> *> NGramTree::freqs(TVec<int> ngram)
00128 {
00129     TVec<map<int,int>* > ret(ngram.length());
00130     ret[0] = root->freqs();
00131   
00132     int n=1;
00133     PP<SymbolNode> it = root;
00134     for(int i=ngram.length()-2; i>=0; i--)
00135     {
00136         it = it->child(ngram[i]);
00137         if(!it)
00138             break;
00139         ret[n] = it->freqs();
00140         n++;
00141     }
00142     return ret;
00143 }
00144 
00145 TVec<int> NGramTree::normalization(TVec<int> ngram)
00146 {
00147     TVec<int> ret(ngram.length());
00148     ret.fill(0);
00149     ret[0] = root->freq();
00150 
00151     int n=1;
00152     PP<SymbolNode> it = root;
00153     for(int i=ngram.length()-2; i>=0; i--)
00154     {
00155         it = it->child(ngram[i]);
00156         if(!it)
00157             break;
00158         ret[n] = it->freq();
00159         n++;
00160     }
00161     return ret;
00162 }
00163 
00164 int NGramTree::n_children(TVec<int> sequence)
00165 {
00166     if(sequence.length()==0)
00167         return 0;
00168 
00169     PP<SymbolNode> it = root;
00170     for(int i=sequence.length()-2; i>=0; i--)
00171     {
00172         it = it->child(sequence[i]);
00173         if(!it)
00174             return 0;
00175     }
00176 
00177     return it->n_children();;
00178 }
00179 
00180 TVec<int> NGramTree::n_freq(TVec<int> sequence)
00181 {
00182     TVec<int> ret(0);
00183     if(sequence.length()==0)
00184         return ret;
00185 
00186     ret.resize(sequence.length());
00187     ret.fill(0);
00188 
00189     PP<SymbolNode> it = root;
00190     int n=0;
00191     ret[n++] = it->n_freq();
00192     for(int i=sequence.length()-2; i>=0; i--)
00193     {
00194         it = it->child(sequence[i]);
00195         if(!it)
00196             return ret;
00197         ret[n++] = it->n_freq();
00198     }
00199     return ret;
00200 }
00201 /*
00202   TVec<PP<NGramTree> > NGramTree::getSubTrees(TVec<int> sequence)
00203   {
00204   PP<SymbolNode> it = root;
00205 
00206   TVec<PP<NGramTree> > ret(0);
00207 
00208   if(sequence.length()==0)
00209   {
00210   ret.resize(it->n_children());
00211   TVec<PP<SymbolNode> > nodes = it->getChildren();
00212   for(int j=0; j<nodes.length(); j++)
00213   ret[j] = new NGramTree(nodes[j]);
00214   return ret;
00215   }
00216 
00217   for(int i=sequence.length()-1; i>=0; i--)
00218   {
00219   it = it->child(sequence[i]);
00220   if(!it)
00221   break;
00222   if(i==0)
00223   {
00224   ret.resize(it->n_children());
00225   TVec<PP<SymbolNode> > nodes = it->getChildren();
00226   for(int j=0; j<nodes.length(); j++)
00227   {
00228   ret[j] = new NGramTree(nodes[j]);
00229   }
00230   return ret;
00231   }
00232   }
00233   return ret;
00234   }
00235 */
00236 
00237 void NGramTree::forget()
00238 {
00239     root = new SymbolNode();
00240 }
00241 
00242 } // end of namespace PLearn
00243 
00244 
00245 /*
00246   Local Variables:
00247   mode:c++
00248   c-basic-offset:4
00249   c-file-style:"stroustrup"
00250   c-file-offsets:((innamespace . 0)(inline-open . 0))
00251   indent-tabs-mode:nil
00252   fill-column:79
00253   End:
00254 */
00255 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines