Move-to-front algorithm: Difference between revisions

Given a symbol table of a ''zero-indexed'' array of all possible input symbols

[[wp:Move-to-front transform|this algorithm]] reversibly transforms a sequence

The transform in many cases acts to give frequently repeated input symbols

lower indices which is [[wp:Move-to-front_transform#Use_in_practical_data_compression_algorithms| useful in some compression algorithms]].

 

;Encoding algorithm:

move that symbol to the front of the symbol table

</pre>

 

;Decoding algorithm:

move that symbol to the front of the symbol table

</pre>

 

;Example:

 

|-

! Input

| 'orbacdefghijklmnpqstuvwxyz'

|}

 

Decoding the indices back to the original symbol order:

|-

! Input

| 'orbacdefghijklmnpqstuvwxyz'

|}

 

;Task:

 

<br>

<big> hiphophiphop </big>

 

<br><br>

 

=={{header|Ada}}==

 

 

procedure Move_To_Front is

Encode_Write_Check("bananaaa");

Encode_Write_Check("hiphophiphop");

 

{{out}}

'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!</pre>

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}

# note text pos is based from 0 #

PROC move to front = ( STRING text, INT text pos )STRING:

# ; test encode and decode( "zyxwvutsrqponmlkjihgfedcba" ) #

 

{{out}}

<pre>

hiphophiphop encodes to [ 7 8 15 2 15 2 2 3 2 2 3 2 ] which correctly decodes to "hiphophiphop"

</pre>

 

=={{header|AutoHotkey}}==

str := "abcdefghijklmnopqrstuvwxyz"

loop, parse, string

return string

}

loop, parse, testStrings, `,

Output .= A_LoopField "`t" MTF_Encode(A_LoopField) "`t" MTF_Decode(MTF_Encode(A_LoopField)) "`n"

MsgBox % Output

Outputs:<pre>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</pre>

 

=={{header|C}}==

#include<stdlib.h>

#include<string.h>

}

return 0;

{{Out}}

<pre>broood : [1 17 15 0 0 5 ]

hiphophiphop : [7 8 15 2 15 2 2 3 2 2 3 2 ]

Correct :)</pre>

 

=={{header|C++}}==

#include <iostream>

#include <iterator>

return 0;

}

{{out}}

<pre>

</pre>

 

 

 

 

 

 

 

=={{header|Common Lisp}}==

 

(defun move-to-front (x xs)

(assert (string= word decoded))

(format T "~s encodes to ~a which decodes back to ~s.~%"

 

{{Out}}

 

=={{header|D}}==

 

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

assert(word == decoded);

}

{{out}}

<pre>'broood' encodes to [1, 17, 15, 0, 0, 5], which decodes back to 'broood'

 

=={{header|Elixir}}==

@table Enum.to_list(?a..?z)

IO.inspect enc = MoveToFront.encode(word)

IO.puts "#{word == MoveToFront.decode(enc)}\n"

 

{{out}}

[7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2]

true

</pre>

 

=={{header|Gambas}}==

Dim sToCode As String[] = ["broood", "bananaaa", "hiphophiphop"] 'Samples to process

Dim sHold As New String[] 'To store results

Print sHold[siCounter] & " = " & sOutput 'Print the coded and decoded result

sOutput = "" 'Clear sOutput

Output:

<pre>

=={{header|Go}}==

{{trans|Python}}

 

import (

seq := make([]byte, len(s))

pad := []byte(symbols)

copy(pad[1:], pad[:x])

pad[0] = c

}

}

{{out}}

<pre>

 

=={{header|Haskell}}==

 

import Data.Maybe (fromJust)

(,) <*> uncurry ((==) . fst) <$> -- Test that ((fst . fst) x) == snd x)

((,) <*> (decode . snd) <$>

{{out}}

<pre>((("broood",[1,17,15,0,0,5]),"broood"),True)

 

Works in both languages:

every writes(s := !A, " -> [") do {

every writes(!(enc := encode(&lcase,s))," ")

procedure reorder(s1,s2,s3)

return s2||s1||s3

 

Sample run:

=={{header|J}}==

 

'seq table'=. y

ndx=.$0

end.

seq

 

Required examples:

 

1 17 15 0 0 5

spindizzy 'bananaaa';'abcdefghijklmnopqrstuvwxyz'

1 1 13 1 1 1 0 0

spindizzy 'hiphophiphop';'abcdefghijklmnopqrstuvwxyz'

 

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

=={{header|Java}}==

{{works with|Java|1.5+}}

import java.util.List;

 

test("hiphophiphop", symTable);

}

{{out}}

<pre>broood: [1, 17, 15, 0, 0, 5]

 

=={{header|JavaScript}}==

var init = {wordAsNumbers: [], charList: 'abcdefghijklmnopqrstuvwxyz'.split('')};

 

console.log(encoded);

console.log("from decoded:");

{{out}}

<pre>from encoded:

=={{header|jq}}==

{{works with|jq|q.4}}

# Output: the encoded string (an array)

def m2f_encode(st):

| [ (.[0] + [ $st[$ix] ]), [$st[$ix]] + $st[0:$ix] + $st[$ix+1:] ] )

| .[0]

'''Example''':

| ("broood", "bananaaa", "hiphophiphop")

| . as $string

| if $string == $decoded then "\($string) => \($encoded) => \($decoded)"

else "INTERNAL ERROR: encoding of \($string) => \($encoded) => \($decoded)"

{{Out}}

broood => [1,17,15,0,0,5] => broood

bananaaa => [1,1,13,1,1,1,0,0] => bananaaa

 

=={{header|Kotlin}}==

 

fun encode(s: String): IntArray {

println(" -> ${if (decoded[i] == strings[i]) "correct" else "incorrect"}")

}

 

