Definition(s)

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

Taken from http://rosettacode.org

Algorithm(s)



In [8]:

    
import string
import copy

SYMBOL_TABLE = list(string.ascii_lowercase)



In [9]:

    
def move2front_encode(text, symboltable):
    encoded_text, symbol_table = [], copy.deepcopy(symboltable)
    
    for e in text:
        ind = symbol_table.index(e)
        encoded_text.append(ind)
        symbol_table.pop(ind)
        symbol_table.insert(0, e)
        
    return encoded_text



In [10]:

    
def move2front_decode(text, symboltable):
    decoded_text, symbol_table = [], copy.deepcopy(symboltable)
    
    for ind in text:
        ch = symbol_table[ind]
        symbol_table.pop(ind)
        symbol_table.insert(0, ch)
        decoded_text.append(ch)
        
    return ''.join(decoded_text)

Run(s)



In [11]:

    
print(move2front_encode('bananaaa', SYMBOL_TABLE))









    



[1, 1, 13, 1, 1, 1, 0, 0]



In [12]:

    
print(move2front_decode([1, 1, 13, 1, 1, 1, 0, 0], SYMBOL_TABLE))









    



bananaaa



In [13]:

    
print(move2front_encode('broood', SYMBOL_TABLE))









    



[1, 17, 15, 0, 0, 5]



In [14]:

    
print(move2front_decode([1, 17, 15, 0, 0, 5], SYMBOL_TABLE))









    



broood