fbpx

C++: Move-To-Front Algorithm

Bjarne-stroustrup
 


Given a symbol table of a zero-indexed array of all possible input symbols this algorithm reversibly transforms a sequence of input symbols into an array of output numbers (indices).
The transform in many cases acts to give frequently repeated input symbols lower indices which is useful in some compression algorithms.

Encoding algorithm
    for each symbol of the input sequence:
        output the index of the symbol in the symbol table
        move that symbol to the front of the symbol table
Decoding algorithm
    # Using the same starting symbol table
    for each index of the input sequence:
        output the symbol at that index of the symbol table
        move that symbol to the front of the symbol table
Example

Encoding the string of character symbols ‘broood’ using a symbol table of the characters ‘a’-to-‘z’

Input Output SymbolTable
broood 1 ‘abcdefghijklmnopqrstuvwxyz’
broood 1 17 ‘bacdefghijklmnopqrstuvwxyz’
broood 1 17 15 ‘rbacdefghijklmnopqstuvwxyz’
broood 1 17 15 0 ‘orbacdefghijklmnpqstuvwxyz’
broood 1 17 15 0 0 ‘orbacdefghijklmnpqstuvwxyz’
broood 1 17 15 0 0 5 ‘orbacdefghijklmnpqstuvwxyz’

Decoding the indices back to the original symbol order:

Input Output SymbolTable
1 17 15 0 0 5 b ‘abcdefghijklmnopqrstuvwxyz’
1 17 15 0 0 5 br ‘bacdefghijklmnopqrstuvwxyz’
1 17 15 0 0 5 bro ‘rbacdefghijklmnopqstuvwxyz’
1 17 15 0 0 5 broo ‘orbacdefghijklmnpqstuvwxyz’
1 17 15 0 0 5 brooo ‘orbacdefghijklmnpqstuvwxyz’
1 17 15 0 0 5 broood ‘orbacdefghijklmnpqstuvwxyz’
Task
  • Encode and decode the following three strings of characters using the symbol table of the characters ‘a’-to-‘z’ as above.
  • Show the strings and their encoding here.
  • Add a check to ensure that the decoded string is the same as the original.

The strings are: ‘broood’, ‘bananaaa’, and ‘hiphophiphop’. (Note the spellings).

#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>

using namespace std;

class MTF
{
public:
	string encode( string str )
	{
		fillSymbolTable();
		vector<int> output;
		for( string::iterator it = str.begin(); it != str.end(); it++ )
		{
			for( int i = 0; i < 26; i++ )
			{
				if( *it == symbolTable[i] )
				{
					output.push_back( i );
					moveToFront( i );
					break;
				}
			}
		}
		string r;
		for( vector<int>::iterator it = output.begin(); it != output.end(); it++ )
		{
			ostringstream ss;
			ss << *it;
			r += ss.str() + " ";
		}
		return r;
	}

	string decode( string str )
	{
		fillSymbolTable();
		istringstream iss( str ); vector<int> output;
		copy( istream_iterator<int>( iss ), istream_iterator<int>(), back_inserter<vector<int> >( output ) );
		string r;
		for( vector<int>::iterator it = output.begin(); it != output.end(); it++ )
		{
			r.append( 1, symbolTable[*it] );
			moveToFront( *it );
		}
		return r;
	}

private:
	void moveToFront( int i )
	{
		char t = symbolTable[i];
		for( int z = i - 1; z >= 0; z-- )
		symbolTable[z + 1] = symbolTable[z];

		symbolTable[0] = t;
	}

	void fillSymbolTable()
	{
		for( int x = 0; x < 26; x++ )
		symbolTable[x] = x + 'a';
	}

	char symbolTable[26];
};

int main()
{
	MTF mtf;
	string a, str[] = { "broood", "bananaaa", "hiphophiphop" };
	for( int x = 0; x < 3; x++ )
	{
		a = str[x];
		cout << a << " -> encoded = ";
		a = mtf.encode( a );
		cout << a << "; decoded = " << mtf.decode( a ) << endl;
	}
	return 0;
}
Output:
broood -> encoded = 1 17 15 0 0 5 ; decoded = broood
bananaaa -> encoded = 1 1 13 1 1 1 0 0 ; decoded = bananaaa
hiphophiphop -> encoded = 7 8 15 2 15 2 2 3 2 2 3 2 ; decoded = hiphophiphop

SOURCE

Content is available under GNU Free Documentation License 1.2.