Move to Front Transform

Created on 2024-09-25T00:56:20-05:00

Return to the Index

This card pertains to a resource available on the internet.

This card can also be read via Gemini.

A compression filter where each symbol is replaced with its index in a symbol table. After insertion, the symbol is moved to the "front" of the symbol table.

The hope is that there is enough local repetition that most offsets are small and a further pass is able to exploit this. For example this may result in a lot more symbols being "4" which allows a range coder or huffman table to prioritize bits to the smaller but more frequent offsets.

Example

abcdefghijklmnopqrstuvwxzy
potato

pabcdefghijklmnoqrstuvwxzy
16,otato

pabcdefghijklmnoqrstuvwxzy
16,16,tato

opabcdefghijklmnqrstuvwxzy
16,16,20,ato

topabcdefghijklmnqrsuvwxzy
16,16,20,ato

topabcdefghijklmnqrsuvwxzy
16,16,20,4,to

atopbcdefghijklmnqrsuvwxzy
16,16,20,4,2,o

taopbcdefghijklmnqrsuvwxzy
16,16,20,4,2,3

otapbcdefghijklmnqrsuvwxzy