103 lines
2.3 KiB
Plaintext
103 lines
2.3 KiB
Plaintext
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
|
|
of input symbols into an array of output numbers (indices).<br>
|
|
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:
|
|
<pre>
|
|
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
|
|
</pre>
|
|
|
|
;Decoding algorithm:
|
|
<pre>
|
|
# 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
|
|
</pre>
|
|
|
|
;Example:
|
|
Encoding the string of character symbols 'broood' using a symbol table of
|
|
the characters 'a'-to-'z'
|
|
|
|
{| class="wikitable" border="1"
|
|
|-
|
|
! Input
|
|
! Output
|
|
! SymbolTable
|
|
|-
|
|
| '''b'''roood
|
|
| 1
|
|
| 'abcdefghijklmnopqrstuvwxyz'
|
|
|-
|
|
| b'''r'''oood
|
|
| 1 17
|
|
| 'bacdefghijklmnopqrstuvwxyz'
|
|
|-
|
|
| br'''o'''ood
|
|
| 1 17 15
|
|
| 'rbacdefghijklmnopqstuvwxyz'
|
|
|-
|
|
| bro'''o'''od
|
|
| 1 17 15 0
|
|
| 'orbacdefghijklmnpqstuvwxyz'
|
|
|-
|
|
| broo'''o'''d
|
|
| 1 17 15 0 0
|
|
| 'orbacdefghijklmnpqstuvwxyz'
|
|
|-
|
|
| brooo'''d'''
|
|
| 1 17 15 0 0 5
|
|
| 'orbacdefghijklmnpqstuvwxyz'
|
|
|}
|
|
|
|
Decoding the indices back to the original symbol order:
|
|
{| class="wikitable" border="1"
|
|
|-
|
|
! 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 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.
|
|
|
|
<br>
|
|
The strings are:
|
|
|
|
<big> broood </big>
|
|
<big> bananaaa </big>
|
|
<big> hiphophiphop </big>
|
|
|
|
(Note the spellings.)
|
|
<br><br>
|