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 lowercase 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 lowercase 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     
   hiphophiphop  


(Note the misspellings in the above strings.)

#define FAIL -1
 
sub mtf( s() as string, i as uinteger )
    'moves the symbol at index i to the front and shifts preceding ones back
    dim as string*1 t = s(i)
    for j as uinteger = i to 1 step -1
        s(j) = s(j-1)
    next j
    s(0)=t
end sub
 
sub make_symbols( s() as string )
    'populates an array of strings with the lowercase alphabet
    for i as uinteger = 97 to 122
        s(i-97) = chr(i)
    next i
end sub
 
function find( s() as string, l as string ) as integer
    'returns the index of the first occurrence of the symbol l in s()
    for i as uinteger = 0 to ubound(s)
        if s(i) = l then return i
    next i
    return FAIL
end function
 
sub encode( s() as string, ind() as uinteger )
    dim as integer n = ubound(s), i
    redim as uinteger ind(0 to n)
    dim as string a(0 to 25)
    make_symbols(a())
    for z as uinteger = 0 to n
        i = find( a(), s(z) )
        if i = FAIL then
            print "Uh oh! Couldn't find ";s(z);" in alphabet."
            end
        end if
        mtf( a(), i )
        ind(z) = i
    next z
end sub
 
sub decode( s() as string, ind() as uinteger )
    dim as integer n = ubound(ind), i
    redim as string s(0 to n)
    dim as string a(0 to 25)
    make_symbols(a())
    for z as uinteger = 0 to n
        s(z) = a(ind(z))
        mtf(a(), ind(z))
    next z
end sub
 
sub printarr( s() as string )
    for i as uinteger = 0 to ubound(s)
        print s(i);
    next i
    print
end sub
 
sub printind( ind() as integer )
    for i as uinteger = 0 to ubound(ind)
        print ind(i);" ";
    next i
    print
end sub
 
sub compose( s() as string, b as string )
    'turns a string into a zero-indexed array of single letters
    'The reason we use such arrays is to get them zero-indexed
    'and to make the point that we could work with multi-char
    'symbol tables if we wanted to
    dim as integer n = len(b), i
    redim as string s(0 to n-1)
    for i = 0 to n-1
        s(i) = mid(b, 1+i, 1)
    next i
end sub
 
'-----------now the tests-------------
redim as string s(0)
redim as integer ind(0)
 
compose( s(), "broood" )
encode( s(), ind() )
printind( ind() )
decode( s(), ind() )
printarr( s() ) : print
 
compose( s(), "bananaaa" )
encode( s(), ind() )
printind( ind() )
decode( s(), ind() )
printarr( s() ) : print
 
compose( s(), "hiphophiphop" )
encode( s(), ind() )
printind( ind() )
decode( s(), ind() )
printarr( s() )