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

with Ada.Text_IO;
 
procedure Move_To_Front is 
 
   subtype Lower_Case is Character range 'a' .. 'z';
   subtype Index is Integer range 0 .. 25;
   type Table is array (Index) of Lower_Case;
   Alphabet: constant Table := "abcdefghijklmnopqrstuvwxyz";
   type Number_String is array(Positive range <>) of Natural;
 
   function Encode(S: String) return Number_String is
      Key: Table := Alphabet;
 
      function Encode(S: String; Tab: in out Table) return Number_String is
 
	 procedure Look_Up(A: in out Table; Ch: Lower_Case; Pos: out Index) is  
	 begin
	    for I in A'Range loop
	       if A(I) = Ch then 
		  Pos := I;
		  A := A(Pos) & A(A'First .. Pos-1) & A(Pos+1 .. A'Last);
		  return;
	       end if;
	    end loop;
	    raise Program_Error with "unknown character";
	 end Look_Up;
 
	 Empty: Number_String(1 .. 0);
	 Result: Natural;   
      begin
	 if S'Length = 0 then 
	    return Empty;
	 else
	    Look_Up(Tab, S(S'First), Result);
	    return Result & Encode(S(S'First+1 .. S'Last), Tab);
	 end if;
      end Encode;
 
   begin
      return Encode(S, Key);
   end Encode;
 
   function Decode(N: Number_String) return String is
      Key: Table := Alphabet;
 
      function Decode(N: Number_String; Tab: in out Table) return String is
 
	 procedure Look_Up(A: in out Table; Pos: Index; Ch: out Lower_Case) is  
	 begin
	    Ch := A(Pos);
	    A := A(Pos) & A(A'First .. Pos-1) & A(Pos+1 .. A'Last);
	 end Look_Up;
 
	 Result: String(N'Range);
      begin
	 for I in N'Range loop
	    Look_Up(Tab, N(I), Result(I));
	 end loop;
	 return Result;
      end Decode;
 
   begin
      return Decode(N, Key);
   end Decode;
 
   procedure Encode_Write_Check(S: String) is
      N: Number_String := Encode(S);
      T: String := Decode(N);
      Check: String := (if S=T then "Correct!" else "*WRONG*!");
   begin
      Ada.Text_IO.Put("'" & S & "' encodes to");
      for Num of N loop
	 Ada.Text_IO.Put(Integer'Image(Num));
      end loop;
      Ada.Text_IO.Put_Line(". This decodes to '" & T & "'. " & Check);
   end Encode_Write_Check;
 
begin
   Encode_Write_Check("broood");
   Encode_Write_Check("bananaaa");
   Encode_Write_Check("hiphophiphop");
end Move_To_Front;