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

 
Module CheckIt {
      Global All$, nl$
      \\ upgrade to document
      Document All$
      Nl$<={
      }
      Function Encode$(Inp$) {
           Def SymbolTable$="abcdefghijklmnopqrstuvwxyz", Out$=""
            For i=1 to Len(Inp$)
                  c$=Mid$(Inp$, i, 1)
                  k=Instr(SymbolTable$, c$)
                  Insert k, 1 SymbolTable$=""
                  Out$=If$(Out$="" -> Quote$(k-1),Quote$(Param(Out$), k-1))
                  Insert 1 SymbolTable$=c$
                  \\ we use <= for globals
                  All$<=Format$("   {0} {1:30} {2}", c$, Out$, SymbolTable$)+nl$
            Next i
            =Out$
      }
      Function Decode$(Inp$) {
           Def SymbolTable$="abcdefghijklmnopqrstuvwxyz", Out$=""
           flush
           Data Param(Inp$)
           While not empty {
                  k=Number+1
                  c$=Mid$(SymbolTable$, k, 1)
                  Out$+=c$
                  Insert k, 1 SymbolTable$=""  ' erase at position k
                  Insert 1 SymbolTable$=c$
                  All$<=Format$("{0::-2} {1} {2:30} {3}", k-1, c$, Out$, SymbolTable$)+nl$
            }
            =Out$
      }
      TryThis("broood")
      TryThis("bananaaa")
      TryThis("hiphophiphop")
      ClipBoard All$
      Sub TryThis(a$)
            Local Out$=Encode$(a$)
            Local final$=Decode$(Out$)
            Print final$, final$=a$
      End Sub
}
CheckIt
 