Move-to-front algorithm

Move-to-front algorithm
You are encouraged to solve this task according to the task description, using any language you may know.

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).

D

<lang d>import std.stdio, std.string, std.ascii, std.algorithm;

ptrdiff_t[] mtfEncoder(in string data) pure nothrow @safe in {

   assert(data.countchars("a-z") == data.length);

} out(result) {

   assert(result.length == data.length);
   assert(result.all!(e => e >= 0 && e < lowercase.length));

} body {

   ubyte[lowercase.length] order = lowercase.representation;
   auto encoded = new typeof(return)(data.length);

   size_t i = 0;
   foreach (immutable b; data) {
       immutable j = encoded[i++] = order[].countUntil(b);
       bringToFront(order[0 .. j], order[j .. j + 1]);
   }

   return encoded;

}

string mtfDecoder(in ptrdiff_t[] encoded) pure nothrow @safe in {

   assert(encoded.all!(e => e >= 0 && e < lowercase.length));

} out(result) {

   assert(result.length == encoded.length);
   assert(result.countchars("a-z") == result.length);

} body {

   ubyte[lowercase.length] order = lowercase.representation;
   auto decoded = new char[encoded.length];

   size_t i = 0;
   foreach (immutable code; encoded) {
       decoded[i++] = order[code];
       bringToFront(order[0 .. code], order[code .. code + 1]);
   }

   return decoded;

}

void main() {

   foreach (immutable word; ["broood", "bananaaa", "hiphophiphop"]) {
       immutable encoded = word.mtfEncoder;
       immutable decoded = encoded.mtfDecoder;
       writefln("'%s' encodes to %s, which decodes back to '%s'",
                word, encoded, decoded);
       assert(word == decoded);
   }

}</lang>

Output:

'broood' encodes to [1, 17, 15, 0, 0, 5], which decodes back to 'broood'
'bananaaa' encodes to [1, 1, 13, 1, 1, 1, 0, 0], which decodes back to 'bananaaa'
'hiphophiphop' encodes to [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2], which decodes back to 'hiphophiphop'

Go

Translation of: Python

<lang go>package main

import (

   "bytes"
   "fmt"

)

type moveToFront string

func (symbols moveToFront) encode(s string) []int {

   seq := make([]int, len(s))
   pad := []byte(symbols)
   c1 := []byte{0}
   for i := 0; i < len(s); i++ {
       c := s[i]
       c1[0] = c
       x := bytes.Index(pad, c1)
       seq[i] = x
       copy(pad[1:], pad[:x])
       pad[0] = c
   }
   return seq

} func (symbols moveToFront) decode(seq []int) string {

   chars := make([]byte, len(seq))
   pad := []byte(symbols)
   for i, x := range seq {
       c := pad[x]
       chars[i] = c
       copy(pad[1:], pad[:x])
       pad[0] = c
   }
   return string(chars)

}

func main() {

   m := moveToFront("abcdefghijklmnopqrstuvwxyz")
   for _, s := range []string{"broood", "bananaaa", "hiphophiphop"} {
       enc := m.encode(s)
       dec := m.decode(enc)
       fmt.Println(s, enc, dec)
       if dec != s {
           panic("Whoops!")
       }
   }

}</lang>

Output:

broood [1 17 15 0 0 5] broood
bananaaa [1 1 13 1 1 1 0 0] bananaaa
hiphophiphop [7 8 15 2 15 2 2 3 2 2 3 2] hiphophiphop

J

<lang J>spindizzy=:3 :0

 'seq table'=. y
 ndx=.$0
 orig=. table
 for_sym. seq do.
   ndx=.ndx,table i.sym
   table=. sym,table-.sym
 end.
 ndx
 assert. seq-:yzzidnips ndx;orig

)

yzzidnips=:3 :0

 'ndx table'=. y
 seq=.
 for_n. ndx do.
   seq=.seq,sym=. n{table
   table=. sym,table-.sym
 end.
 seq

)</lang>

Required examples:

<lang J> spindizzy 'broood';'abcdefghijklmnopqrstuvwxyz' 1 17 15 0 0 5

  spindizzy 'bananaaa';'abcdefghijklmnopqrstuvwxyz'

1 1 13 1 1 1 0 0

  spindizzy 'hiphophiphop';'abcdefghijklmnopqrstuvwxyz'

7 8 15 2 15 2 2 3 2 2 3 2</lang>

It's not clear, though, why anyone would think that this is any better than lookups against an unmodified symbol table.

PL/I

<lang pl/i>*process source attributes xref or(!);

/*********************************************************************
* 25.5.2014 Walter Pachl translated from REXX
*********************************************************************/
ed: Proc Options(main);
Call enc_dec('broood');
Call enc_dec('bananaaa');
Call enc_dec('hiphophiphop');

