PLearn 0.1
|
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 :