{{out}}

 

=={{header|Lua}}==

function getAlphabet ()

local letters = {}

print("Decoded: " .. decode(output))

print()

{{out}}

<pre>Original string: broood

Decoded: hiphophiphop</pre>

 

 

f[{output_,symList_},next_]:=Module[{index},index=Position[symList,next][[1,1]]-1;

{output~Append~index,Prepend[Delete[symList,index+1],next]}];

{output~Append~index,Prepend[DeleteCases[symList,ToString[index]],index]}];

q=Fold[f2,{{},CharacterRange["a","z"]},p][[1]];

Testing out the function:

{{out}}

<pre>'broood' encodes to: {1,17,15,0,0,5} - {1,17,15,0,0,5} decodes to: 'broood' - Input equals Output: True

 

=={{header|MATLAB}}==

symTable = 'abcdefghijklmnopqrstuvwxyz';

inStr = {'broood' 'bananaaa' 'hiphophiphop'};

symTable = [symTable(arr(k)) symTable(1:arr(k)-1) symTable(arr(k)+1:end)];

end

{{out}}

<pre>broood: [ 1 17 15 0 0 5 ]

hiphophiphop: [ 7 8 15 2 15 2 2 3 2 2 3 2 ]

correctly decoded to hiphophiphop</pre>

 

=={{header|Perl}}==

use warnings;

sub encode {

print "correctly decoded to $decoded\n";

}

{{out}}

<pre>broood: 1 17 15 0 0 5

correctly decoded to hiphophiphop

</pre>

}

}

}

}

{{out}}

 

 

 

{{out}}

 

=={{header|PicoLisp}}==

(let Table (chop "abcdefghijklmnopqrstuvwxyz")

(mapcar

(get Table (inc 'N))

(rot Table N) ) )

Test:

(encode "broood") )

(test "broood"

(encode "hiphophiphop") )

(test "hiphophiphop"

 

=={{header|PL/I}}==

/*********************************************************************

* 25.5.2014 Walter Pachl translated from REXX

Else

Put Skip List('all wrong!!');

{{out}}

<pre> in=broood

 

=={{header|PowerShell}}==

{

[CmdletBinding()]

}

End{}

 

{{out}}

 

===Python: Procedural===

from string import ascii_lowercase

 

decode = move2front_decode(encode, SYMBOLTABLE)

print('which decodes back to %r' % decode)

 

{{out}}

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.

 

return [[st.index(ch), st.insert(0, st.pop(st.index(ch)))][0] for ch in s]

 

decode = m2f_d(encode, ST[::])

print('decodes back to %r' % decode)

 

{{out}}

Similar to that of the procedural version above.

 

=={{header|Racket}}==

(define default-symtab "abcdefghijklmnopqrstuvwxyz")

 

(printf "~s encodes to ~s, which decodes ~s to ~s.~%" str enc crt dec))

 

{{out}}

"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".</pre>

 

=={{header|REXX}}==

===version 1===

* 25.05.2014 Walter Pachl

* REXX strings start with position 1

Say 'all wrong!!'

Return

{{out}}

<pre> in=broood

===version 2===

Programming note: &nbsp; the two REXX statements that add/subtract &nbsp; <big> '''one''' </big>&nbsp; deal with the task's requirement that the symbol table be &nbsp; ''zero-indexed'' &nbsp; (the REXX language uses &nbsp; ''unity-based'' &nbsp; strings).

parse arg xxx; if xxx='' then xxx= 'broood bananaaa hiphophiphop' /*use the default?*/

$= /*set the decode string to a null. */

end /*k*/ /* [↑] the move─to─front encoding. */

!= /*set the encode string to a null. */

end /*m*/ /* [↑] the move─to─front decoding. */

{{out|output|text=&nbsp; when using the default input:}}

<pre>

</pre>

 

=={{header|Ruby}}==

Use a module as namespace:

ABC = ("a".."z").to_a.freeze

['broood', 'bananaaa', 'hiphophiphop'].each do |word|

p word == MoveToFront.decode(p MoveToFront.encode(p word))

 

{{out}}

[7, 8, 15, 2, 15, 2, 2, 3, 2, 2, 3, 2]

true

</pre>

 

=={{header|Scala}}==

{{works with|Scala|2.11.8+}}

 

import scala.annotation.tailrec

MoveToFront.test("bananaaa", symTable)

MoveToFront.test("hiphophiphop", symTable)

{{out}}

<pre>broood: List(1, 17, 15, 0, 0, 5)

{{trans|Perl}}

Implemented using regular expressions:

var table = ('a'..'z' -> join);

str.chars.map { |c|

print "in" if (decoded != test);

say "correctly decoded to #{decoded}";

 

Alternatively, implemented as a module, using arrays:

 

define ABC = @("a".."z")

print "in" if (decoded != test);

say "correctly decoded to #{decoded}";

 

{{out}}

 

=={{header|Swift}}==

 

var str="broood"

print(encarr)

print(decarr)

 

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

oo::class create MoveToFront {

puts [format "'%s' encodes to %s. This decodes to '%s'. %s" \

$tester $enc $dec [expr {$tester eq $dec ? "Correct!" : "WRONG!"}]]

{{out}}

<pre>

 

=={{header|VBScript}}==

'create the array list and populate it with the initial symbol position

Set symbol_table = CreateObject("System.Collections.ArrayList")

mtf_decode(mtf_encode(word)) & "."

WScript.StdOut.WriteBlankLines(1)

 

{{Out}}

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.

</pre>

 

=={{header|zkl}}==

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.

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

out:=texts.apply(encode);

texts.zipWith(fcn(t,e){ println(t,"-->",e) },out);

 

out.apply(decode).println();

{{out}}

<pre>