enc_dec: Proc(in);
Dcl in  Char(*);
Dcl out Char(20) Var Init();
Dcl st Char(26) Init('abcdefghijklmnopqrstuvwxyz');
Dcl sta Char(26) Init((st));
Dcl enc(20) Bin Fixed(31);
Dcl encn Bin Fixed(31) Init(0);
Dcl (i,p.k) Bin Fixed(31);
Dcl c       Char(1);
Do i=1 To length(in);
  c=substr(in,i,1);
  p=index(st,c);
  encn+=1;
  enc(encn)=p-1;
  st=c!!left(st,p-1)!!substr(st,p+1);
  End;
Put Skip List(' in='!!in);
Put Skip List('sta='!!sta!!' original symbol table');
Put Skip Edit('enc=',(enc(i) do i=1 To encn))(a,20(F(3)));
Put Skip List(' st='!!st!!' symbol table after encoding');
Do i=1 To encn;
  k=enc(i)+1;
  out=out!!substr(sta,k,1);
  sta=substr(sta,k,1)!!left(sta,k-1)!!substr(sta,k+1);
  End;
Put Skip List('out='!!out);
Put Skip List(' ');
If out=in Then;
Else
  Put Skip List('all wrong!!');
End;</lang>

Output:

 in=broood
sta=abcdefghijklmnopqrstuvwxyz original symbol table
enc=  1 17 15  0  0  5
 st=dorbacefghijklmnpqstuvwxyz symbol table after encoding
out=broood

 in=bananaaa
sta=abcdefghijklmnopqrstuvwxyz original symbol table
enc=  1  1 13  1  1  1  0  0
 st=anbcdefghijklmopqrstuvwxyz symbol table after encoding
out=bananaaa

 in=hiphophiphop
sta=abcdefghijklmnopqrstuvwxyz original symbol table
enc=  7  8 15  2 15  2  2  3  2  2  3  2
 st=pohiabcdefgjklmnqrstuvwxyz symbol table after encoding
out=hiphophiphop

Python

<lang python>from __future__ import print_function from string import ascii_lowercase

SYMBOLTABLE = list(ascii_lowercase)

def move2front_encode(strng, symboltable):

   sequence, pad = [], symboltable[::]
   for char in strng:
       indx = pad.index(char)
       sequence.append(indx)
       pad = [pad.pop(indx)] + pad
   return sequence

def move2front_decode(sequence, symboltable):

   chars, pad = [], symboltable[::]
   for indx in sequence:
       char = pad[indx]
       chars.append(char)
       pad = [pad.pop(indx)] + pad
   return .join(chars)

if __name__ == '__main__':

   for s in ['broood', 'bananaaa', 'hiphophiphop']:
       encode = move2front_encode(s, SYMBOLTABLE)
       print('%14r encodes to %r' % (s, encode), end=', ')
       decode = move2front_decode(encode, SYMBOLTABLE)
       print('which decodes back to %r' % decode)
       assert s == decode, 'Whoops!'</lang>

Output:

      'broood' encodes to [1, 17, 15, 0, 0, 5], which decodes back to 'broood'
    'bananaaa' encodes to [1, 1, 13, 1, 1, 1, 0, 0], which decodes back to 'bananaaa'
'hiphophiphop' encodes to [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2], which decodes back to 'hiphophiphop'

REXX

<lang rexx>/* REXX ***************************************************************

• 25.05.2014 Walter Pachl
• REXX strings start with position 1
  • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • /

Call enc_dec 'broood' Call enc_dec 'bananaaa' Call enc_dec 'hiphophiphop' Exit enc_dec: Procedure Parse Arg in st='abcdefghijklmnopqrstuvwxyz' sta=st /* remember this for decoding */ enc= Do i=1 To length(in)

 c=substr(in,i,1)
 p=pos(c,st)
 enc=enc (p-1)
 st=c||left(st,p-1)substr(st,p+1)
 End

Say ' in='in Say 'sta='sta 'original symbol table' Say 'enc='enc Say ' st='st 'symbol table after encoding' out= Do i=1 To words(enc)

 k=word(enc,i)+1
 out=out||substr(sta,k,1)
 sta=substr(sta,k,1)left(sta,k-1)substr(sta,k+1)
 End

Say 'out='out Say ' ' If out==in Then Nop Else

 Say 'all wrong!!'

Return </lang>

Output:

 in=brood
sta=abcdefghijklmnopqrstuvwxyz original symbol table
enc= 1 17 15 0 0 5
 st=dorbacefghijklmnpqstuvwxyz symbol table after encoding
out=brood

 in=bananaaa
sta=abcdefghijklmnopqrstuvwxyz original symbol table
enc= 1 1 13 1 1 1 0 0
 st=anbcdefghijklmopqrstuvwxyz symbol table after encoding
out=bananaaa

 in=hiphophiphop
sta=abcdefghijklmnopqrstuvwxyz original symbol table
enc= 7 8 15 2 15 2 2 3 2 2 3 2
 st=pohiabcdefgjklmnqrstuvwxyz symbol table after encoding
out=hiphophiphop