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

``````