newsgroups-index (beta)

Simple prediction

Daniel_Lidström

From:	Daniel_Lidström
Subject:	Simple prediction
Date:	Fri, 21 Jan 2005 23:37:49 +0100

Hello

here's a program that can do simple prediction (prediction by partial
match). For example, the prediction string `sbbssmsmsassbbs' is the
encoding of some action and the next action is to be guessed, based on the
previous pattern. In this case the program predicts the following:

Enter string for prediction: sbbssmsmsassbbs
a 10%
b 20%
m 20%
s 50%

Next action is very likely `s'. I used this to predict an opponent's
actions in an online gladiator game. Have fun with it!

// Finite Context Model prediction.
// See http://www.cbloom.com/algs/markov.html
// Predict the next character by looking at previous
// character sequences.
// If no previous sequence matches current sequence,
// character is predicted based on the number of
// occurrences.

#include
#include
#include
#include
#include

using namespace std;

int main()
{

while( true ) {

string text;
cout << "Enter string for prediction: "; cin >> text;

typedef map< string, map > Dictionary;
Dictionary sums;

// calculate sums
for( string::iterator it=text.begin(); it!=text.end()-1; ++it ) {

for( string::iterator jt=it+1; jt!=text.end(); ++jt ) {
// construct substring:
stringstream stream;
for( string::iterator kt=it; kt!=jt; ++kt )
stream << *kt;
sums[stream.str()][*jt] ++;
}

}

//! try to match last characters in text to previous
//! characters in text
//! fill prediction with character prediction
map prediction;
int total_sum = 0; //! used to count predictions
for( int i=text.size()-1; i>=0; --i ) { // from last to first
// create substring
string last(text, i, string::npos);
Dictionary::iterator It = sums.find(last);
if( It!=sums.end() ) {
//cout << last << " exists somewhere in " << text << endl;
//! update character counts
for( std::map::iterator jt=It->second.begin(); jt!=It->second.end(); ++jt ) {
prediction[jt->first] += jt->second;
total_sum += jt->second;
}
}
else break;
}

if( prediction.empty() ) { //! show prediction just by chance of character (num/total)
total_sum = text.size();
for( string::iterator it=text.begin(); it!=text.end(); ++it )
prediction[*it] ++;
}

//! show prediction
for( std::map::iterator it=prediction.begin(); it!=prediction.end(); ++it )
cout << it->first << ' ' << setprecision(0) << fixed << double(it->second*100)/total_sum << '%' << endl;
}

return 0;
}

--
Daniel