How to resolve the algorithm Move-to-front algorithm step by step in the jq programming language

Published on 12 May 2024 09:40 PM
#Jq

How to resolve the algorithm Move-to-front algorithm step by step in the jq programming language

Table of Contents

Problem Statement

Given a symbol table of a zero-indexed array of all possible input symbols this algorithm reversibly transforms a sequence of input symbols into an array of output numbers (indices). The transform in many cases acts to give frequently repeated input symbols lower indices which is useful in some compression algorithms.

Encoding the string of character symbols 'broood' using a symbol table of the lowercase characters   a-to-z

Decoding the indices back to the original symbol order:

The strings are:

(Note the misspellings in the above strings.)

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Move-to-front algorithm step by step in the jq programming language

Source code in the jq programming language

# 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;

("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

$ 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

You may also check:How to resolve the algorithm MD5/Implementation step by step in the ooRexx programming language
You may also check:How to resolve the algorithm Pisano period step by step in the 11l programming language
You may also check:How to resolve the algorithm Shoelace formula for polygonal area step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Forward difference step by step in the Nim programming language
You may also check:How to resolve the algorithm UTF-8 encode and decode step by step in the VBA programming language