ARPAPredictor.cpp
Go to the documentation of this file.
/******************************************************
* Presage, an extensible predictive text entry system
* ---------------------------------------------------
*
* Copyright (C) 2008 Matteo Vescovi <matteo.vescovi@yahoo.co.uk>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*
**********(*)*/
#include "ARPAPredictor.h"
#include <sstream>
#include <algorithm>
#include <cmath>
#define OOV "<UNK>"
ARPAPredictor::ARPAPredictor(Configuration* config, ContextTracker* ct, const char* name)
: Predictor(config,
ct,
name,
"ARPAPredictor, a predictor relying on an ARPA language model",
"ARPAPredictor, long description."
),
dispatcher (this)
{
LOGGER = PREDICTORS + name + ".LOGGER";
ARPAFILENAME = PREDICTORS + name + ".ARPAFILENAME";
VOCABFILENAME = PREDICTORS + name + ".VOCABFILENAME";
TIMEOUT = PREDICTORS + name + ".TIMEOUT";
// build notification dispatch map
dispatcher.map (config->find (LOGGER), & ARPAPredictor::set_logger);
dispatcher.map (config->find (VOCABFILENAME), & ARPAPredictor::set_vocab_filename);
dispatcher.map (config->find (ARPAFILENAME), & ARPAPredictor::set_arpa_filename);
dispatcher.map (config->find (TIMEOUT), & ARPAPredictor::set_timeout);
loadVocabulary();
createARPATable();
}
void ARPAPredictor::set_vocab_filename (const std::string& value)
{
logger << INFO << "VOCABFILENAME: " << value << endl;
vocabFilename = value;
}
void ARPAPredictor::set_arpa_filename (const std::string& value)
{
logger << INFO << "ARPAFILENAME: " << value << endl;
arpaFilename = value;
}
void ARPAPredictor::set_timeout (const std::string& value)
{
logger << INFO << "TIMEOUT: " << value << endl;
timeout = atoi(value.c_str());
}
void ARPAPredictor::loadVocabulary()
{
std::ifstream vocabFile;
vocabFile.open(vocabFilename.c_str());
if(!vocabFile)
logger << ERROR << "Error opening vocabulary file: " << vocabFilename << endl;
assert(vocabFile);
std::string row;
int code = 0;
while(std::getline(vocabFile,row))
{
if(row[0]=='#')
continue;
vocabCode[row]=code;
vocabDecode[code]=row;
logger << DEBUG << "["<<row<<"] -> "<< code<<endl;
code++;
}
logger << DEBUG << "Loaded "<<code<<" words from vocabulary" <<endl;
}
void ARPAPredictor::createARPATable()
{
std::ifstream arpaFile;
arpaFile.open(arpaFilename.c_str());
if(!arpaFile)
logger << ERROR << "Error opening ARPA model file: " << arpaFilename << endl;
assert(arpaFile);
std::string row;
int currOrder = 0;
unigramCount = 0;
bigramCount = 0;
trigramCount = 0;
int lineNum =0;
bool startData = false;
while(std::getline(arpaFile,row))
{
lineNum++;
if(row.empty())
continue;
if(row == "\\end\\")
break;
if(row == "\\data\\")
{
startData = true;
continue;
}
if( startData == true && currOrder == 0)
{
if( row.find("ngram 1")==0 )
{
unigramTot = atoi(row.substr(8).c_str());
logger << DEBUG << "tot unigram = "<<unigramTot<<endl;
continue;
}
if( row.find("ngram 2")==0)
{
bigramTot = atoi(row.substr(8).c_str());
logger << DEBUG << "tot bigram = "<<bigramTot<<endl;
continue;
}
if( row.find("ngram 3")==0)
{
trigramTot = atoi(row.substr(8).c_str());
logger << DEBUG << "tot trigram = "<<trigramTot<<endl;
continue;
}
}
if( row == "\\1-grams:" && startData)
{
currOrder = 1;
std::cerr << std::endl << "ARPA loading unigrams:" << std::endl;
unigramProg = new ProgressBar<char>(std::cerr);
continue;
}
if( row == "\\2-grams:" && startData)
{
currOrder = 2;
std::cerr << std::endl << std::endl << "ARPA loading bigrams:" << std::endl;
bigramProg = new ProgressBar<char>(std::cerr);
continue;
}
if( row == "\\3-grams:" && startData)
{
currOrder = 3;
std::cerr << std::endl << std::endl << "ARPA loading trigrams:" << std::endl;
trigramProg = new ProgressBar<char>(std::cerr);
continue;
}
if(currOrder == 0)
continue;
switch(currOrder)
{
case 1: addUnigram(row);
break;
case 2: addBigram(row);
break;
case 3: addTrigram(row);
break;
}
}
std::cerr << std::endl << std::endl;
logger << DEBUG << "loaded unigrams: "<< unigramCount << endl;
logger << DEBUG << "loaded bigrams: " << bigramCount << endl;
logger << DEBUG << "loaded trigrams: "<< trigramCount << endl;
}
void ARPAPredictor::addUnigram(std::string row)
{
std::stringstream str(row);
float logProb = 0;
float logAlfa = 0;
std::string wd1Str;
str >> logProb;
str >> wd1Str;
str >> logAlfa;
if(wd1Str != OOV )
{
int wd1 = vocabCode[wd1Str];
unigramMap[wd1]= ARPAData(logProb,logAlfa);
logger << DEBUG << "adding unigram ["<<wd1Str<< "] -> "<<logProb<<" "<<logAlfa<<endl;
}
unigramCount++;
unigramProg->update((float)unigramCount/(float)unigramTot);
}
void ARPAPredictor::addBigram(std::string row)
{
std::stringstream str(row);
float logProb = 0;
float logAlfa = 0;
std::string wd1Str;
std::string wd2Str;
str >> logProb;
str >> wd1Str;
str >> wd2Str;
str >> logAlfa;
if(wd1Str != OOV && wd2Str != OOV)
{
int wd1 = vocabCode[wd1Str];
int wd2 = vocabCode[wd2Str];
bigramMap[BigramKey(wd1,wd2)]=ARPAData(logProb,logAlfa);
logger << DEBUG << "adding bigram ["<<wd1Str<< "] ["<<wd2Str<< "] -> "<<logProb<<" "<<logAlfa<<endl;
}
bigramCount++;
bigramProg->update((float)bigramCount/(float)bigramTot);
}
void ARPAPredictor::addTrigram(std::string row)
{
std::stringstream str(row);
float logProb = 0;
std::string wd1Str;
std::string wd2Str;
std::string wd3Str;
str >> logProb;
str >> wd1Str;
str >> wd2Str;
str >> wd3Str;
if(wd1Str != OOV && wd2Str != OOV && wd3Str != OOV)
{
int wd1 = vocabCode[wd1Str];
int wd2 = vocabCode[wd2Str];
int wd3 = vocabCode[wd3Str];
trigramMap[TrigramKey(wd1,wd2,wd3)]=logProb;
logger << DEBUG << "adding trigram ["<<wd1Str<< "] ["<<wd2Str<< "] ["<<wd3Str<< "] -> "<<logProb <<endl;
}
trigramCount++;
trigramProg->update((float)trigramCount/(float)trigramTot);
}
ARPAPredictor::~ARPAPredictor()
{
delete unigramProg;
delete bigramProg;
delete trigramProg;
}
bool ARPAPredictor::matchesPrefixAndFilter(std::string word, std::string prefix, const char** filter ) const
{
if(filter == 0)
return word.find(prefix)==0;
for(int j = 0; filter[j] != 0; j++)
{
std::string pattern = prefix+std::string(filter[j]);
if(word.find(pattern)==0)
return true;
}
return false;
}
Prediction ARPAPredictor::predict(const size_t max_partial_prediction_size, const char** filter) const
{
logger << DEBUG << "predict()" << endl;
Prediction prediction;
int cardinality = 3;
std::vector<std::string> tokens(cardinality);
std::string prefix = Utility::strtolower(contextTracker->getToken(0));
std::string wd2Str = Utility::strtolower(contextTracker->getToken(1));
std::string wd1Str = Utility::strtolower(contextTracker->getToken(2));
std::multimap< float, std::string, cmp > result;
logger << DEBUG << "["<<wd1Str<<"]"<<" ["<<wd2Str<<"] "<<"["<<prefix<<"]"<<endl;
//search for the past tokens in the vocabulary
std::map<std::string,int>::const_iterator wd1It,wd2It;
wd1It = vocabCode.find(wd1Str);
wd2It = vocabCode.find(wd2Str);
//we have two valid past tokens available
if(wd1It!=vocabCode.end() && wd2It!=vocabCode.end())
{
//iterate over all vocab words
for(std::map<int,std::string>::const_iterator it = vocabDecode.begin(); it!=vocabDecode.end(); ++it) //cppcheck: Prefer prefix ++/-- operators for non-primitive types.
{
//if wd3 matches prefix and filter -> compute its backoff probability and add to the result set
if(matchesPrefixAndFilter(it->second,prefix,filter))
{
std::pair<const float,std::string> p (computeTrigramBackoff(wd1It->second,wd2It->second,it->first),
it->second);
result.insert(p);
}
}
}
//we have one valid past token available
else if(wd2It!=vocabCode.end())
{
//iterate over all vocab words
for(std::map<int,std::string>::const_iterator it = vocabDecode.begin(); it!=vocabDecode.end(); ++it)
{
//if wd3 matches prefix and filter -> compute its backoff probability and add to the result set
if(matchesPrefixAndFilter(it->second,prefix,filter))
{
std::pair<const float,std::string> p(computeBigramBackoff(wd2It->second,it->first),
it->second);
result.insert(p);
}
}
}
//we have no valid past token available
else
{
//iterate over all vocab words
for(std::map<int,std::string>::const_iterator it = vocabDecode.begin(); it!=vocabDecode.end(); ++it)
{
//if wd3 matches prefix and filter -> compute its backoff probability and add to the result set
if(matchesPrefixAndFilter(it->second,prefix,filter))
{
std::pair<const float,std::string> p (unigramMap.find(it->first)->second.logProb,
it->second);
result.insert(p);
}
}
}
size_t numSuggestions = 0;
for(std::multimap< float, std::string, cmp >::const_iterator it = result.begin();
it != result.end() && numSuggestions < max_partial_prediction_size;
++it)
{
prediction.addSuggestion(Suggestion(it->second,exp(it->first)));
numSuggestions++;
}
return prediction;
}
float ARPAPredictor::computeTrigramBackoff(int wd1,int wd2,int wd3) const
{
logger << DEBUG << "computing P( ["<<vocabDecode.find(wd3)->second<< "] | ["<<vocabDecode.find(wd1)->second<<"] ["<<vocabDecode.find(wd2)->second<<"] )"<<endl;
//trigram exist
std::map<TrigramKey,float>::const_iterator trigramIt =trigramMap.find(TrigramKey(wd1,wd2,wd3));
if(trigramIt!=trigramMap.end())
{
logger << DEBUG << "trigram ["<<vocabDecode.find(wd1)->second<< "] ["<<vocabDecode.find(wd2)->second<< "] ["<<vocabDecode.find(wd3)->second<< "] exists" <<endl;
logger << DEBUG << "returning "<<trigramIt->second <<endl;
return trigramIt->second;
}
//bigram exist
std::map<BigramKey,ARPAData>::const_iterator bigramIt =bigramMap.find(BigramKey(wd1,wd2));
if(bigramIt!=bigramMap.end())
{
logger << DEBUG << "bigram ["<<vocabDecode.find(wd1)->second<< "] ["<<vocabDecode.find(wd2)->second<< "] exists" <<endl;
float prob = bigramIt->second.logAlfa + computeBigramBackoff(wd2,wd3);
logger << DEBUG << "returning "<<prob<<endl;
return prob;
}
//else
logger << DEBUG << "no bigram w1,w2 exist" <<endl;
float prob = computeBigramBackoff(wd2,wd3);
logger << DEBUG << "returning "<<prob<<endl;
return prob;
}
float ARPAPredictor::computeBigramBackoff(int wd1, int wd2) const
{
//bigram exist
std::map<BigramKey,ARPAData>::const_iterator bigramIt =bigramMap.find(BigramKey(wd1,wd2));
if(bigramIt!=bigramMap.end())
return bigramIt->second.logProb;
//else
return unigramMap.find(wd1)->second.logAlfa +unigramMap.find(wd2)->second.logProb;
}
void ARPAPredictor::learn(const std::vector<std::string>& change)
{
logger << DEBUG << "learn() method called" << endl;
logger << DEBUG << "learn() method exited" << endl;
}
void ARPAPredictor::update (const Observable* var)
{
logger << DEBUG << "About to invoke dispatcher: " << var->get_name () << " - " << var->get_value() << endl;
dispatcher.dispatch (var);
}
ContextTracker::getToken
std::string getToken(const int) const
Definition: contextTracker.cpp:191
ARPAPredictor::computeTrigramBackoff
float computeTrigramBackoff(int, int, int) const
Definition: ARPAPredictor.cpp:409
ARPAPredictor::learn
virtual void learn(const std::vector< std::string > &change)
Definition: ARPAPredictor.cpp:455
ARPAPredictor::trigramProg
ProgressBar< char > * trigramProg
Definition: ARPAPredictor.h:165
ARPAPredictor::ARPAFILENAME
std::string ARPAFILENAME
Definition: ARPAPredictor.h:129
ARPAPredictor::trigramCount
int trigramCount
Definition: ARPAPredictor.h:157
ARPAPredictor::TIMEOUT
std::string TIMEOUT
Definition: ARPAPredictor.h:131
Suggestion
Definition: suggestion.h:49
ProgressBar::update
void update(const double percentage)
Definition: progress.h:72
ARPAPredictor::unigramTot
int unigramTot
Definition: ARPAPredictor.h:159
ARPAPredictor::timeout
int timeout
Definition: ARPAPredictor.h:135
ARPAPredictor::set_vocab_filename
void set_vocab_filename(const std::string &value)
Definition: ARPAPredictor.cpp:61
ARPAPredictor::VOCABFILENAME
std::string VOCABFILENAME
Definition: ARPAPredictor.h:130
ARPAPredictor::addUnigram
void addUnigram(std::string)
Definition: ARPAPredictor.cpp:214
ARPAData
Definition: ARPAPredictor.h:44
ARPAPredictor::bigramCount
int bigramCount
Definition: ARPAPredictor.h:156
ARPAPredictor::~ARPAPredictor
~ARPAPredictor()
Definition: ARPAPredictor.cpp:298
Observable::get_name
virtual std::string get_name() const =0
Prediction
Definition: prediction.h:46
Dispatcher::map
void map(Observable *var, const mbr_func_ptr_t &ptr)
Definition: dispatcher.h:80
ARPAPredictor::unigramCount
int unigramCount
Definition: ARPAPredictor.h:155
Predictor::set_logger
virtual void set_logger(const std::string &level)
Definition: predictor.cpp:87
Predictor::name
const std::string name
Definition: predictor.h:95
Predictor
Definition: predictor.h:45
Predictor::contextTracker
ContextTracker * contextTracker
Definition: predictor.h:101
ARPAPredictor::vocabCode
std::map< std::string, int > vocabCode
Definition: ARPAPredictor.h:137
ARPAPredictor::dispatcher
Dispatcher< ARPAPredictor > dispatcher
Definition: ARPAPredictor.h:167
ContextTracker
Tracks user interaction and context.
Definition: contextTracker.h:154
config
std::string config
Definition: presageDemo.cpp:69
Observable::get_value
virtual std::string get_value() const =0
Prediction::addSuggestion
void addSuggestion(Suggestion)
Definition: prediction.cpp:89
ARPAPredictor::update
virtual void update(const Observable *variable)
Definition: ARPAPredictor.cpp:461
ARPAPredictor::matchesPrefixAndFilter
bool matchesPrefixAndFilter(std::string, std::string, const char **) const
Definition: ARPAPredictor.cpp:305
ARPAPredictor::trigramMap
std::map< TrigramKey, float > trigramMap
Definition: ARPAPredictor.h:142
Dispatcher::dispatch
void dispatch(const Observable *var)
Definition: dispatcher.h:91
ARPAPredictor::predict
virtual Prediction predict(const size_t size, const char **filter) const
Generate prediction.
Definition: ARPAPredictor.cpp:320
ARPAPredictor::computeBigramBackoff
float computeBigramBackoff(int, int) const
Definition: ARPAPredictor.cpp:443
ARPAPredictor::unigramMap
std::map< int, ARPAData > unigramMap
Definition: ARPAPredictor.h:140
ARPAPredictor::vocabFilename
std::string vocabFilename
Definition: ARPAPredictor.h:134
ARPAPredictor::addBigram
void addBigram(std::string)
Definition: ARPAPredictor.cpp:241
ARPAPredictor::addTrigram
void addTrigram(std::string)
Definition: ARPAPredictor.cpp:268
endl
const Logger< _charT, _Traits > & endl(const Logger< _charT, _Traits > &lgr)
Definition: logger.h:277
ARPAPredictor::bigramMap
std::map< BigramKey, ARPAData > bigramMap
Definition: ARPAPredictor.h:141
TrigramKey
Definition: ARPAPredictor.h:53
ARPAPredictor::createARPATable
void createARPATable()
Definition: ARPAPredictor.cpp:106
Utility::strtolower
static char * strtolower(char *)
Definition: utility.cpp:41
ProgressBar< char >
ARPAPredictor::arpaFilename
std::string arpaFilename
Definition: ARPAPredictor.h:133
Predictor::PREDICTORS
const std::string PREDICTORS
Definition: predictor.h:99
ARPAPredictor::loadVocabulary
void loadVocabulary()
Definition: ARPAPredictor.cpp:79
Configuration
Definition: configuration.h:35
ARPAPredictor::set_timeout
void set_timeout(const std::string &value)
Definition: ARPAPredictor.cpp:73
ARPAPredictor::LOGGER
std::string LOGGER
Definition: ARPAPredictor.h:128
BigramKey
Definition: ARPAPredictor.h:83
ARPAPredictor::unigramProg
ProgressBar< char > * unigramProg
Definition: ARPAPredictor.h:163
ARPAPredictor::ARPAPredictor
ARPAPredictor(Configuration *, ContextTracker *, const char *)
Definition: ARPAPredictor.cpp:37
Observable
Definition: observable.h:36
ARPAPredictor::vocabDecode
std::map< int, std::string > vocabDecode
Definition: ARPAPredictor.h:138
Predictor::logger
Logger< char > logger
Definition: predictor.h:105
ARPAPredictor::bigramTot
int bigramTot
Definition: ARPAPredictor.h:160
ARPAPredictor::bigramProg
ProgressBar< char > * bigramProg
Definition: ARPAPredictor.h:164
ARPAPredictor::trigramTot
int trigramTot
Definition: ARPAPredictor.h:161
ARPAPredictor.h
OOV
#define OOV
Definition: ARPAPredictor.cpp:33
ARPAPredictor::set_arpa_filename
void set_arpa_filename(const std::string &value)
Definition: ARPAPredictor.cpp:67