Move-to-front algorithm
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).
You are encouraged to solve this task according to the task description, using any language you may know.
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.)
V symboltable = Array(‘a’..‘z’)
F move2front_encode(strng)
[Int] sequence
V pad = copy(:symboltable)
L(char) strng
V indx = pad.index(char)
sequence.append(indx)
pad = [pad.pop(indx)] [+] pad
R sequence
F move2front_decode(sequence)
[Char] chars
V pad = copy(:symboltable)
L(indx) sequence
V char = pad[indx]
chars.append(char)
pad = [pad.pop(indx)] [+] pad
R chars.join(‘’)
L(s) [‘broood’, ‘bananaaa’, ‘hiphophiphop’]
V encode = move2front_encode(s)
print(‘#14 encodes to #.’.format(s, encode), end' ‘, ’)
V decode = move2front_decode(encode)
print(‘which decodes back to #.’.format(decode))
assert(s == decode, ‘Whoops!’)- 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
DEFINE SYMBOL_TABLE_SIZE="26"
PROC InitSymbolTable(BYTE ARRAY table BYTE len)
BYTE i
FOR i=0 TO len-1
DO
table(i)=i+'a
OD
RETURN
BYTE FUNC Find(BYTE ARRAY table BYTE len,c)
BYTE i
FOR i=0 TO len-1
DO
IF table(i)=c THEN
RETURN (i)
FI
OD
Break()
RETURN (0)
PROC MoveToFront(BYTE ARRAY table BYTE len,pos)
BYTE sym
sym=table(pos)
WHILE pos>0
DO
table(pos)=table(pos-1)
pos==-1
OD
table(pos)=sym
RETURN
PROC Encode(CHAR ARRAY in BYTE ARRAY out BYTE POINTER outLen)
BYTE ARRAY table(SYMBOL_TABLE_SIZE)
BYTE i,pos
outLen^=0
InitSymbolTable(table,SYMBOL_TABLE_SIZE)
FOR i=1 TO in(0)
DO
pos=Find(table,SYMBOL_TABLE_SIZE,in(i))
out(outLen^)=pos
outLen^==+1
MoveToFront(table,SYMBOL_TABLE_SIZE,pos)
OD
RETURN
PROC Decode(BYTE ARRAY in BYTE inLen CHAR ARRAY out)
BYTE ARRAY table(SYMBOL_TABLE_SIZE)
BYTE i,pos,len
len=0
InitSymbolTable(table,SYMBOL_TABLE_SIZE)
FOR i=0 TO inLen-1
DO
pos=in(i)
len==+1
out(len)=table(pos)
MoveToFront(table,SYMBOL_TABLE_SIZE,pos)
OD
out(0)=len
RETURN
PROC Test(CHAR ARRAY s)
BYTE ARRAY encoded(255)
CHAR ARRAY decoded(256)
BYTE encodedLength,i
Print("Source: ")
PrintE(s)
Encode(s,encoded,@encodedLength)
Print("Encoded: ")
FOR i=0 TO encodedLength-1
DO
PrintB(encoded(i)) Put(32)
OD
PutE()
Decode(encoded,encodedLength,decoded)
Print("Decoded: ")
PrintE(decoded)
IF SCompare(s,decoded)=0 THEN
PrintE("Decoded is equal to the source.")
ELSE
PrintE("Decoded is different from the source!")
FI
PutE()
RETURN
PROC Main()
Test("broood")
Test("bananaaa")
Test("hiphophiphop")
RETURN- Output:
Screenshot from Atari 8-bit computer
Source: broood Encoded: 1 17 15 0 0 5 Decoded: broood Decoded is equal to the source. Source: bananaaa Encoded: 1 1 13 1 1 1 0 0 Decoded: bananaaa Decoded is equal to the source. Source: hiphophiphop Encoded: 7 8 15 2 15 2 2 3 2 2 3 2 Decoded: hiphophiphop Decoded is equal to the source.
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;
- Output:
'broood' encodes to 1 17 15 0 0 5. This decodes to 'broood'. Correct! 'bananaaa' encodes to 1 1 13 1 1 1 0 0. This decodes to 'bananaaa'. Correct! 'hiphophiphop' encodes to 7 8 15 2 15 2 2 3 2 2 3 2. This decodes to 'hiphophiphop'. Correct!
decode(list l)
{
integer c, e;
data al, s;
al = "abcdefghijklmnopqrstuvwxyz";
for (, e in l) {
s.append(c = al[e]);
al.delete(e).insert(0, c);
}
s;
}
encode(data s)
{
integer c, e;
data al;
list l;
al = "abcdefghijklmnopqrstuvwxyz";
for (, c in s) {
l.append(e = al.place(c));
al.delete(e).insert(0, c);
}
l;
}
main(void)
{
for (, text s in list("broood", "bananaaa", "hiphophiphop")) {
list l;
l = encode(s);
l.ucall(o_, 1, " ");
o_(": ", decode(l), "\n");
}
0;
}- Output:
1 17 15 0 0 5: broood 1 1 13 1 1 1 0 0: bananaaa 7 8 15 2 15 2 2 3 2 2 3 2: hiphophiphop
# move the character at text pos to the front of text #
# note text pos is based from 0 #
PROC move to front = ( STRING text, INT text pos )STRING:
IF text pos < 1
THEN
# the character is already at the front (or not in the string) #
text
ELSE
# the character isn't already at the front - construct the new string #
INT char pos = LWB text + text pos;
( text[ char pos : char pos ]
+ text[ : char pos - 1 ]
+ text[ char pos + 1 : ]
)
FI;
# encode the string "text", using "initial table" as the starting symbol table#
PROC encode = ( STRING text, STRING initial table )[]INT:
BEGIN
[ 1 : ( UPB text - LWB text ) + 1 ]INT result;
STRING symbol table := initial table;
FOR text pos FROM LWB text TO UPB text
DO
INT symbol pos := 0;
result[ text pos ]
:= IF char in string( text[ text pos ], symbol pos, symbol table )
THEN
# the character is in the symbol table at symbol pos #
# (indexed from LWB text) - we store the positions #
# indexed from 0 #
symbol pos - LWB text
ELSE
# the character isn't in the symbol table #
-1
FI;
# modify the symbol table so the latest character is at the front #
symbol table := move to front( symbol table, result[ text pos ] )
OD;
result
END; # encode #
# decode "encoded", using "initial table" as the starting symbol table #
PROC decode = ( []INT encoded, STRING initial table )STRING:
BEGIN
STRING result := "";
STRING symbol table := initial table;
FOR text pos FROM LWB encoded TO UPB encoded
DO
result
+:= IF encoded[ text pos ] < 0
THEN
# the encoded character wasn't in the string #
"?"
ELSE
# the character is in the symbol table #
symbol table[ encoded[ text pos ] + LWB symbol table ]
FI;
# modify the symbol table so the latest character is at the front #
symbol table := move to front( symbol table, encoded[ text pos ] )
OD;
result
END; # decode #
# routine to test the encode and decode routines #
PROC test encode and decode = ( STRING text )VOID:
BEGIN
# initial value for the symbol table #
[]CHAR initial table = "abcdefghijklmnopqrstuvwxyz";
# procedure to format the encoded value #
PROC format encoded value = ( []INT values )STRING:
BEGIN
STRING result := "";
FOR value pos FROM LWB values TO UPB values
DO
result +:= ( " " + whole( values[ value pos ], 0 ) )
OD;
result
END; # format encoded value #
[]INT encoded = encode( text, initial table );
STRING decoded = decode( encoded, initial table );
print( ( ( text
+ " encodes to ["
+ format encoded value( encoded )
+ " ] which "
+ IF text = decoded
THEN
"correctly"
ELSE
"INCORRECTLY"
FI
+ " decodes to """
+ decoded
+ """"
)
, newline
)
)
END; # test encode and decode #
test encode and decode( "broood" )
; test encode and decode( "bananaaa" )
; test encode and decode( "hiphophiphop" )
# ; test encode and decode( "abcdefghijklmnopqrstuvwxyz" ) #
# ; test encode and decode( "zyxwvutsrqponmlkjihgfedcba" ) #- Output:
broood encodes to [ 1 17 15 0 0 5 ] which correctly decodes to "broood" bananaaa encodes to [ 1 1 13 1 1 1 0 0 ] which correctly decodes to "bananaaa" hiphophiphop encodes to [ 7 8 15 2 15 2 2 3 2 2 3 2 ] which correctly decodes to "hiphophiphop"
enc ← {⎕IO←0 ⋄ 0=≢⍵:⍵ ⋄ (⍺⍳c),(c,⍺~c←⊃⍵)∇1↓⍵}
dec ← {⎕IO←0 ⋄ 0=≢⍵:0↑⍺ ⋄ c,(c,⍺~c←(⊃⍵)⊃⍺)∇1↓⍵}
show ← {az←⎕C⎕A ⋄ e←az enc ⍵ ⋄ d←az dec e ⋄ ⍵≡d:⍵,' → ',(⍕e),' → ',d ⋄ 'Error'⎕SIGNAL 16}
↑show¨ 'broood' 'bananaaa' 'hiphophiphop'
- 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
symbolTable: @'a'..'z'
encodeWord: function [s][
symt: new symbolTable
result: []
loop s 'c [
idx: index symt c
'result ++ idx
symt: (rotate symt\[0..idx] 1) ++ symt\[(idx+1)..dec size symt]
]
return result
]
decodeWord: function [s][
symt: new symbolTable
result: []
loop s 'idx [
'result ++ symt\[idx]
symt: (rotate symt\[0..idx] 1) ++ symt\[(idx+1)..dec size symt]
]
return join result
]
loop ["broood", "babanaaa", "hiphophiphop"] 'word [
encoded: encodeWord word
decoded: decodeWord encoded
print ["'"++word++"'" "encodes to" encoded "which correctly decodes to" "'"++decoded++"'"]
]
- Output:
'broood' encodes to [1 17 15 0 0 5] which correctly decodes to 'broood' 'babanaaa' encodes to [1 1 1 1 13 1 0 0] which correctly decodes to 'babanaaa' 'hiphophiphop' encodes to [7 8 15 2 15 2 2 3 2 2 3 2] which correctly decodes to 'hiphophiphop'
MTF_Encode(string){
str := "abcdefghijklmnopqrstuvwxyz"
loop, parse, string
code .= (A_Index>1 ? ",":"") . InStr(str, A_LoopField) - 1 , str := A_LoopField . StrReplace(str, A_LoopField)
return code
}
MTF_Decode(code){
str := "abcdefghijklmnopqrstuvwxyz"
loop, parse, code, `,
string .= (letter := SubStr(str, A_LoopField+1, 1)) , str := letter . StrReplace(str, letter)
return string
}
Examples:
testStrings = broood,bananaaa,hiphophiphop
loop, parse, testStrings, `,
Output .= A_LoopField "`t" MTF_Encode(A_LoopField) "`t" MTF_Decode(MTF_Encode(A_LoopField)) "`n"
MsgBox % Output
return
Outputs:
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
10 DEFINT C,L: DIM C(128)
20 AL$="abcdefghijklmnopqrstuvwxyz"
30 READ W$: IF W$="" THEN END
40 PRINT W$;" -> ";
50 S$=W$: GOSUB 1000
60 FOR I=1 TO L: PRINT C(I);: NEXT I
70 GOSUB 1100
80 PRINT " -> ";S$
90 IF S$<>W$ THEN PRINT "Not equal"
100 GOTO 30
110 END
120 DATA broood,bananaaa,hiphophiphop,""
1000 REM ENCODE
1010 Z$=AL$
1020 FOR I=1 TO LEN(S$)
1030 J=INSTR(Z$,MID$(S$,I,1))
1040 C(I)=J-1
1050 Z$=MID$(Z$,J,1) + LEFT$(Z$,J-1) + RIGHT$(Z$,LEN(Z$)-J)
1060 NEXT I
1070 L=LEN(S$)
1080 RETURN
1100 REM DECODE
1110 Z$=AL$
1120 S$=""
1130 FOR I=1 TO L
1140 C$=MID$(Z$,C(I)+1,1)
1150 S$=S$+C$
1160 J=INSTR(Z$,C$)
1170 Z$=MID$(Z$,J,1) + LEFT$(Z$,J-1) + RIGHT$(Z$,LEN(Z$)-J)
1180 NEXT I
1190 RETURN
- 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
get "libhdr"
let indexof(ch, s) = valof
for i = 0 to s%0 do
if s%i = ch resultis i
let copy(sin, sout) be
for i = 0 to sin%0 do
sout%i := sin%i
let streq(a, b) = valof
$( for i = 0 to a%0 do
unless a%i = b%i resultis false
resultis true
$)
let movetofront(s, ch) be
$( let i = indexof(ch, s)
for j = i to 2 by -1 do
s%j := s%(j-1)
s%1 := ch
$)
let encode(s, alph, v) be
$( let a = vec 1+256/BYTESPERWORD
copy(alph, a)
for i = 1 to s%0
$( let c = indexof(s%i, a)
v!(i-1) := c-1
movetofront(a, s%i)
$)
$)
let decode(v, n, alph, s) be
$( let a = vec 1+256/BYTESPERWORD
copy(alph, a)
s%0 := n
for i = 0 to n-1
$( let c = a%(v!i+1)
s%(i+1) := c
movetofront(a, c)
$)
$)
let show(s) be
$( let enc = vec 256
let dec = vec 1+256/BYTESPERWORD
let alph = "abcdefghijklmnopqrstuvwxyz"
writes(s)
writes(" -> ")
encode(s, alph, enc)
for i = 0 to s%0-1 do writef("%N ", enc!i)
writes("-> ")
decode(enc, s%0, alph, dec)
writes(dec)
test streq(s, dec)
writes(" (ok)*N") or writes(" (fail)*N")
$)
let start() be
$( show("broood")
show("bananaaa")
show("hiphophiphop")
$)- Output:
broood -> 1 17 15 0 0 5 -> broood (ok) bananaaa -> 1 1 13 1 1 1 0 0 -> bananaaa (ok) hiphophiphop -> 7 8 15 2 15 2 2 3 2 2 3 2 -> hiphophiphop (ok)
( encode
= string symboltable
. !arg:(?string.?symboltable)
& vap
$ ( (
= A Z i
. !symboltable:?A [?i !arg ?Z
& !arg !A !Z:?symboltable
& !i
)
. !string
)
)
& ( decode
= indices symboltable
. !arg:(?indices.?symboltable)
& str
$ ( map
$ ( (
= A Z symbol
. !symboltable:?A [!arg %?symbol ?Z
& !symbol !A !Z:?symboltable
& !symbol
)
. !indices
)
)
)
& ( test
= string symboltable encoded decoded
. !arg:(?string.?symboltable)
& put$str$("input:" !string ", ")
& encode$(!string.!symboltable):?encoded
& put$("encoded:" !encoded ", ")
& decode$(!encoded.!symboltable):?decoded
& put$str$("decoded:" !decoded ", ")
& ( !string:!decoded
& out$OK
| out$WRONG
)
)
& a b c d e f g h i j k l m n o p q r s t y v w x y z
: ?symboltable
& test$(broood.!symboltable)
& test$(bananaaa.!symboltable)
& test$(hiphophiphop.!symboltable)#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 100
int move_to_front(char *str,char c)
{
char *q,*p;
int shift=0;
p=(char *)malloc(strlen(str)+1);
strcpy(p,str);
q=strchr(p,c); //returns pointer to location of char c in string str
shift=q-p; // no of characters from 0 to position of c in str
strncpy(str+1,p,shift);
str[0]=c;
free(p);
// printf("\n%s\n",str);
return shift;
}
void decode(int* pass,int size,char *sym)
{
int i,index;
char c;
char table[]="abcdefghijklmnopqrstuvwxyz";
for(i=0;i<size;i++)
{
c=table[pass[i]];
index=move_to_front(table,c);
if(pass[i]!=index) printf("there is an error");
sym[i]=c;
}
sym[size]='\0';
}
void encode(char *sym,int size,int *pass)
{
int i=0;
char c;
char table[]="abcdefghijklmnopqrstuvwxyz";
for(i=0;i<size;i++)
{
c=sym[i];
pass[i]=move_to_front(table,c);
}
}
int check(char *sym,int size,int *pass)
{
int *pass2=malloc(sizeof(int)*size);
char *sym2=malloc(sizeof(char)*size);
int i,val=1;
encode(sym,size,pass2);
i=0;
while(i<size && pass[i]==pass2[i])i++;
if(i!=size)val=0;
decode(pass,size,sym2);
if(strcmp(sym,sym2)!=0)val=0;
free(sym2);
free(pass2);
return val;
}
int main()
{
char sym[3][MAX_SIZE]={"broood","bananaaa","hiphophiphop"};
int pass[MAX_SIZE]={0};
int i,len,j;
for(i=0;i<3;i++)
{
len=strlen(sym[i]);
encode(sym[i],len,pass);
printf("%s : [",sym[i]);
for(j=0;j<len;j++)
printf("%d ",pass[j]);
printf("]\n");
if(check(sym[i],len,pass))
printf("Correct :)\n");
else
printf("Incorrect :(\n");
}
return 0;
}
- Output:
broood : [1 17 15 0 0 5 ] Correct :) bananaaa : [1 1 13 1 1 1 0 0 ] Correct :) hiphophiphop : [7 8 15 2 15 2 2 3 2 2 3 2 ] Correct :)
using System;
using System.Collections.Generic;
using System.Text;
namespace MoveToFront
{
class Program
{
private static char[] symbolTable;
private static void setSymbolTable()
{
symbolTable = "abcdefghijklmnopqrstuvwxyz".ToCharArray();
}
private static void moveToFront(int charIndex)
{
char toFront = symbolTable[charIndex];
for (int j = charIndex; j > 0; j--)
{
symbolTable[j] = symbolTable[j - 1];
}
symbolTable[0] = toFront;
}
public static int[] Encode(string input)
{
setSymbolTable();
var output = new List<int>();
foreach (char c in input)
{
for (int i = 0; i < 26; i++)
{
if (symbolTable[i] == c)
{
output.Add(i);
moveToFront(i);
break;
}
}
}
return output.ToArray();
}
public static string Decode(int[] input)
{
setSymbolTable();
var output = new StringBuilder(input.Length);
foreach (int n in input)
{
output.Append(symbolTable[n]);
moveToFront(n);
}
return output.ToString();
}
static void Main(string[] args)
{
string[] testInputs = new string[] { "broood", "bananaaa", "hiphophiphop" };
int[] encoding;
foreach (string s in testInputs)
{
Console.WriteLine($"Encoding for '{s}':");
encoding = Encode(s);
foreach (int i in encoding)
{
Console.Write($"{i} ");
}
Console.WriteLine($"\nDecoding for '{s}':");
Console.WriteLine($"{Decode(encoding)}\n");
}
}
}
}
#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>
using namespace std;
class MTF
{
public:
string encode( string str )
{
fillSymbolTable();
vector<int> output;
for( string::iterator it = str.begin(); it != str.end(); it++ )
{
for( int i = 0; i < 26; i++ )
{
if( *it == symbolTable[i] )
{
output.push_back( i );
moveToFront( i );
break;
}
}
}
string r;
for( vector<int>::iterator it = output.begin(); it != output.end(); it++ )
{
ostringstream ss;
ss << *it;
r += ss.str() + " ";
}
return r;
}
string decode( string str )
{
fillSymbolTable();
istringstream iss( str ); vector<int> output;
copy( istream_iterator<int>( iss ), istream_iterator<int>(), back_inserter<vector<int> >( output ) );
string r;
for( vector<int>::iterator it = output.begin(); it != output.end(); it++ )
{
r.append( 1, symbolTable[*it] );
moveToFront( *it );
}
return r;
}
private:
void moveToFront( int i )
{
char t = symbolTable[i];
for( int z = i - 1; z >= 0; z-- )
symbolTable[z + 1] = symbolTable[z];
symbolTable[0] = t;
}
void fillSymbolTable()
{
for( int x = 0; x < 26; x++ )
symbolTable[x] = x + 'a';
}
char symbolTable[26];
};
int main()
{
MTF mtf;
string a, str[] = { "broood", "bananaaa", "hiphophiphop" };
for( int x = 0; x < 3; x++ )
{
a = str[x];
cout << a << " -> encoded = ";
a = mtf.encode( a );
cout << a << "; decoded = " << mtf.decode( a ) << endl;
}
return 0;
}
- Output:
broood -> encoded = 1 17 15 0 0 5 ; decoded = broood bananaaa -> encoded = 1 1 13 1 1 1 0 0 ; decoded = bananaaa hiphophiphop -> encoded = 7 8 15 2 15 2 2 3 2 2 3 2 ; decoded = hiphophiphop
(def lowercase (map char (range (int \a) (inc (int \z)))))
(defn move-to-front [x xs]
(cons x (remove #{x} xs)))
(defn encode [text table & {:keys [acc] :or {acc []}}]
(let [c (first text)
idx (.indexOf table c)]
(if (empty? text) acc (recur (drop 1 text) (move-to-front c table) {:acc (conj acc idx)}))))
(defn decode [indices table & {:keys [acc] :or {acc []}}]
(if (empty? indices) (apply str acc)
(let [n (first indices)
c (nth table n)]
(recur (drop 1 indices) (move-to-front c table) {:acc (conj acc c)}))))
(doseq [word ["broood" "bananaaa" "hiphophiphop"]]
(let [encoded (encode word lowercase)
decoded (decode encoded lowercase)]
(println (format "%s encodes to %s which decodes back to %s."
word encoded decoded))))
- 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.
movetofront = proc (s: string, c: char) returns (string) signals (not_found)
if string$indexc(c, s) = 0 then signal not_found end
next: array[char] := array[char]$[c]
for sc: char in string$chars(s) do
if sc = c then continue end
array[char]$addh(next, sc)
end
return(string$ac2s(next))
end movetofront
encode = proc (s, alph: string) returns (sequence[int]) signals (not_found)
encoded: array[int] := array[int]$[]
for c: char in string$chars(s) do
array[int]$addh(encoded, string$indexc(c, alph) - 1)
alph := movetofront(alph, c) resignal not_found
end
return(sequence[int]$a2s(encoded))
end encode
decode = proc (data: sequence[int], alph: string) returns (string) signals (not_found)
decoded: array[char] := array[char]$[]
for n: int in sequence[int]$elements(data) do
c: char := alph[n + 1]
array[char]$addh(decoded, c)
alph := movetofront(alph, c) resignal not_found
end
return(string$ac2s(decoded))
end decode
print_seq = proc (seq: sequence[int], s: stream)
for n: int in sequence[int]$elements(seq) do
stream$puts(s, int$unparse(n) || " ")
end
end print_seq
start_up = proc ()
po: stream := stream$primary_output()
words: sequence[string] := sequence[string]$["broood", "bananaaa", "hiphophiphop"]
alph: string := "abcdefghijklmnopqrstuvwxyz"
for word: string in sequence[string]$elements(words) do
stream$puts(po, word || " -> ")
encoded: sequence[int] := encode(word, alph)
print_seq(encoded, po)
stream$puts(po, "-> ")
decoded: string := decode(encoded, alph)
stream$puts(po, decoded)
if word = decoded
then stream$putl(po, " ok")
else stream$putl(po, " fail")
end
end
end start_up- Output:
broood -> 1 17 15 0 0 5 -> broood ok bananaaa -> 1 1 13 1 1 1 0 0 -> bananaaa ok hiphophiphop -> 7 8 15 2 15 2 2 3 2 2 3 2 -> hiphophiphop ok
IDENTIFICATION DIVISION.
PROGRAM-ID. MTF-ENCODE-DECODE.
DATA DIVISION.
WORKING-STORAGE SECTION.
*> Initial alphabet reference
01 ALPHABET-INIT PIC X(26) VALUE
"abcdefghijklmnopqrstuvwxyz".
*> Dynamic character list (simulates the JS charList array)
01 CHAR-TABLE.
05 CHAR-ITEM PIC X OCCURS 26 TIMES.
*> Variables for processing
01 WORK-AREAS.
05 INPUT-WORD PIC X(20) VALUE SPACES.
05 WORD-LEN PIC 99 VALUE 0.
05 I PIC 99 VALUE 0.
05 J PIC 99 VALUE 0.
05 K PIC 99 VALUE 0.
05 TEMP-CHAR PIC X VALUE SPACE.
05 CHAR-INDEX PIC 99 VALUE 0.
*> Storage for algorithm outputs
01 ENCODED-DATA.
05 ENCODED-NUMBERS PIC 99 OCCURS 20 TIMES.
01 DECODED-DATA.
05 DECODED-WORD PIC X(20) VALUE SPACES.
*> Variables for console logging/displaying
01 DISPLAY-AREAS.
05 DISPLAY-LINE PIC X(120) VALUE SPACES.
05 DISP-POS PIC 99 VALUE 1.
05 DISP-NUM PIC Z9.
*> Equivalent to JS: var words = ['broood', ...]
01 TEST-DATA.
05 TEST-WORDS.
10 FILLER PIC X(20) VALUE "broood".
10 FILLER PIC X(20) VALUE "bananaaa".
10 FILLER PIC X(20) VALUE "hiphophiphop".
05 TEST-WORD-REDEF REDEFINES TEST-WORDS.
10 TEST-WORD-ARR PIC X(20) OCCURS 3 TIMES.
05 TEST-IDX PIC 9 VALUE 1.
PROCEDURE DIVISION.
MAIN-LOGIC.
DISPLAY "Testing Move-To-Front (MTF) Algorithm".
DISPLAY "=====================================".
*> Equivalent to: words.map(...)
PERFORM VARYING TEST-IDX FROM 1 BY 1 UNTIL TEST-IDX > 3
MOVE TEST-WORD-ARR(TEST-IDX) TO INPUT-WORD
PERFORM GET-WORD-LENGTH
DISPLAY "Original Word : " INPUT-WORD(1:WORD-LEN)
*> Encode
PERFORM ENCODE-MTF
PERFORM PRINT-ENCODED
*> Decode
PERFORM DECODE-MTF
PERFORM PRINT-DECODED
DISPLAY "-------------------------------------"
END-PERFORM.
STOP RUN.
*> ==========================================
*> ENCODE ALGORITHM
*> ==========================================
ENCODE-MTF.
PERFORM INIT-CHAR-LIST.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WORD-LEN
MOVE INPUT-WORD(I:1) TO TEMP-CHAR
MOVE 0 TO CHAR-INDEX
*> Simulate JS: charList.indexOf(char)
PERFORM VARYING J FROM 1 BY 1
UNTIL J > 26 OR CHAR-INDEX > 0
IF CHAR-ITEM(J) = TEMP-CHAR
MOVE J TO CHAR-INDEX
END-IF
END-PERFORM
*> JS arrays are 0-indexed, COBOL is 1-indexed.
*> Subtract 1 to match exact JS numeric output.
COMPUTE ENCODED-NUMBERS(I) = CHAR-INDEX - 1
*> Simulate JS: splice(charNum, 1) and unshift()
PERFORM MOVE-TO-FRONT
END-PERFORM.
*> ==========================================
*> DECODE ALGORITHM
*> ==========================================
DECODE-MTF.
PERFORM INIT-CHAR-LIST.
MOVE SPACES TO DECODED-WORD.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WORD-LEN
*> Convert JS 0-based index back to COBOL 1-based index
COMPUTE CHAR-INDEX = ENCODED-NUMBERS(I) + 1
MOVE CHAR-ITEM(CHAR-INDEX) TO TEMP-CHAR
*> Append character to decoded string
MOVE TEMP-CHAR TO DECODED-WORD(I:1)
*> Simulate JS: splice(num, 1) and unshift()
PERFORM MOVE-TO-FRONT
END-PERFORM.
*> ==========================================
*> SHARED HELPER FUNCTIONS
*> ==========================================
*> Moves item at CHAR-INDEX to position 1, shifting rest right
MOVE-TO-FRONT.
IF CHAR-INDEX > 1
PERFORM VARYING K FROM CHAR-INDEX BY -1 UNTIL K = 1
COMPUTE J = K - 1
MOVE CHAR-ITEM(J) TO CHAR-ITEM(K)
END-PERFORM
MOVE TEMP-CHAR TO CHAR-ITEM(1)
END-IF.
*> Resets the array back to "a" through "z"
INIT-CHAR-LIST.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > 26
MOVE ALPHABET-INIT(I:1) TO CHAR-ITEM(I)
END-PERFORM.
*> Trims whitespace to find true length of current input word
GET-WORD-LENGTH.
MOVE 0 TO WORD-LEN.
PERFORM VARYING I FROM 20 BY -1
UNTIL I < 1 OR INPUT-WORD(I:1) NOT = SPACE
CONTINUE
END-PERFORM.
MOVE I TO WORD-LEN.
*> ==========================================
*> DISPLAY/LOGGING FORMATTERS
*> ==========================================
PRINT-ENCODED.
MOVE SPACES TO DISPLAY-LINE.
MOVE 1 TO DISP-POS.
STRING "Encoded Array : [" DELIMITED BY SIZE
INTO DISPLAY-LINE WITH POINTER DISP-POS.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WORD-LEN
MOVE ENCODED-NUMBERS(I) TO DISP-NUM
IF I = WORD-LEN
STRING DISP-NUM DELIMITED BY SIZE
"]" DELIMITED BY SIZE
INTO DISPLAY-LINE WITH POINTER DISP-POS
ELSE
STRING DISP-NUM DELIMITED BY SIZE
", " DELIMITED BY SIZE
INTO DISPLAY-LINE WITH POINTER DISP-POS
END-IF
END-PERFORM.
DISPLAY DISPLAY-LINE(1:DISP-POS).
PRINT-DECODED.
DISPLAY "Decoded Word : " DECODED-WORD(1:WORD-LEN).
- Output:
Testing Move-To-Front (MTF) Algorithm ===================================== Original Word : broood Encoded Array : [ 1, 17, 15, 0, 0, 5] Decoded Word : broood ------------------------------------- Original Word : bananaaa Encoded Array : [ 1, 1, 13, 1, 1, 1, 0, 0] Decoded Word : bananaaa ------------------------------------- Original Word : hiphophiphop Encoded Array : [ 7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] Decoded Word : hiphophiphop -------------------------------------
(defconstant +lower+ (coerce "abcdefghijklmnopqrstuvwxyz" 'list))
(defun move-to-front (x xs)
(cons x (remove x xs)))
(defun enc (text table)
(map 'list
(lambda (c)
(let ((idx (position c table)))
(setf table (move-to-front c table))
idx))
text))
(defun dec (indices table)
(coerce (mapcar (lambda (idx)
(let ((c (nth idx table)))
(setf table (move-to-front c table))
c))
indices)
'string))
(loop for word in '("broood" "bananaaa" "hiphophiphop")
do (let* ((encoded (enc word +lower+))
(decoded (dec encoded +lower+)))
(assert (string= word decoded))
(format T "~s encodes to ~a which decodes back to ~s.~%"
word encoded decoded)))
- 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".
include "cowgol.coh";
include "strings.coh";
sub CheckCharError(ptr: [uint8]) is
if ptr == 0 as [uint8] then
print("Character not found.\n");
ExitWithError();
end if;
end sub;
sub FindChar(chr: uint8, str: [uint8]): (loc: [uint8]) is
loc := 0 as [uint8];
var begin := str;
while [str] != 0 and [str] != chr loop
str := @next str;
end loop;
if [str] == chr then
loc := str;
end if;
end sub;
sub FindCharIdx(chr: uint8, str: [uint8]): (idx: intptr) is
var locptr := FindChar(chr, str);
CheckCharError(locptr);
idx := locptr - str;
end sub;
sub MoveToFront(sym: uint8, symtab: [uint8]) is
var symptr := FindChar(sym, symtab);
CheckCharError(symptr);
while symptr > symtab loop
[symptr] := [@prev symptr];
symptr := @prev symptr;
end loop;
[symtab] := sym;
end sub;
sub Encode(string: [uint8], symtab: [uint8], result: [uint8]) is
var symtab_buffer: uint8[256];
var st := &symtab_buffer[0];
CopyString(symtab, st);
while [string] != 0 loop
[result] := FindCharIdx([string], st) as uint8;
MoveToFront([string], st);
string := @next string;
result := @next result;
end loop;
end sub;
sub Decode(codes: [uint8], size: intptr, symtab: [uint8], result: [uint8]) is
var symtab_buffer: uint8[256];
var st := &symtab_buffer[0];
CopyString(symtab, st);
while size > 0 loop
[result] := [st + [codes] as intptr];
MoveToFront([result], st);
codes := @next codes;
result := @next result;
size := size - 1;
end loop;
[result] := 0;
end sub;
sub Test(string: [uint8]) is
sub PrintArr(codes: [uint8], size: intptr) is
while size > 0 loop
print_i8([codes]);
print_char(' ');
codes := @next codes;
size := size - 1;
end loop;
end sub;
var symtab := "abcdefghijklmnopqrstuvwxyz";
var encoded_buf: uint8[256];
var decoded_buf: uint8[256];
var encoded := &encoded_buf[0];
var decoded := &decoded_buf[0];
var size := StrLen(string);
print(string);
print(" -> ");
Encode(string, symtab, encoded);
PrintArr(encoded, size);
print("-> ");
Decode(encoded, size, symtab, decoded);
print(decoded);
if StrCmp(string, decoded) == 0 then
print(" (ok)\n");
else
print(" (fail)\n");
end if;
end sub;
Test("broood");
Test("bananaaa");
Test("hiphophiphop");- Output:
broood -> 1 17 15 0 0 5 -> broood (ok) bananaaa -> 1 1 13 1 1 1 0 0 -> bananaaa (ok) hiphophiphop -> 7 8 15 2 15 2 2 3 2 2 3 2 -> hiphophiphop (ok)
class Array
# useful method to work on parts of the array in-place
def slice (start, length)
start = size - start if start < 0
raise "Out of bounds" unless start >= 0 && length >= 0 && start + length <= size
Slice.new(to_unsafe + start, length)
end
end
def encode (message, symbols)
symbols = symbols.dup
message.chars.map {|ch|
idx = symbols.index! ch
symbols.slice(0, idx+1).rotate! -1
idx
}
end
def decode (message, symbols)
symbols = symbols.dup
message.map {|idx|
ch = symbols[idx]
symbols.slice(0, idx+1).rotate! -1
ch
}.join
end
symbols = ('a'..'z').to_a
["broood", "bananaaa", "hiphophiphop"].each do |word|
encoded = encode(word, symbols)
decoded = decode(encoded, symbols)
printf "%-12s -> %-38s -> %s\n", word, encoded, decoded
end
- 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
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);
}
}
- 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'
subr init
symt$[] = strchars "abcdefghijklmnopqrstuvwxyz"
.
proc rot k .
c$ = symt$[k]
for j = k downto 2
symt$[j] = symt$[j - 1]
.
symt$[1] = c$
.
func[] encode s$ .
init
for c$ in strchars s$
k = 1
while symt$[k] <> c$
k += 1
.
res[] &= k - 1
rot k
.
return res[]
.
func$ decode s[] .
init
for k in s[]
k += 1
c$ = symt$[k]
res$ &= c$
rot k
.
return res$
.
for word$ in [ "broood" "babanaaa" "hiphophiphop" ]
enc[] = encode word$
print word$ & " -> " & enc[]
if decode enc[] <> word$
print "error"
.
.- Output:
broood -> [ 1 17 15 0 0 5 ] babanaaa -> [ 1 1 1 1 13 1 0 0 ] hiphophiphop -> [ 7 8 15 2 15 2 2 3 2 2 3 2 ]
defmodule MoveToFront do
@table Enum.to_list(?a..?z)
def encode(text), do: encode(to_char_list(text), @table, [])
defp encode([], _, output), do: Enum.reverse(output)
defp encode([h|t], table, output) do
i = Enum.find_index(table, &(&1 == h))
encode(t, move2front(table, i), [i | output])
end
def decode(indices), do: decode(indices, @table, [])
defp decode([], _, output), do: Enum.reverse(output) |> to_string
defp decode([h|t], table, output) do
decode(t, move2front(table, h), [Enum.at(table, h) | output])
end
def move2front(table, i), do: [Enum.at(table,i) | List.delete_at(table, i)]
end
Enum.each(["broood", "bananaaa", "hiphophiphop"], fn word ->
IO.inspect word
IO.inspect enc = MoveToFront.encode(word)
IO.puts "#{word == MoveToFront.decode(enc)}\n"
end)
- Output:
"broood" [1, 17, 15, 0, 0, 5] true "bananaaa" [1, 1, 13, 1, 1, 1, 0, 0] true "hiphophiphop" [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] true
// Move-to-front algorithm . Nigel Galloway: March 1st., 2021
let fN g=List.permute(fun n->match compare n g with 0->0 |1->n |_->n+1)
let decode n=let rec fG n g=[|match n with n::t->yield List.item n g; yield! fG t (fN n g)|_->()|] in fG n ['a'..'z']|>System.String
let encode n=let rec fG n g=[match n with n::t->let n=g|>List.findIndex((=)n) in yield n; yield! fG t (fN n g)|_->()]
fG ((string n).ToCharArray()|>List.ofArray) ['a'..'z']
["broood";"bananaaa";"hiphophiphop"]|>List.iter(fun n->let i=encode n in let g=decode i in printfn "%s->%A->%s check=%A" n i g (n=g))
- Output:
broood->[1; 17; 15; 0; 0; 5]->broood check=true bananaaa->[1; 1; 13; 1; 1; 1; 0; 0]->bananaaa check=true hiphophiphop->[7; 8; 15; 2; 15; 2; 2; 3; 2; 2; 3; 2]->hiphophiphop check=true
USING: formatting kernel locals make sequences ;
: to-front ( elt seq -- seq' ) over [ remove ] dip prefix ;
: encode ( symbols msg -- indices )
[ [ swap 2dup index , to-front ] each ] { } make nip ;
: decode ( symbols indices -- msg )
[ [ swap [ nth ] keep over , to-front ] each ] "" make nip ;
:: round-trip ( msg symbols -- )
symbols msg encode :> encoded
symbols encoded decode :> decoded
msg decoded assert=
msg encoded decoded "%s -> %u -> %s\n" printf ;
"broood" "bananaaa" "hiphophiphop"
[ "abcdefghijklmnopqrstuvwxyz" round-trip ] tri@
- 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
! Move-to-front algorithm
! tested with Intel ifx (IFX) 2025.2.1 20250806 on Kubuntu 25.10
! GNU Fortran (Ubuntu 15.2.0-4ubuntu4) 15.2.0 on Kubuntu 25.10
! VSI Fortran x86-64 V8.7-001 on OpenVMS x86_64 V9.2-3
! No Non-standard features used, should compile on any fairly recent Fortran.
! U.B., February 2026
!=========================================================================================
program FrontMove
implicit none
! Starting sequence in the local symbol tables in 2 subroutines
character (len=26), parameter :: startSymbolTab = 'abcdefghijklmnopqrstuvwxyz'
! The test cases of the task description:
call EncodeAndCrossCheck ('broood')
call EncodeAndCrossCheck ('bananaaa')
call EncodeAndCrossCheck ('hiphophiphop')
! Two more tests: What happens in MoveToFront() if char appears at the beginning ('a')
! or at the end ('z') of the symbol table?
call EncodeAndCrossCheck ('anton')
call EncodeAndCrossCheck ('zwareshagz')
contains
! =========================================================================
! Encode a given text string using the Move-to-fromt algorithm, then
! decode the resultant sequence of numbers, to be compared to the original.
! =========================================================================
subroutine EncodeAndCrossCheck (text)
character (len=*), intent(in) :: text ! Input: the text to encode
integer, dimension(len(text)) :: code ! Resultant numeric array
character (len=26) :: SymTab ! The symbol table to work with
integer :: l ! LEngth of input text
integer :: ii, idx ! Loop index, Pos of a char inside Symbol Table
! Initialize work table
SymTab = startSymbolTab
l = len (text)
write (*,'(A, T13, A)', advance='no') text, ' ->'
! 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
do ii=1, l
idx = index (SymTab, text(ii:ii))
code (ii) = idx-1 ! Code muss be null-based
write (*, '(I3)', advance='no') code(ii)
call moveToFront (SymTab, idx)
end do
do ii=3*l,36
write (*,'(x)', advance='no') ! some space to format output
enddo
write (*,'(A)', advance='no') ' -> '
! Now decode the resultant code and hope to see again the original text.
call decodeAndCheck (code, l, text)
end subroutine EncodeAndCrossCheck
! =====================================================================================
! Decode a given array of numbers and check if the rtesult matches the given input text
! =====================================================================================
subroutine decodeAndCheck (code, l, text)
integer , intent(in) ::l
integer, dimension(l), intent(in) :: code
character (len=*), intent(in) :: text ! the text to compare to the decode result.
character (len=26) :: SymTab
integer :: ii, idx
logical :: mismatch
! # Using the same starting symbol table
SymTab = startSymbolTab
mismatch = .false.
! Decoding Algorithm:
! 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
do ii=1, l
idx = code(ii) + 1
write (*, '(A1)', advance='no') SymTab (idx:idx)
if (SymTab (idx:idx) .ne. text (ii:ii)) mismatch = .true.
call moveToFront (SymTab, idx)
end do
if (.not. mismatch) then
write (*,*) '(Success)'
else
write (*,*) 'ERROR.'
endif
end subroutine decodeAndCheck
! =========================================================================
! Move the character found at index 'ind' in the string "'txt' to the front
! =========================================================================
subroutine moveToFront (txt, ind)
character (len=*), intent(inout) :: txt
integer, intent(in) :: ind
! Rearrange txt: character at ind, then everything in front of ind, then everything behind.
txt = txt(ind:ind) // txt(:ind-1) // txt (ind+1:)
end subroutine moveToFront
end program FrontMove
- Output:
broood -> 1 17 15 0 0 5 -> broood (Success) bananaaa -> 1 1 13 1 1 1 0 0 -> bananaaa (Success) hiphophiphop -> 7 8 15 2 15 2 2 3 2 2 3 2 -> hiphophiphop (Success) anton -> 0 13 19 15 2 -> anton (Success) zwareshagz -> 25 23 2 19 7 20 11 4 11 7 -> zwareshagz (Success)
#define FAIL -1
sub mtf( s() as string, i as uinteger )
'moves the symbol at index i to the front and shifts preceding ones back
dim as string*1 t = s(i)
for j as uinteger = i to 1 step -1
s(j) = s(j-1)
next j
s(0)=t
end sub
sub make_symbols( s() as string )
'populates an array of strings with the lowercase alphabet
for i as uinteger = 97 to 122
s(i-97) = chr(i)
next i
end sub
function find( s() as string, l as string ) as integer
'returns the index of the first occurrence of the symbol l in s()
for i as uinteger = 0 to ubound(s)
if s(i) = l then return i
next i
return FAIL
end function
sub encode( s() as string, ind() as uinteger )
dim as integer n = ubound(s), i
redim as uinteger ind(0 to n)
dim as string a(0 to 25)
make_symbols(a())
for z as uinteger = 0 to n
i = find( a(), s(z) )
if i = FAIL then
print "Uh oh! Couldn't find ";s(z);" in alphabet."
end
end if
mtf( a(), i )
ind(z) = i
next z
end sub
sub decode( s() as string, ind() as uinteger )
dim as integer n = ubound(ind), i
redim as string s(0 to n)
dim as string a(0 to 25)
make_symbols(a())
for z as uinteger = 0 to n
s(z) = a(ind(z))
mtf(a(), ind(z))
next z
end sub
sub printarr( s() as string )
for i as uinteger = 0 to ubound(s)
print s(i);
next i
print
end sub
sub printind( ind() as integer )
for i as uinteger = 0 to ubound(ind)
print ind(i);" ";
next i
print
end sub
sub compose( s() as string, b as string )
'turns a string into a zero-indexed array of single letters
'The reason we use such arrays is to get them zero-indexed
'and to make the point that we could work with multi-char
'symbol tables if we wanted to
dim as integer n = len(b), i
redim as string s(0 to n-1)
for i = 0 to n-1
s(i) = mid(b, 1+i, 1)
next i
end sub
'-----------now the tests-------------
redim as string s(0)
redim as integer ind(0)
compose( s(), "broood" )
encode( s(), ind() )
printind( ind() )
decode( s(), ind() )
printarr( s() ) : print
compose( s(), "bananaaa" )
encode( s(), ind() )
printind( ind() )
decode( s(), ind() )
printarr( s() ) : print
compose( s(), "hiphophiphop" )
encode( s(), ind() )
printind( ind() )
decode( s(), ind() )
printarr( s() )
- Output:
1 17 15 0 0 5 broood
1 1 13 1 1 1 0 0 bananaaa
7 8 15 2 15 2 2 3 2 2 3 2 hiphophiphop
Click this link to run this code
Public Sub Main()
Dim sToCode As String[] = ["broood", "bananaaa", "hiphophiphop"] 'Samples to process
Dim sHold As New String[] 'To store results
Dim siCount, siCounter, siPos As Short 'Various variables
Dim sOutput, sCode, sWork, sEach As String 'Various variables
For siCounter = 0 To sToCode.Max 'To loop through each 'Sample'
sCode = "abcdefghijklmnopqrstuvwxyz" 'Set sCode to default setting
For siCount = 1 To Len(sToCode[siCounter]) 'Loop through each letter in 'Sample'
sWork = Mid(sToCode[siCounter], siCount, 1) 'sWork to store the Letter
siPos = InStr(scode, sWork) - 1 'Find the position of the letter in sCode, -1 for '0' based array
sOutput &= Str(siPos) & " " 'Add the postion to sOutput
sCode = Mid(sCode, siPos + 1, 1) & Replace(sCode, sWork, "") 'sCode = the letter + the rest of sCode except the letter
Next
Print sToCode[siCounter] & " = " & sOutput 'Print the 'Sample' and the coded version
sHold.Add(Trim(sOutput)) 'Add the code to the sHold array
sOutput = "" 'Clear sOutput
Next
Print 'Print a blank line
For siCounter = 0 To sHold.Max 'To loop through each coded 'Sample'
sCode = "abcdefghijklmnopqrstuvwxyz" 'Set sCode to default setting
For Each sEach In Split(sHold[siCounter], " ") 'For each 'code' in coded 'Sample'
sWork = Mid(sCode, Val(sEach) + 1, 1) 'sWork = the decoded letter
sOutput &= sWork 'Add the decoded letter to sOutput
sCode = sWork & Replace(sCode, sWork, "") 'sCode = the decoded letter + the rest of sCode except the letter
Next
Print sHold[siCounter] & " = " & sOutput 'Print the coded and decoded result
sOutput = "" 'Clear sOutput
Next
End
Output:
broood = 1 17 15 0 0 5 bananaaa = 1 1 13 1 1 1 0 0 hiphophiphop = 7 8 15 2 15 2 2 3 2 2 3 2 1 17 15 0 0 5 = broood 1 1 13 1 1 1 0 0 = bananaaa 7 8 15 2 15 2 2 3 2 2 3 2 = hiphophiphop
package main
import (
"bytes"
"fmt"
)
type symbolTable string
func (symbols symbolTable) encode(s string) []byte {
seq := make([]byte, len(s))
pad := []byte(symbols)
for i, c := range []byte(s) {
x := bytes.IndexByte(pad, c)
seq[i] = byte(x)
copy(pad[1:], pad[:x])
pad[0] = c
}
return seq
}
func (symbols symbolTable) decode(seq []byte) 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 := symbolTable("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!")
}
}
}
- 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
import Data.List (delete, elemIndex, mapAccumL)
import Data.Maybe (fromJust)
table :: String
table = ['a' .. 'z']
encode :: String -> [Int]
encode =
let f t s = (s : delete s t, fromJust (elemIndex s t))
in snd . mapAccumL f table
decode :: [Int] -> String
decode = snd . mapAccumL f table
where
f t i =
let s = (t !! i)
in (s : delete s t, s)
main :: IO ()
main =
mapM_ print $
(,) <*> uncurry ((==) . fst) <$> -- Test that ((fst . fst) x) == snd x)
((,) <*> (decode . snd) <$>
((,) <*> encode <$> ["broood", "bananaaa", "hiphophiphop"]))
- Output:
((("broood",[1,17,15,0,0,5]),"broood"),True)
((("bananaaa",[1,1,13,1,1,1,0,0]),"bananaaa"),True)
((("hiphophiphop",[7,8,15,2,15,2,2,3,2,2,3,2]),"hiphophiphop"),True)
Works in both languages:
procedure main(A)
every writes(s := !A, " -> [") do {
every writes(!(enc := encode(&lcase,s))," ")
writes("] -> ",s2 := decode(&lcase,enc))
write((s == s2, " (Correct)") | " (Incorrect)")
}
end
procedure encode(m,s)
enc := []
every c := !s do {
m ?:= reorder(tab(i := upto(c)),move(1),tab(0))
put(enc,i-1) # Strings are 1-based
}
return enc
end
procedure decode(m,enc)
dec := ""
every i := 1 + !enc do { # Lists are 1-based
dec ||:= m[i]
m ?:= reorder(tab(i),move(1),tab(0))
}
return dec
end
procedure reorder(s1,s2,s3)
return s2||s1||s3
end
Sample run:
->mtfa broood bananaaa hiphophiphop broood -> [1 17 15 0 0 5 ] -> broood (Correct) bananaaa -> [1 1 13 1 1 1 0 0 ] -> bananaaa (Correct) hiphophiphop -> [7 8 15 2 15 2 2 3 2 2 3 2 ] -> hiphophiphop (Correct) ->
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
)
Required examples:
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
It's not clear, though, why anyone would think that this is any better than lookups against an unmodified symbol table.
import java.util.LinkedList;
import java.util.List;
public class MTF{
public static List<Integer> encode(String msg, String symTable){
List<Integer> output = new LinkedList<Integer>();
StringBuilder s = new StringBuilder(symTable);
for(char c : msg.toCharArray()){
int idx = s.indexOf("" + c);
output.add(idx);
s = s.deleteCharAt(idx).insert(0, c);
}
return output;
}
public static String decode(List<Integer> idxs, String symTable){
StringBuilder output = new StringBuilder();
StringBuilder s = new StringBuilder(symTable);
for(int idx : idxs){
char c = s.charAt(idx);
output = output.append(c);
s = s.deleteCharAt(idx).insert(0, c);
}
return output.toString();
}
private static void test(String toEncode, String symTable){
List<Integer> encoded = encode(toEncode, symTable);
System.out.println(toEncode + ": " + encoded);
String decoded = decode(encoded, symTable);
System.out.println((toEncode.equals(decoded) ? "" : "in") + "correctly decoded to " + decoded);
}
public static void main(String[] args){
String symTable = "abcdefghijklmnopqrstuvwxyz";
test("broood", symTable);
test("bananaaa", symTable);
test("hiphophiphop", symTable);
}
}
- Output:
broood: [1, 17, 15, 0, 0, 5] correctly decoded to broood bananaaa: [1, 1, 13, 1, 1, 1, 0, 0] correctly decoded to bananaaa hiphophiphop: [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] correctly decoded to hiphophiphop
var encodeMTF = function (word) {
var init = {wordAsNumbers: [], charList: 'abcdefghijklmnopqrstuvwxyz'.split('')};
return word.split('').reduce(function (acc, char) {
var charNum = acc.charList.indexOf(char); //get index of char
acc.wordAsNumbers.push(charNum); //add original index to acc
acc.charList.unshift(acc.charList.splice(charNum, 1)[0]); //put at beginning of list
return acc;
}, init).wordAsNumbers; //return number list
};
var decodeMTF = function (numList) {
var init = {word: '', charList: 'abcdefghijklmnopqrstuvwxyz'.split('')};
return numList.reduce(function (acc, num) {
acc.word += acc.charList[num];
acc.charList.unshift(acc.charList.splice(num, 1)[0]); //put at beginning of list
return acc;
}, init).word;
};
//test our algorithms
var words = ['broood', 'bananaaa', 'hiphophiphop'];
var encoded = words.map(encodeMTF);
var decoded = encoded.map(decodeMTF);
//print results
console.log("from encoded:");
console.log(encoded);
console.log("from decoded:");
console.log(decoded);
- Output:
from encoded: [ [1, 17, 15, 0, 0, 5], [1, 1, 13, 1, 1, 1, 0, 0], [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] ] from decoded: ['broood', 'bananaaa', 'hiphophiphop']
# Input is the string to be encoded, st is the initial symbol table (an array)
# Output: the encoded string (an array)
def m2f_encode(st):
reduce explode[] as $ch
( [ [], st]; # state: [ans, st]
(.[1]|index($ch)) as $ix
| .[1] as $st
| [ (.[0] + [ $ix ]), [$st[$ix]] + $st[0:$ix] + $st[$ix+1:] ] )
| .[0];
# Input should be the encoded string (an array)
# and st should be the initial symbol table (an array)
def m2f_decode(st):
reduce .[] as $ix
( [ [], st]; # state: [ans, st]
.[1] as $st
| [ (.[0] + [ $st[$ix] ]), [$st[$ix]] + $st[0:$ix] + $st[$ix+1:] ] )
| .[0]
| implode;Example:
("abcdefghijklmnopqrstuvwxyz" | explode) as $ST
| ("broood", "bananaaa", "hiphophiphop")
| . as $string
| m2f_encode($ST)
| . as $encoded
| m2f_decode($ST) as $decoded
| if $string == $decoded then "\($string) => \($encoded) => \($decoded)"
else "INTERNAL ERROR: encoding of \($string) => \($encoded) => \($decoded)"
end- Output:
$ jq -r -n -f move_to_front.jq
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
function encodeMTF(str::AbstractString, symtable::Vector{Char}=collect('a':'z'))
function encode(ch::Char)
r = findfirst(symtable, ch)
deleteat!(symtable, r)
prepend!(symtable, ch)
return r
end
collect(encode(ch) for ch in str)
end
function decodeMTF(arr::Vector{Int}, symtable::Vector{Char}=collect('a':'z'))
function decode(i::Int)
r = symtable[i]
deleteat!(symtable, i)
prepend!(symtable, r)
return r
end
join(decode(i) for i in arr)
end
testset = ["broood", "bananaaa", "hiphophiphop"]
encoded = encodeMTF.(testset)
decoded = decodeMTF.(encoded)
for (str, enc, dec) in zip(testset, encoded, decoded)
println("Test string: $str\n -> Encoded: $enc\n -> Decoded: $dec")
end
using Base.Test
@testset "Decoded string equal to original" begin
for (str, dec) in zip(testset, decoded)
@test str == dec
end
end
- Output:
Test string: broood -> Encoded: [2, 18, 16, 1, 1, 6] -> Decoded: broood Test string: bananaaa -> Encoded: [2, 2, 14, 2, 2, 2, 1, 1] -> Decoded: bananaaa Test string: hiphophiphop -> Encoded: [8, 9, 16, 3, 16, 3, 3, 4, 3, 3, 4, 3] -> Decoded: hiphophiphop Test Summary: | Pass Total Decoded string equal to original | 3 3
// version 1.1.2
fun encode(s: String): IntArray {
if (s.isEmpty()) return intArrayOf()
val symbols = "abcdefghijklmnopqrstuvwxyz".toCharArray()
val result = IntArray(s.length)
for ((i, c) in s.withIndex()) {
val index = symbols.indexOf(c)
if (index == -1)
throw IllegalArgumentException("$s contains a non-alphabetic character")
result[i] = index
if (index == 0) continue
for (j in index - 1 downTo 0) symbols[j + 1] = symbols[j]
symbols[0] = c
}
return result
}
fun decode(a: IntArray): String {
if (a.isEmpty()) return ""
val symbols = "abcdefghijklmnopqrstuvwxyz".toCharArray()
val result = CharArray(a.size)
for ((i, n) in a.withIndex()) {
if (n !in 0..25)
throw IllegalArgumentException("${a.contentToString()} contains an invalid number")
result[i] = symbols[n]
if (n == 0) continue
for (j in n - 1 downTo 0) symbols[j + 1] = symbols[j]
symbols[0] = result[i]
}
return result.joinToString("")
}
fun main(args: Array<String>) {
val strings = arrayOf("broood", "bananaaa", "hiphophiphop")
val encoded = Array<IntArray?>(strings.size) { null }
for ((i, s) in strings.withIndex()) {
encoded[i] = encode(s)
println("${s.padEnd(12)} -> ${encoded[i]!!.contentToString()}")
}
println()
val decoded = Array<String?>(encoded.size) { null }
for ((i, a) in encoded.withIndex()) {
decoded[i] = decode(a!!)
print("${a.contentToString().padEnd(38)} -> ${decoded[i]!!.padEnd(12)}")
println(" -> ${if (decoded[i] == strings[i]) "correct" else "incorrect"}")
}
}
- Output:
broood -> [1, 17, 15, 0, 0, 5] bananaaa -> [1, 1, 13, 1, 1, 1, 0, 0] hiphophiphop -> [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] [1, 17, 15, 0, 0, 5] -> broood -> correct [1, 1, 13, 1, 1, 1, 0, 0] -> bananaaa -> correct [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] -> hiphophiphop -> correct
-- Return table of the alphabet in lower case
function getAlphabet ()
local letters = {}
for ascii = 97, 122 do table.insert(letters, string.char(ascii)) end
return letters
end
-- Move the table value at ind to the front of tab
function moveToFront (tab, ind)
local toMove = tab[ind]
for i = ind - 1, 1, -1 do tab[i + 1] = tab[i] end
tab[1] = toMove
end
-- Perform move-to-front encoding on input
function encode (input)
local symbolTable, output, index = getAlphabet(), {}
for pos = 1, #input do
for k, v in pairs(symbolTable) do
if v == input:sub(pos, pos) then index = k end
end
moveToFront(symbolTable, index)
table.insert(output, index - 1)
end
return table.concat(output, " ")
end
-- Perform move-to-front decoding on input
function decode (input)
local symbolTable, output = getAlphabet(), ""
for num in input:gmatch("%d+") do
output = output .. symbolTable[num + 1]
moveToFront(symbolTable, num + 1)
end
return output
end
-- Main procedure
local testCases, output = {"broood", "bananaaa", "hiphophiphop"}
for _, case in pairs(testCases) do
output = encode(case)
print("Original string: " .. case)
print("Encoded: " .. output)
print("Decoded: " .. decode(output))
print()
end
- Output:
Original string: broood Encoded: 1 17 15 0 0 5 Decoded: broood Original string: bananaaa Encoded: 1 1 13 1 1 1 0 0 Decoded: bananaaa Original string: hiphophiphop Encoded: 7 8 15 2 15 2 2 3 2 2 3 2 Decoded: hiphophiphop
edit
In Encode$() we use a string of parameters (function Quote$() make this)
Function Param() get the string with parameters and place it in code (inline).
In Decode$ we use current stack (first we flush to ensure that isn't some other arguments on it, M2000 has no signature control over the call of user functions, we can place anything)
For deleting and inserting characters in a string we use Insert. Insert of "" in a place of 1 char means delete it. So Insert k, 1 SymbolTable$="" means that in k position, for one char we place empty string.
To extract information to clipboard we use global variables, is handy;
Number pop a number from stack of values, if no number found then raise error.
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- Output:
broood True bananaaa True hiphophiphop True
From clipboard
b 1 bacdefghijklmnopqrstuvwxyz r 1,17 rbacdefghijklmnopqstuvwxyz o 1,17,15 orbacdefghijklmnpqstuvwxyz o 1,17,15,0 orbacdefghijklmnpqstuvwxyz o 1,17,15,0,0 orbacdefghijklmnpqstuvwxyz d 1,17,15,0,0,5 dorbacefghijklmnpqstuvwxyz 1 b b bacdefghijklmnopqrstuvwxyz 17 r br rbacdefghijklmnopqstuvwxyz 15 o bro orbacdefghijklmnpqstuvwxyz 0 o broo orbacdefghijklmnpqstuvwxyz 0 o brooo orbacdefghijklmnpqstuvwxyz 5 d broood dorbacefghijklmnpqstuvwxyz b 1 bacdefghijklmnopqrstuvwxyz a 1,1 abcdefghijklmnopqrstuvwxyz n 1,1,13 nabcdefghijklmopqrstuvwxyz a 1,1,13,1 anbcdefghijklmopqrstuvwxyz n 1,1,13,1,1 nabcdefghijklmopqrstuvwxyz a 1,1,13,1,1,1 anbcdefghijklmopqrstuvwxyz a 1,1,13,1,1,1,0 anbcdefghijklmopqrstuvwxyz a 1,1,13,1,1,1,0,0 anbcdefghijklmopqrstuvwxyz 1 b b bacdefghijklmnopqrstuvwxyz 1 a ba abcdefghijklmnopqrstuvwxyz 13 n ban nabcdefghijklmopqrstuvwxyz 1 a bana anbcdefghijklmopqrstuvwxyz 1 n banan nabcdefghijklmopqrstuvwxyz 1 a banana anbcdefghijklmopqrstuvwxyz 0 a bananaa anbcdefghijklmopqrstuvwxyz 0 a bananaaa anbcdefghijklmopqrstuvwxyz h 7 habcdefgijklmnopqrstuvwxyz i 7,8 ihabcdefgjklmnopqrstuvwxyz p 7,8,15 pihabcdefgjklmnoqrstuvwxyz h 7,8,15,2 hpiabcdefgjklmnoqrstuvwxyz o 7,8,15,2,15 ohpiabcdefgjklmnqrstuvwxyz p 7,8,15,2,15,2 pohiabcdefgjklmnqrstuvwxyz h 7,8,15,2,15,2,2 hpoiabcdefgjklmnqrstuvwxyz i 7,8,15,2,15,2,2,3 ihpoabcdefgjklmnqrstuvwxyz p 7,8,15,2,15,2,2,3,2 pihoabcdefgjklmnqrstuvwxyz h 7,8,15,2,15,2,2,3,2,2 hpioabcdefgjklmnqrstuvwxyz o 7,8,15,2,15,2,2,3,2,2,3 ohpiabcdefgjklmnqrstuvwxyz p 7,8,15,2,15,2,2,3,2,2,3,2 pohiabcdefgjklmnqrstuvwxyz 7 h h habcdefgijklmnopqrstuvwxyz 8 i hi ihabcdefgjklmnopqrstuvwxyz 15 p hip pihabcdefgjklmnoqrstuvwxyz 2 h hiph hpiabcdefgjklmnoqrstuvwxyz 15 o hipho ohpiabcdefgjklmnqrstuvwxyz 2 p hiphop pohiabcdefgjklmnqrstuvwxyz 2 h hiphoph hpoiabcdefgjklmnqrstuvwxyz 3 i hiphophi ihpoabcdefgjklmnqrstuvwxyz 2 p hiphophip pihoabcdefgjklmnqrstuvwxyz 2 h hiphophiph hpioabcdefgjklmnqrstuvwxyz 3 o hiphophipho ohpiabcdefgjklmnqrstuvwxyz 2 p hiphophiphop pohiabcdefgjklmnqrstuvwxyz
mtf[word_]:=Module[{f,f2,p,q},
f[{output_,symList_},next_]:=Module[{index},index=Position[symList,next][[1,1]]-1;
{output~Append~index,Prepend[Delete[symList,index+1],next]}];
p=Fold[f,{{},CharacterRange["a","z"]},Characters[ToString[word]]][[1]];
f2[{output_,symList_},next_]:=Module[{index},index=symList[[next+1]];
{output~Append~index,Prepend[DeleteCases[symList,ToString[index]],index]}];
q=Fold[f2,{{},CharacterRange["a","z"]},p][[1]];
Print["'", word,"' encodes to: ",p, " - " ,p," decodes to: '",StringJoin@q,"' - Input equals Output: " ,word===StringJoin@q];]
Testing out the function:
mtf /@ {"broood", "bananaaa", "hiphophiphop"}
- Output:
'broood' encodes to: {1,17,15,0,0,5} - {1,17,15,0,0,5} decodes to: 'broood' - Input equals Output: True
'bananaaa' encodes to: {1,1,13,1,1,1,0,0} - {1,1,13,1,1,1,0,0} decodes to: 'bananaaa' - Input equals Output: True
'hiphophiphop' encodes to: {7,8,15,2,15,2,2,3,2,2,3,2} - {7,8,15,2,15,2,2,3,2,2,3,2} decodes to: 'hiphophiphop' - Input equals Output: True
function testMTF
symTable = 'abcdefghijklmnopqrstuvwxyz';
inStr = {'broood' 'bananaaa' 'hiphophiphop'};
for k = 1:length(inStr)
outArr = encodeMTF(inStr{k}, symTable);
outStr = decodeMTF(outArr, symTable);
fprintf('%s: [ %s]\n', inStr{k}, sprintf('%d ', outArr))
fprintf('%scorrectly decoded to %s\n', char('in'.*~strcmp(outStr, inStr{k})), outStr)
end
end
function arr = encodeMTF(str, symTable)
n = length(str);
arr = zeros(1, n);
for k = 1:n
arr(k) = find(str(k) == symTable, 1);
symTable = [symTable(arr(k)) symTable(1:arr(k)-1) symTable(arr(k)+1:end)];
end
arr = arr-1; % Change to zero-indexed array
end
function str = decodeMTF(arr, symTable)
arr = arr+1; % Change to one-indexed array
n = length(arr);
str = char(zeros(1, n));
for k = 1:n
str(k) = symTable(arr(k));
symTable = [symTable(arr(k)) symTable(1:arr(k)-1) symTable(arr(k)+1:end)];
end
end
- Output:
broood: [ 1 17 15 0 0 5 ] correctly decoded to broood bananaaa: [ 1 1 13 1 1 1 0 0 ] correctly decoded to bananaaa hiphophiphop: [ 7 8 15 2 15 2 2 3 2 2 3 2 ] correctly decoded to hiphophiphop
main :: [sys_message]
main = [Stdout (lay (map test ["broood", "bananaaa", "hiphophiphop"]))]
test :: [char]->[char]
test str = str ++ " -> " ++ show encoded ++ " -> " ++ decoded ++ result
where alph = "abcdefghijklmnopqrstuvwxyz"
encoded = enc alph str
decoded = dec alph encoded
result = " (ok)", if str == decoded
result = " (fail)", otherwise
enc :: [*]->[*]->[num]
enc symtab [] = []
enc symtab (x:xs) = find x symtab : enc (movetofront x symtab) xs
dec :: [*]->[num]->[*]
dec symtab [] = []
dec symtab (x:xs) = c : dec (movetofront c symtab) xs where c = symtab ! x
movetofront :: *->[*]->[*]
movetofront x xs = x:remove x xs
remove :: *->[*]->[*]
remove x [] = []
remove x (x:xs) = remove x xs
remove x (y:xs) = y:remove x xs
find :: *->[*]->num
find x (x:xs) = 0
find x (y:xs) = 1 + find x xs- Output:
broood -> [1,17,15,0,0,5] -> broood (ok) bananaaa -> [1,1,13,1,1,1,0,0] -> bananaaa (ok) hiphophiphop -> [7,8,15,2,15,2,2,3,2,2,3,2] -> hiphophiphop (ok)
import algorithm, sequtils, strformat
const SymbolTable = toSeq('a'..'z')
func encode(s: string): seq[int] =
var symtable: seq[char] = SymbolTable
for c in s:
let idx = symtable.find(c)
result.add idx
symtable.rotateLeft(0..idx, -1)
func decode(s: seq[int]): string =
var symtable = SymbolTable
for idx in s:
result.add symtable[idx]
symtable.rotateLeft(0..idx, -1)
for word in ["broood", "babanaaa", "hiphophiphop"]:
let encoded = word.encode()
let decoded = encoded.decode()
let status = if decoded == word: "correctly" else: "incorrectly"
echo &"'{word}' encodes to {encoded} which {status} decodes to '{decoded}'."
- Output:
'broood' encodes to @[1, 17, 15, 0, 0, 5] which correctly decodes to 'broood'. 'babanaaa' encodes to @[1, 1, 1, 1, 13, 1, 0, 0] which correctly decodes to 'babanaaa'. 'hiphophiphop' encodes to @[7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] which correctly decodes to 'hiphophiphop'.
const
SymbolTable = Lst('a'..'z');
function encode(s: string): list<integer>;
begin
result := new List<integer>;
var symtable := SymbolTable;
foreach var c in s do
begin
var idx := symtable.IndexOf(c);
result.add(idx);
symtable.RemoveAt(idx);
symtable.Insert(0, c);
end;
end;
function decode(s: list<integer>): string;
begin
var symtable := SymbolTable;
foreach var idx in s do
begin
var c := symtable[idx];
result += c;
symtable.RemoveAt(idx);
symtable.Insert(0, c);
end;
end;
begin
foreach var word in ['broood', 'babanaaa', 'hiphophiphop'] do
begin
var encoded := encode(word);
var decoded := decode(encoded);
var status := if decoded = word then 'correctly' else 'incorrectly';
println(word, 'encodes to', encoded, 'which', status, 'decodes to', decoded);
end;
end.
- Output:
broood encodes to [1,17,15,0,0,5] which correctly decodes to broood babanaaa encodes to [1,1,1,1,13,1,0,0] which correctly decodes to babanaaa hiphophiphop encodes to [7,8,15,2,15,2,2,3,2,2,3,2] which correctly decodes to hiphophiphop
use strict;
use warnings;
sub encode {
my ($str) = @_;
my $table = join '', 'a' .. 'z';
map {
$table =~ s/(.*?)$_/$_$1/ or die;
length($1);
} split //, $str;
}
sub decode {
my $table = join '', 'a' .. 'z';
join "", map {
$table =~ s/(.{$_})(.)/$2$1/ or die;
$2;
} @_;
}
for my $test ( qw(broood bananaaa hiphophiphop) ) {
my @encoded = encode($test);
print "$test: @encoded\n";
my $decoded = decode(@encoded);
print "in" x ( $decoded ne $test );
print "correctly decoded to $decoded\n";
}
- Output:
broood: 1 17 15 0 0 5 correctly decoded to broood bananaaa: 1 1 13 1 1 1 0 0 correctly decoded to bananaaa hiphophiphop: 7 8 15 2 15 2 2 3 2 2 3 2 correctly decoded to hiphophiphop
Equivalent longhand versions of the symtab reordering left in as comments
with javascript_semantics function encode(string s) string symtab = "abcdefghijklmnopqrstuvwxyz" sequence res = {} for i=1 to length(s) do integer ch = s[i], k = find(ch,symtab) res &= k-1 -- for j=k to 2 by -1 do -- symtab[j] = symtab[j-1] -- end for -- symtab[1] = ch symtab[1..k] = ch&symtab[1..k-1] end for return res end function function decode(sequence s) string symtab = "abcdefghijklmnopqrstuvwxyz" string res = "" for i=1 to length(s) do integer k = s[i]+1 integer ch = symtab[k] res &= ch -- for j=k to 2 by -1 do -- symtab[j] = symtab[j-1] -- end for -- symtab[1] = ch symtab[1..k] = ch&symtab[1..k-1] end for return res end function procedure test(string s) sequence e = encode(s) string d = decode(e) ?{s,e,d,{"**ERROR**","ok"}[(s=d)+1]} end procedure test("broood") test("bananaaa") test("hiphophiphop")
- Output:
{"broood",{1,17,15,0,0,5},"broood","ok"}
{"bananaaa",{1,1,13,1,1,1,0,0},"bananaaa","ok"}
{"hiphophiphop",{7,8,15,2,15,2,2,3,2,2,3,2},"hiphophiphop","ok"}
<?php
function symbolTable() {
$symbol = array();
for ($c = ord('a') ; $c <= ord('z') ; $c++) {
$symbol[$c - ord('a')] = chr($c);
}
return $symbol;
}
function mtfEncode($original, $symbol) {
$encoded = array();
for ($i = 0 ; $i < strlen($original) ; $i++) {
$char = $original[$i];
$position = array_search($char, $symbol);
$encoded[] = $position;
$mtf = $symbol[$position];
unset($symbol[$position]);
array_unshift($symbol, $mtf);
}
return $encoded;
}
function mtfDecode($encoded, $symbol) {
$decoded = '';
foreach ($encoded AS $position) {
$char = $symbol[$position];
$decoded .= $char;
unset($symbol[$position]);
array_unshift($symbol, $char);
}
return $decoded;
}
foreach (array('broood', 'bananaaa', 'hiphophiphop') AS $original) {
$encoded = mtfEncode($original, symbolTable());
$decoded = mtfDecode($encoded, symbolTable());
echo
$original,
' -> [', implode(',', $encoded), ']',
' -> ', $decoded,
' : ', ($original === $decoded ? 'OK' : 'Error'),
PHP_EOL;
}
- Output:
broood -> [1,17,15,0,0,5] -> broood : OK bananaaa -> [1,1,13,1,1,1,0,0] -> bananaaa : OK hiphophiphop -> [7,8,15,2,15,2,2,3,2,2,3,2] -> hiphophiphop : OK
Picat has 1-based index so some adjustments was necessary.
import util.
go =>
Strings = ["broood", "bananaaa", "hiphophiphop"],
foreach(String in Strings)
check(String)
end,
nl.
% adjustments to 1-based index
encode(String) = [Pos,Table] =>
Table = "abcdefghijklmnopqrstuvwxyz",
Pos = [],
Len = String.length,
foreach({C,I} in zip(String,1..Len))
Pos := Pos ++ [find_first_of(Table,C)-1],
if Len > I then
Table := [C] ++ delete(Table,C)
end
end.
decode(Pos) = String =>
Table = "abcdefghijklmnopqrstuvwxyz",
String = [],
foreach(P in Pos)
C = Table[P+1],
Table := [C] ++ delete(Table,C),
String := String ++ [C]
end.
% Check the result
check(String) =>
[Pos,Table] = encode(String),
String2 = decode(Pos),
if length(String) < 100 then
println(pos=Pos),
println(table=Table),
println(string2=String2)
else
printf("String is too long to print (%d chars)\n", length(String))
end,
println(cond(String != String2, "not ", "") ++ "same"),
nl.- Output:
pos = [1,17,15,0,0,5] table = orbacdefghijklmnpqstuvwxyz string2 = broood same pos = [1,1,13,1,1,1,0,0] table = anbcdefghijklmopqrstuvwxyz string2 = bananaaa same pos = [7,8,15,2,15,2,2,3,2,2,3,2] table = ohpiabcdefgjklmnqrstuvwxyz string2 = hiphophiphop same
(de encode (Str)
(let Table (chop "abcdefghijklmnopqrstuvwxyz")
(mapcar
'((C)
(dec
(prog1
(index C Table)
(rot Table @) ) ) )
(chop Str) ) ) )
(de decode (Lst)
(let Table (chop "abcdefghijklmnopqrstuvwxyz")
(pack
(mapcar
'((N)
(prog1
(get Table (inc 'N))
(rot Table N) ) )
Lst ) ) ) )Test:
(test (1 17 15 0 0 5)
(encode "broood") )
(test "broood"
(decode (1 17 15 0 0 5)) )
(test (1 1 13 1 1 1 0 0)
(encode "bananaaa") )
(test "bananaaa"
(decode (1 1 13 1 1 1 0 0)) )
(test (7 8 15 2 15 2 2 3 2 2 3 2)
(encode "hiphophiphop") )
(test "hiphophiphop"
(decode (7 8 15 2 15 2 2 3 2 2 3 2)) )*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;- 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
100H:
BDOS: PROCEDURE (FN,ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; GO TO 0; END EXIT;
PRINT: PROCEDURE (STR); DECLARE STR ADDRESS; CALL BDOS(9, STR); END PRINT;
PRINT$NUM: PROCEDURE (N);
DECLARE N ADDRESS, I BYTE;
DECLARE S (6) BYTE INITIAL ('.....$');
I = 5;
DIGIT: DO;
S(I := I-1) = '0' + N MOD 10;
IF (N := N/10) > 0 THEN GO TO DIGIT;
END;
CALL PRINT(.S(I));
END PRINT$NUM;
FIND: PROCEDURE (STR, CHR) ADDRESS;
DECLARE STR ADDRESS, CHR BYTE;
DECLARE S BASED STR BYTE, I ADDRESS;
I = 0;
DO WHILE S(I) <> CHR; I = I+1; END;
RETURN I;
END FIND;
MOVE$TO$FRONT: PROCEDURE (SYMTAB, SYM);
DECLARE SYMTAB ADDRESS, SYM BYTE, TMP BYTE;
DECLARE S BASED SYMTAB BYTE, I ADDRESS;
I = FIND(SYMTAB, SYM);
DO WHILE I>0; S(I) = S(I := I-1); END;
S(0) = SYM;
END MOVE$TO$FRONT;
COPY$STRING: PROCEDURE (INSTR, OUTSTR);
DECLARE (INSTR, OUTSTR) ADDRESS;
DECLARE (I BASED INSTR, O BASED OUTSTR) BYTE;
DO WHILE I <> '$';
O = I;
INSTR = INSTR + 1;
OUTSTR = OUTSTR + 1;
END;
O = '$';
END COPY$STRING;
STR$LEN: PROCEDURE (STR) ADDRESS;
DECLARE STR ADDRESS;
RETURN FIND(STR, '$');
END STR$LEN;
STR$EQ: PROCEDURE (STR1, STR2) BYTE;
DECLARE (STR1, STR2) ADDRESS;
DECLARE (S1 BASED STR1, S2 BASED STR2) BYTE;
DECLARE I ADDRESS;
I = 0;
DO WHILE S1(I) = S2(I) AND S1(I) <> '$'; I=I+1; END;
RETURN S1(I) = S2(I);
END STR$EQ;
ENCODE: PROCEDURE (STR, SYMTAB, RESULT);
DECLARE (STR, SYMTAB, RESULT) ADDRESS;
DECLARE S BASED STR BYTE, R BASED RESULT BYTE, I ADDRESS;
DECLARE TEMP$SYMTAB (256) BYTE;
CALL COPY$STRING(SYMTAB, .TEMP$SYMTAB);
DO I=0 TO STR$LEN(STR) - 1;
R(I) = FIND(.TEMP$SYMTAB, S(I));
CALL MOVE$TO$FRONT(.TEMP$SYMTAB, S(I));
END;
END ENCODE;
DECODE: PROCEDURE (ARR, SZ, SYMTAB, RESULT);
DECLARE (ARR, SZ, SYMTAB, RESULT) ADDRESS;
DECLARE N BASED ARR BYTE, R BASED RESULT BYTE, I ADDRESS;
DECLARE TEMP$SYMTAB (256) BYTE;
CALL COPY$STRING(SYMTAB, .TEMP$SYMTAB);
DO I=0 TO SZ-1;
R(I) = TEMP$SYMTAB(N(I));
CALL MOVE$TO$FRONT(.TEMP$SYMTAB, R(I));
END;
R(SZ) = '$';
END DECODE;
PRINT$ARR: PROCEDURE (ARR, SZ);
DECLARE (ARR, SZ) ADDRESS;
DECLARE N BASED ARR BYTE, I ADDRESS;
DO I=0 TO SZ-1;
CALL PRINT$NUM(N(I));
CALL PRINT(.' $');
END;
END PRINT$ARR;
TEST: PROCEDURE (STR);
DECLARE STR ADDRESS, SZ ADDRESS;
DECLARE ENC$ARR (256) BYTE;
DECLARE SYMTAB (27) BYTE INITIAL ('ABCDEFGHIJKLMNOPQRSTUVWYXZ$');
DECLARE DEC$STR (256) BYTE;
SZ = STR$LEN(STR);
CALL PRINT(STR);
CALL PRINT(.' -> $');
CALL ENCODE(STR, .SYMTAB, .ENC$ARR);
CALL PRINT$ARR(.ENC$ARR, SZ);
CALL PRINT(.'-> $');
CALL DECODE(.ENC$ARR, SZ, .SYMTAB, .DEC$STR);
CALL PRINT(.DEC$STR);
IF STR$EQ(STR, .DEC$STR)
THEN CALL PRINT(.' (OK)$');
ELSE CALL PRINT(.' (FAIL)$');
CALL PRINT(.(13,10,'$'));
END TEST;
CALL TEST(.'BROOOD$');
CALL TEST(.'BANANAAA$');
CALL TEST(.'HIPHOPHIPHOP$');
CALL EXIT;
EOF- Output:
BROOOD -> 1 17 15 0 0 5 -> BROOOD (OK) BANANAAA -> 1 1 13 1 1 1 0 0 -> BANANAAA (OK) HIPHOPHIPHOP -> 7 8 15 2 15 2 2 3 2 2 3 2 -> HIPHOPHIPHOP (OK)
local fmt = require "fmt"
require "table2"
local function encode(s)
if s == "" then return {} end
local symbols = "abcdefghijklmnopqrstuvwxyz":split("")
local result = table.rep(#s, 0)
for i = 1, #s do
local c = s[i]
local index = symbols:findindex(|ch| -> ch == c)
if !index then error($"{s} contains a non-alphabetic character") end
result[i] = index
if index > 1 then
for k = index - 1, 1, -1 do symbols[k + 1] = symbols[k] end
symbols[1] = c
end
end
return result
end
local function decode(a)
if #a == 0 then return "" end
local symbols = "abcdefghijklmnopqrstuvwxyz":split("")
local result = table.rep(#a, "")
local i = 1
for a as n do
if n < 1 or n > 26 then error($"{fmt.format("%,s", a)} contains an invalid number") end
result[i] = symbols[n]
if n > 1 then
for j = n - 1, 1, -1 do symbols[j + 1] = symbols[j] end
symbols[1] = result[i]
end
i += 1
end
return result:concat("")
end
local strings = {"broood", "bananaaa", "hiphophiphop"}
local encoded = table.create(#strings)
for i, s in strings do
encoded[i] = encode(s)
fmt.print("%-12s -> %,s", s, encoded[i])
end
print()
local decoded = table.create(#encoded)
i = 1
for encoded as a do
decoded[i] = decode(a)
local correct = (decoded[i] == strings[i]) ? "correct" : "incorrect"
fmt.print("%,-38s -> %-12s -> %s", a, decoded[i], correct)
i += 1
end
- Output:
broood -> {2, 18, 16, 1, 1, 6}
bananaaa -> {2, 2, 14, 2, 2, 2, 1, 1}
hiphophiphop -> {8, 9, 16, 3, 16, 3, 3, 4, 3, 3, 4, 3}
{2, 18, 16, 1, 1, 6} -> broood -> correct
{2, 2, 14, 2, 2, 2, 1, 1} -> bananaaa -> correct
{8, 9, 16, 3, 16, 3, 3, 4, 3, 3, 4, 3} -> hiphophiphop -> correct
Function Test-MTF
{
[CmdletBinding()]
Param
(
[Parameter(Mandatory=$true,Position=0)]
[string]$word,
[Parameter(Mandatory=$false)]
[string]$SymbolTable = 'abcdefghijklmnopqrstuvwxyz'
)
Begin
{
Function Encode
{
Param
(
[Parameter(Mandatory=$true,Position=0)]
[string]$word,
[Parameter(Mandatory=$false)]
[string]$SymbolTable = 'abcdefghijklmnopqrstuvwxyz'
)
foreach ($letter in $word.ToCharArray())
{
$index = $SymbolTable.IndexOf($letter)
$prop = [ordered]@{
Input = $letter
Output = [int]$index
SymbolTable = $SymbolTable
}
New-Object PSobject -Property $prop
$SymbolTable = $SymbolTable.Remove($index,1).Insert(0,$letter)
}
}
Function Decode
{
Param
(
[Parameter(Mandatory=$true,Position=0)]
[int[]]$index,
[Parameter(Mandatory=$false)]
[string]$SymbolTable = 'abcdefghijklmnopqrstuvwxyz'
)
foreach ($i in $index)
{
#Write-host $i -ForegroundColor Red
$letter = $SymbolTable.Chars($i)
$prop = [ordered]@{
Input = $i
Output = $letter
SymbolTable = $SymbolTable
}
New-Object PSObject -Property $prop
$SymbolTable = $SymbolTable.Remove($i,1).Insert(0,$letter)
}
}
}
Process
{
#Encoding
Write-Host "Encoding $word" -NoNewline
$Encoded = (Encode -word $word).output
Write-Host -NoNewline ": $($Encoded -join ',')"
#Decoding
Write-Host "`nDecoding $($Encoded -join ',')" -NoNewline
$Decoded = (Decode -index $Encoded).output -join ''
Write-Host -NoNewline ": $Decoded`n"
}
End{}
}
- Output:
Test-MTF -word broood Test-MTF -word bananaaa Test-MTF -word hiphophiphop Encoding broood: 1,17,15,0,0,5 Decoding 1,17,15,0,0,5: broood Encoding bananaaa: 1,1,13,1,1,1,0,0 Decoding 1,1,13,1,1,1,0,0: bananaaa Encoding hiphophiphop: 7,8,15,2,15,2,2,3,2,2,3,2 Decoding 7,8,15,2,15,2,2,3,2,2,3,2: hiphophiphop
Python: Procedural
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!'
- 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'
Python: Functional
From the procedural version note that through the encoding or decoding loops both the final output is accumulated as well as the symbol table being rearranged.
For the functional forms a 2-item list of output to be accumulated and symboltable manipulation is calculated then only the former accumulated as the later works to transform the symbol table in-place.
def m2f_e(s, st):
return [[st.index(ch), st.insert(0, st.pop(st.index(ch)))][0] for ch in s]
def m2f_d(sq, st):
return ''.join([st[i], st.insert(0, st.pop(i))][0] for i in sq)
ST = list('abcdefghijklmnopqrstuvwxyz')
for s in ['broood', 'bananaaa', 'hiphophiphop']:
encode = m2f_e(s, ST[::])
print('%14r encodes to %r' % (s, encode), end=', ')
decode = m2f_d(encode, ST[::])
print('decodes back to %r' % decode)
assert s == decode, 'Whoops!'
- Output:
Similar to that of the procedural version above.
[ []
26 times
[ char a i^ +
join ] ] constant is symbols ( --> $ )
[ [] symbols rot
witheach
[ over find
tuck pluck
swap join
dip join ]
drop ] is encode ( $ --> [ )
[ $ "" symbols rot
witheach
[ pluck
dup rot join
dip join ]
drop ] is decode ( [ --> $ )
[ dup echo$
say " --> "
dup encode
dup echo
say " --> "
decode
dup echo$
= iff
[ say " :-)" ]
else
[ say " :-(" ]
cr cr ] is task ( $ --> )
$ "broood bananaaa hiphophiphop"
nest$ witheach task- 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 :-)
encodeMTF <- function(str, symtable = letters) {
encode <- function(ch) {
r <- which(symtable == ch)
symtable <<- c(ch, symtable[-r])
return(r)
}
sapply(strsplit(str, "")[[1]], encode)
}
decodeMTF <- function(arr, symtable = letters) {
decode <- function(i) {
r <- symtable[i]
symtable <<- c(r, symtable[-i])
return(r)
}
paste(sapply(arr, decode), collapse = "")
}
testset <- c("broood", "bananaaa", "hiphophiphop")
encoded <- lapply(testset, encodeMTF)
decoded <- mapply(decodeMTF, encoded)
for (i in seq_along(testset)) {
cat("Test string:", testset[i], "\n -> Encoded:", paste(encoded[[i]], collapse = ", "), "\n -> Decoded:", decoded[i], "\n\n")
}
# Test if decoded strings equal original
all(sapply(seq_along(testset), function(i) identical(testset[i], decoded[i])))
- Output:
Test string: broood -> Encoded: 2, 18, 16, 1, 1, 6 -> Decoded: broood Test string: bananaaa -> Encoded: 2, 2, 14, 2, 2, 2, 1, 1 -> Decoded: bananaaa Test string: hiphophiphop -> Encoded: 8, 9, 16, 3, 16, 3, 3, 4, 3, 3, 4, 3 -> Decoded: hiphophiphop [1] TRUE
#lang racket
(define default-symtab "abcdefghijklmnopqrstuvwxyz")
(define (move-to-front:encode in (symtab default-symtab))
(define inner-encode
(match-lambda**
[((? string? (app string->list in)) st acc) ; make input all listy
(inner-encode in st acc)]
[(in (? string? (app string->list st)) acc) ; make symtab all listy
(inner-encode in st acc)]
[((list) _ (app reverse rv)) ; nothing more to encode
rv]
[((list a tail ...) (list left ... a right ...) acc) ; encode and recur
(inner-encode tail `(,a ,@left ,@right) (cons (length left) acc))]))
(inner-encode in symtab null))
(define (move-to-front:decode in (symtab default-symtab))
(define inner-decode
(match-lambda**
[(in (? string? (app string->list st)) acc) ; make symtab all listy
(inner-decode in st acc)]
[((list) _ (app (compose list->string reverse) rv)) ; nothing more to encode
rv]
[((list a tail ...) symbols acc) ; decode and recur
(match/values
(split-at symbols a)
[(l (cons ra rd))
(inner-decode tail (cons ra (append l rd)) (cons ra acc))])]))
(inner-decode in symtab null))
(module+ test
;; Test against the example in the task
(require rackunit)
(check-equal? (move-to-front:encode "broood") '(1 17 15 0 0 5))
(check-equal? (move-to-front:decode '(1 17 15 0 0 5)) "broood")
(check-equal? (move-to-front:decode (move-to-front:encode "broood")) "broood"))
(module+ main
(define (encode+decode-string str)
(define enc (move-to-front:encode str))
(define dec (move-to-front:decode enc))
(define crt (if (equal? dec str) "correctly" "incorrectly"))
(printf "~s encodes to ~s, which decodes ~s to ~s.~%" str enc crt dec))
(for-each encode+decode-string '("broood" "bananaaa" "hiphophiphop")))
- Output:
"broood" encodes to (1 17 15 0 0 5), which decodes "correctly" to "broood". "bananaaa" encodes to (1 1 13 1 1 1 0 0), which decodes "correctly" to "bananaaa". "hiphophiphop" encodes to (7 8 15 2 15 2 2 3 2 2 3 2), which decodes "correctly" to "hiphophiphop".
(formerly Perl 6)
sub encode ( Str $word ) {
my @sym = 'a' .. 'z';
gather for $word.comb -> $c {
die "Symbol '$c' not found in @sym" if $c eq @sym.none;
@sym[0 .. take (@sym ... $c).end] .= rotate(-1);
}
}
sub decode ( @enc ) {
my @sym = 'a' .. 'z';
[~] gather for @enc -> $pos {
take @sym[$pos];
@sym[0..$pos] .= rotate(-1);
}
}
use Test;
plan 3;
for <broood bananaaa hiphophiphop> -> $word {
my $enc = encode($word);
my $dec = decode($enc);
is $word, $dec, "$word.fmt('%-12s') ($enc[])";
}
- Output:
1..3 ok 1 - broood (1 17 15 0 0 5) ok 2 - bananaaa (1 1 13 1 1 1 0 0) ok 3 - hiphophiphop (7 8 15 2 15 2 2 3 2 2 3 2)
$ENTRY Go {
= <Show 'broood'>
<Show 'bananaaa'>
<Show 'hiphophiphop'>;
};
Alph {
= 'abcdefghijklmnopqrstuvwxyz';
};
Show {
e.X, <Encode (<Alph>) e.X>: e.Enc,
<Decode (<Alph>) e.Enc>: e.X
= <Prout e.X ' -> ' e.Enc ' -> ' e.X>;
e.X = <Prout 'Result of decode not equal to input'>;
};
Encode {
(e.Alph) = ;
(e.Alph) s.C e.X =
<Lookup s.C e.Alph>
<Encode (<MoveToFront s.C e.Alph>) e.X>;
};
Decode {
(e.Alph) = ;
(e.Alph) s.I e.X, <Item s.I e.Alph>: s.C =
s.C <Decode (<MoveToFront s.C e.Alph>) e.X>;
};
Lookup {
s.C e.X s.C e.Y, <Lenw e.X>: s.L e.X = s.L;
};
Item {
s.N e.X, <First <Add 1 s.N> e.X>: (e.Y s.C) e.Z = s.C;
};
MoveToFront {
s.C e.X s.C e.Y = s.C e.X e.Y;
};- 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
version 1
/* 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
- 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
version 2
Programming note: the two REXX statements that add/subtract one deal with the task's requirement that the symbol table be zero-indexed (the REXX language uses unity-based strings).
/*REXX program demonstrates the move─to─front algorithm encode/decode symbol table. */
parse arg xxx; if xxx='' then xxx= 'broood bananaaa hiphophiphop' /*use the default?*/
one= 1 /*(offset) for this task's requirement.*/
do j=1 for words(xxx); x= word(xxx, j) /*process a single word at a time. */
@= 'abcdefghijklmnopqrstuvwxyz'; @@= @ /*symbol table: the lowercase alphabet */
$= /*set the decode string to a null. */
do k=1 for length(x); z= substr(x, k, 1) /*encrypt a symbol in the word. */
_= pos(z, @); if _==0 then iterate /*the symbol position in symbol table. */
$= $ (_ - one); @= z || delstr(@, _, 1) /*(re─)adjust the symbol table string. */
end /*k*/ /* [↑] the move─to─front encoding. */
!= /*set the encode string to a null. */
do m=1 for words($); n= word($, m) + one /*decode the sequence table string. */
y= substr(@@, n, 1); != ! || y /*the decode symbol for the N word.*/
@@= y || delstr(@@, n, 1) /*rebuild the symbol table string. */
end /*m*/ /* [↑] the move─to─front decoding. */
say ' word: ' left(x, 20) "encoding:" left($, 35) word('wrong OK', 1 + (!==x) )
end /*j*/ /*stick a fork in it, we're all done. */
- output when using the default input:
word: broood encoding: 1 17 15 0 0 5 OK
word: bananaaa encoding: 1 1 13 1 1 1 0 0 OK
word: hiphophiphop encoding: 7 8 15 2 15 2 2 3 2 2 3 2 OK
# Project : Move-to-front algorithm
test("broood")
test("bananaaa")
test("hiphophiphop")
func encode(s)
symtab = "abcdefghijklmnopqrstuvwxyz"
res = ""
for i=1 to len(s)
ch = s[i]
k = substr(symtab, ch)
res = res + " " + (k-1)
for j=k to 2 step -1
symtab[j] = symtab[j-1]
next
symtab[1] = ch
next
return res
func decode(s)
s = str2list( substr(s, " ", nl) )
symtab = "abcdefghijklmnopqrstuvwxyz"
res = ""
for i=1 to len(s)
k = number(s[i]) + 1
ch = symtab[k]
res = res + " " + ch
for j=k to 2 step -1
symtab[j] = symtab[j-1]
next
symtab[1] = ch
next
return right(res, len(res)-2)
func test(s)
e = encode(s)
d = decode(e)
see "" + s + " => " + "(" + right(e, len(e) - 1) + ") " + " => " + substr(d, " ", "") + nlOutput:
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
« → s p
« « s n DUP SUB » 'n' s SIZE 1 -1 SEQ EVAL
p ROLL s SIZE →LIST REVLIST ∑LIST
» » 'MOV2F' STO
« → s
« { } "abcdefghijklmnopqrstuvxyz"
1 s SIZE FOR j
DUP s j DUP SUB POS
ROT OVER +
ROT ROT MOV2F
NEXT
DROP 1 -
» » '→M2F' STO
« 1 ADD → idx
« "" "abcdefghijklmnopqrstuvxyz"
1 idx SIZE FOR j
DUP idx j GET DUP SUB
ROT OVER +
ROT ROT OVER SWAP POS MOV2F
NEXT
DROP
» » 'M2F→' STO
« DUP →M2F
DUP2 M2F→ SAME "Ok" "KO" IFTE
3 →LIST
» 'TASK' STO
{ "broood" "bananaaa" "hiphophiphop" } 1 TASK DOLIST
- Output:
1: { { "broood" { 1 17 15 0 0 5 } "Ok" } { "bananaaa" { 1 1 13 1 1 1 0 0 } "Ok" } { "hiphophiphop" { 7 8 15 2 15 2 2 3 2 2 3 2 } "Ok" } }
Use a module as namespace:
module MoveToFront
ABC = ("a".."z").to_a.freeze
def self.encode(str)
ar = ABC.dup
str.chars.each_with_object([]) do |char, memo|
memo << (i = ar.index(char))
ar = m2f(ar,i)
end
end
def self.decode(indices)
ar = ABC.dup
indices.each_with_object("") do |i, str|
str << ar[i]
ar = m2f(ar,i)
end
end
private
def self.m2f(ar,i)
[ar.delete_at(i)] + ar
end
end
['broood', 'bananaaa', 'hiphophiphop'].each do |word|
p word == MoveToFront.decode(p MoveToFront.encode(p word))
end
- Output:
"broood" [1, 17, 15, 0, 0, 5] true "bananaaa" [1, 1, 13, 1, 1, 1, 0, 0] true "hiphophiphop" [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] true
fn main() {
let examples = vec!["broood", "bananaaa", "hiphophiphop"];
for example in examples {
let encoded = encode(example);
let decoded = decode(&encoded);
println!(
"{} encodes to {:?} decodes to {}",
example, encoded, decoded
);
}
}
fn get_symbols() -> Vec<u8> {
(b'a'..b'z').collect()
}
fn encode(input: &str) -> Vec<usize> {
input
.as_bytes()
.iter()
.fold((Vec::new(), get_symbols()), |(mut o, mut s), x| {
let i = s.iter().position(|c| c == x).unwrap();
let c = s.remove(i);
s.insert(0, c);
o.push(i);
(o, s)
})
.0
}
fn decode(input: &[usize]) -> String {
input
.iter()
.fold((Vec::new(), get_symbols()), |(mut o, mut s), x| {
o.push(s[*x]);
let c = s.remove(*x);
s.insert(0, c);
(o, s)
})
.0
.into_iter()
.map(|c| c as char)
.collect()
}
- Output:
broood encodes to [1, 17, 15, 0, 0, 5] decodes to broood bananaaa encodes to [1, 1, 13, 1, 1, 1, 0, 0] decodes to bananaaa hiphophiphop encodes to [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] decodes to hiphophiphop
package rosetta
import scala.annotation.tailrec
object MoveToFront {
/**
* Default radix
*/
private val R = 256
/**
* Default symbol table
*/
private def symbolTable = (0 until R).map(_.toChar).mkString
/**
* Apply move-to-front encoding using default symbol table.
*/
def encode(s: String): List[Int] = {
encode(s, symbolTable)
}
/**
* Apply move-to-front encoding using symbol table <tt>symTable</tt>.
*/
def encode(s: String, symTable: String): List[Int] = {
val table = symTable.toCharArray
@inline @tailrec def moveToFront(ch: Char, index: Int, tmpout: Char): Int = {
val tmpin = table(index)
table(index) = tmpout
if (ch != tmpin)
moveToFront(ch, index + 1, tmpin)
else {
table(0) = ch
index
}
}
@tailrec def encodeString(output: List[Int], s: List[Char]): List[Int] = s match {
case Nil => output
case x :: xs => {
encodeString(moveToFront(x, 0, table(0)) :: output, s.tail)
}
}
encodeString(Nil, s.toList).reverse
}
/**
* Apply move-to-front decoding using default symbol table.
*/
def decode(ints: List[Int]): String = {
decode(ints, symbolTable)
}
/**
* Apply move-to-front decoding using symbol table <tt>symTable</tt>.
*/
def decode(lst: List[Int], symTable: String): String = {
val table = symTable.toCharArray
@inline def moveToFront(c: Char, index: Int) {
for (i <- index-1 to 0 by -1)
table(i+1) = table(i)
table(0) = c
}
@tailrec def decodeList(output: List[Char], lst: List[Int]): List[Char] = lst match {
case Nil => output
case x :: xs => {
val c = table(x)
moveToFront(c, x)
decodeList(c :: output, xs)
}
}
decodeList(Nil, lst).reverse.mkString
}
def test(toEncode: String, symTable: String) {
val encoded = encode(toEncode, symTable)
println(toEncode + ": " + encoded)
val decoded = decode(encoded, symTable)
if (toEncode != decoded)
print("in")
println("correctly decoded to " + decoded)
}
}
/**
* Unit tests the <tt>MoveToFront</tt> data type.
*/
object RosettaCodeMTF extends App {
val symTable = "abcdefghijklmnopqrstuvwxyz"
MoveToFront.test("broood", symTable)
MoveToFront.test("bananaaa", symTable)
MoveToFront.test("hiphophiphop", symTable)
}
- Output:
broood: List(1, 17, 15, 0, 0, 5) correctly decoded to broood bananaaa: List(1, 1, 13, 1, 1, 1, 0, 0) correctly decoded to bananaaa hiphophiphop: List(7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2) correctly decoded to hiphophiphop
program move_to_front;
tests := ["broood", "bananaaa", "hiphophiphop"];
alph := "abcdefghijklmnopqrstuvwxyz";
loop for test in tests do
e := encode(test, alph);
d := decode(e, alph);
v := if test = d then "(ok)" else "(fail)" end;
print(test,"->",e,"->",d,v);
end loop;
proc encode(s, alph);
enc := [];
loop for c in s do
[i, j] := mark(alph, c);
alph := c + alph(..i-1) + alph(j+1..);
enc with:= i-1;
end loop;
return enc;
end proc;
proc decode(ls, alph);
s := "";
loop for i in ls do
c := alph(i + 1);
s +:= c;
alph := c + alph(..i) + alph(i+2..);
end loop;
return s;
end proc;
end program;- Output:
broood -> [1 17 15 0 0 5] -> broood (ok) bananaaa -> [1 1 13 1 1 1 0 0] -> bananaaa (ok) hiphophiphop -> [7 8 15 2 15 2 2 3 2 2 3 2] -> hiphophiphop (ok)
Implemented using regular expressions:
func encode(str) {
var table = ('a'..'z' -> join);
str.chars.map { |c|
var s = '';
table.sub!(Regex('(.*?)' + c), {|s1| s=s1; c + s1});
s.len;
}
}
func decode(nums) {
var table = ('a'..'z' -> join);
nums.map { |n|
var s = '';
table.sub!(Regex('(.{' + n + '})(.)'), {|s1, s2| s=s2; s2 + s1});
s;
}.join;
}
%w(broood bananaaa hiphophiphop).each { |test|
var encoded = encode(test);
say "#{test}: #{encoded}";
var decoded = decode(encoded);
print "in" if (decoded != test);
say "correctly decoded to #{decoded}";
}
Alternatively, implemented as a module, using arrays:
module MoveToFront {
define ABC = @("a".."z")
func m2f(ar,i) {
[ar.delete_index(i)] + ar
}
func encode(str) {
var ar = ABC+[]
gather {
str.each_char { |char|
take(var i = ar.index(char))
ar = m2f(ar, i);
}
}
}
func decode(indices) {
var ar = ABC+[]
gather {
indices.each { |i|
take ar[i];
ar = m2f(ar, i)
}
}.join
}
}
%w(broood bananaaa hiphophiphop).each { |test|
var encoded = MoveToFront::encode(test);
say "#{test}: #{encoded}";
var decoded = MoveToFront::decode(encoded);
print "in" if (decoded != test);
say "correctly decoded to #{decoded}";
}
- Output:
broood: 1 17 15 0 0 5 correctly decoded to broood bananaaa: 1 1 13 1 1 1 0 0 correctly decoded to bananaaa hiphophiphop: 7 8 15 2 15 2 2 3 2 2 3 2 correctly decoded to hiphophiphop
var str="broood"
var number:[Int]=[1,17,15,0,0,5]
//function to encode the string
func encode(st:String)->[Int]
{
var array:[Character]=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
var num:[Int]=[]
var temp:Character="a"
var i1:Int=0
for i in st.characters
{
for j in 0...25
{
if i==array[j]
{
num.append(j)
temp=array[j]
i1=j
while(i1>0)
{
array[i1]=array[i1-1]
i1=i1-1
}
array[0]=temp
}
}
}
return num
}
func decode(s:[Int])->[Character]
{
var st1:[Character]=[]
var alph:[Character]=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
var temp1:Character="a"
var i2:Int=0
for i in 0...s.character.count-1
{
i2=s[i]
st1.append(alph[i2])
temp1=alph[i2]
while(i2>0)
{
alph[i2]=alph[i2-1]
i2=i2-1
}
alph[0]=temp1
}
return st1
}
var encarr:[Int]=encode(st:str)
var decarr:[Character]=decode(s:number)
print(encarr)
print(decarr)
package require Tcl 8.6
oo::class create MoveToFront {
variable symbolTable
constructor {symbols} {
set symbolTable [split $symbols ""]
}
method MoveToFront {table index} {
list [lindex $table $index] {*}[lreplace $table $index $index]
}
method encode {text} {
set t $symbolTable
set r {}
foreach c [split $text ""] {
set i [lsearch -exact $t $c]
lappend r $i
set t [my MoveToFront $t $i]
}
return $r
}
method decode {numbers} {
set t $symbolTable
set r ""
foreach n $numbers {
append r [lindex $t $n]
set t [my MoveToFront $t $n]
}
return $r
}
}
MoveToFront create mtf "abcdefghijklmnopqrstuvwxyz"
foreach tester {"broood" "bananaaa" "hiphophiphop"} {
set enc [mtf encode $tester]
set dec [mtf decode $enc]
puts [format "'%s' encodes to %s. This decodes to '%s'. %s" \
$tester $enc $dec [expr {$tester eq $dec ? "Correct!" : "WRONG!"}]]
}
- Output:
'broood' encodes to 1 17 15 0 0 5. This decodes to 'broood'. Correct! 'bananaaa' encodes to 1 1 13 1 1 1 0 0. This decodes to 'bananaaa'. Correct! 'hiphophiphop' encodes to 7 8 15 2 15 2 2 3 2 2 3 2. This decodes to 'hiphophiphop'. Correct!
Mtf ← ⌅(
⊙⋅◌⍢(⊙(⊂⍜↻°⊂)⊸⊂⊙⤚⊗⊙⊙°⊂|>0⋅⋅⧻)[] +@a⇡26
| ⋅⋅∘⍢(⊃(∘|⊂⍜↻°⊂◌|˜⊂⊡◌)⊃⋅∘∘°⊂|>0⧻) ⊙(+@a⇡26 ""))
≡◇(&p$"_ _ _"⊸°Mtf⊸Mtf) {"broood""bananaa" "hiphopchipshop"}
- Output:
broood [1 17 15 0 0 5] broood bananaa [1 1 13 1 1 1 0] bananaa hiphopchipshop [7 8 15 2 15 2 6 3 4 3 18 3 5 3] hiphopchipshop
Function mtf_encode(s)
'create the array list and populate it with the initial symbol position
Set symbol_table = CreateObject("System.Collections.ArrayList")
For j = 97 To 122 'a to z in decimal.
symbol_table.Add Chr(j)
Next
output = ""
For i = 1 To Len(s)
char = Mid(s,i,1)
If i = Len(s) Then
output = output & symbol_table.IndexOf(char,0)
symbol_table.RemoveAt(symbol_table.LastIndexOf(char))
symbol_table.Insert 0,char
Else
output = output & symbol_table.IndexOf(char,0) & " "
symbol_table.RemoveAt(symbol_table.LastIndexOf(char))
symbol_table.Insert 0,char
End If
Next
mtf_encode = output
End Function
Function mtf_decode(s)
'break the function argument into an array
code = Split(s," ")
'create the array list and populate it with the initial symbol position
Set symbol_table = CreateObject("System.Collections.ArrayList")
For j = 97 To 122 'a to z in decimal.
symbol_table.Add Chr(j)
Next
output = ""
For i = 0 To UBound(code)
char = symbol_table(code(i))
output = output & char
If code(i) <> 0 Then
symbol_table.RemoveAt(symbol_table.LastIndexOf(char))
symbol_table.Insert 0,char
End If
Next
mtf_decode = output
End Function
'Testing the functions
wordlist = Array("broood","bananaaa","hiphophiphop")
For Each word In wordlist
WScript.StdOut.Write word & " encodes as " & mtf_encode(word) & " and decodes as " &_
mtf_decode(mtf_encode(word)) & "."
WScript.StdOut.WriteBlankLines(1)
Next
- Output:
broood encodes as 1 17 15 0 0 5 and decodes as broood. bananaaa encodes as 1 1 13 1 1 1 0 0 and decodes as bananaaa. hiphophiphop encodes as 7 8 15 2 15 2 2 3 2 2 3 2 and decodes as hiphophiphop.
import "./fmt" for Fmt
import "./seq" for Lst
var encode = Fn.new { |s|
if (s.isEmpty) return []
var symbols = "abcdefghijklmnopqrstuvwxyz".toList
var result = List.filled(s.count, 0)
var i = 0
for (c in s) {
var index = Lst.indexOf(symbols, c)
if (index == -1) Fiber.abort("%(s) contains a non-alphabetic character")
result[i] = index
if (index > 0) {
for (j in index-1..0) symbols[j + 1] = symbols[j]
symbols[0] = c
}
i = i + 1
}
return result
}
var decode = Fn.new { |a|
if (a.isEmpty) return ""
var symbols = "abcdefghijklmnopqrstuvwxyz".toList
var result = List.filled(a.count, "")
var i = 0
for (n in a) {
if (n < 0 || n > 25) Fiber.abort("%(a) contains an invalid number")
result[i] = symbols[n]
if (n > 0) {
for (j in n-1..0) symbols[j + 1] = symbols[j]
symbols[0] = result[i]
}
i = i + 1
}
return result.join()
}
var strings = ["broood", "bananaaa", "hiphophiphop"]
var encoded = List.filled(strings.count, null)
var i = 0
for (s in strings) {
encoded[i] = encode.call(s)
Fmt.print("$-12s -> $n", s, encoded[i])
i = i + 1
}
System.print()
var decoded = List.filled(encoded.count, null)
i = 0
for (a in encoded) {
decoded[i] = decode.call(a)
var correct = (decoded[i] == strings[i]) ? "correct" : "incorrect"
Fmt.print("$-38n -> $-12s -> $s", a, decoded[i], correct)
i = i + 1
}
- Output:
broood -> [1, 17, 15, 0, 0, 5] bananaaa -> [1, 1, 13, 1, 1, 1, 0, 0] hiphophiphop -> [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] [1, 17, 15, 0, 0, 5] -> broood -> correct [1, 1, 13, 1, 1, 1, 0, 0] -> bananaaa -> correct [7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2] -> hiphophiphop -> correct
!ys-0
# Move-to-front transform. Encode: for each symbol, emit its index in
# the table, then move it to the front. Decode reverses this with the
# same starting table. The round trip is the identity.
defn main():
each word qw(broood bananaaa hiphophiphop):
codes =: word:encode
back =: codes:decode
say: "$word -> $(codes:joins) -> $back"
defn- table():
alpha =: 'abcdefghijklmnopqrstuvwxyz'
vec: alpha
defn- encode(s):
loop tab table(), cs s:V, out []:
if cs:empty?:
then: out
else:
i =: pos(tab cs:first)
recur: bump(tab i), cs:rest, out.conj(i)
defn- decode(codes):
loop tab table(), is codes, out []:
if is:empty?:
then: out:join
else:
i =: is:first
recur: bump(tab i), is:rest, out.conj(tab.$i)
defn- pos(v x):
loop i 0:
if v.$i == x: i recur(i.++)
# Move the element at index i to the front of the table.
defn- bump(tab i):
c =: tab.$i
rest =: tab.take(i).concat(tab.drop(i.++))
vec: c.cons(rest)
- Output:
$ ys move-to-front-algorithm.ys 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
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
defer _ = gpa.deinit();
const examples = [_][]const u8{ "broood", "bananaaa", "hiphophiphop" };
for (examples) |example| {
const encoded = try encode(allocator, example);
defer allocator.free(encoded);
const decoded = try decode(allocator, encoded);
defer allocator.free(decoded);
std.debug.print("{s} encodes to {any} decodes to {s}\n", .{ example, encoded, decoded });
}
}
fn getSymbols(allocator: std.mem.Allocator) ![]u8 {
var symbols = std.ArrayList(u8).init(allocator);
errdefer symbols.deinit();
var c: u8 = 'a';
while (c <= 'z') : (c += 1) {
try symbols.append(c);
}
return symbols.toOwnedSlice();
}
fn encode(allocator: std.mem.Allocator, input: []const u8) ![]usize {
var output = std.ArrayList(usize).init(allocator);
errdefer output.deinit();
var symbols = try getSymbols(allocator);
defer allocator.free(symbols);
for (input) |byte| {
// Find position of the byte in symbols
var position: usize = 0;
for (symbols, 0..) |symbol, i| {
if (symbol == byte) {
position = i;
break;
}
}
// Remove the byte at the position
const char = symbols[position];
std.mem.copyForwards(u8, symbols[1..position + 1], symbols[0..position]);
symbols[0] = char;
try output.append(position);
}
return output.toOwnedSlice();
}
fn decode(allocator: std.mem.Allocator, input: []const usize) ![]u8 {
var output = std.ArrayList(u8).init(allocator);
errdefer output.deinit();
var symbols = try getSymbols(allocator);
defer allocator.free(symbols);
for (input) |position| {
try output.append(symbols[position]);
// Remove the byte at the position
const char = symbols[position];
std.mem.copyForwards(u8, symbols[1..position + 1], symbols[0..position]);
symbols[0] = char;
}
return output.toOwnedSlice();
}
- Output:
broood encodes to { 1, 17, 0, 0, 0, 0 } decodes to brrrrr
bananaaa encodes to { 1, 1, 13, 1, 1, 1, 0, 0 } decodes to bananaaa
hiphophiphop encodes to { 7, 8, 15, 0, 0, 0, 0, 1, 1, 0, 0, 0 } decodes to hipppppipppp
fcn encode(text){ //-->List
st:=["a".."z"].pump(Data); //"abcd..z" as byte array
text.reduce(fcn(st,c,sink){
n:=st.index(c); sink.write(n); st.del(n).insert(0,c); },st,sink:=L());
sink;
}Strings are immutable so we create a bit bucket (which is mutable) to hold the symbol table which can then be modified in place.
fcn decode(list){ //-->String
st:=["a".."z"].pump(String); //"abcd..z"
sink:=Sink(String);
list.reduce('wrap(st,n){ c:=st[n]; sink.write(c); c+st.del(n); },st);
sink.close();
}Here, we create a new symbol table each round as we would have to convert the byte we got from the bit bucket to string (so it is a wash garbage wise).
texts:=T("broood","bananaaa","hiphophiphop");
out:=texts.apply(encode);
texts.zipWith(fcn(t,e){ println(t,"-->",e) },out);
out.apply(decode).println();
texts.zipWith('==,out.apply(decode)).println();- Output:
broood-->L(1,17,15,0,0,5)
bananaaa-->L(1,1,13,1,1,1,0,0)
hiphophiphop-->L(7,8,15,2,15,2,2,3,2,2,3,2)
L("broood","bananaaa","hiphophiphop")
L(True,True,True)