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
Content is available under GNU Free Documentation License 1.2.