MTF Approximates - cr88192/bgbtech_misc GitHub Wiki

STF: Swap Towards Front

• For any index I above 0, swap with index I-1.
• Can use a single array w/o rotations.
• Consists solely of swaps.
• Does well for decent sized buffers with static probabilities.
• Drawback: takes a while to adapt.
  • For each symbol, it needs to appear around 256 times in the worse case with a 256 symbol alphabet.
  • For a 256 symbol alphabet, general adaptation will require around 64k symbols.

FMTF: Fake Move To Front

• For index(I)==0, do nothing.
• Else:
  • Rotate space back by one position;
  • Swap new index 0 with old index I.
• Involves use of rotations.
• Adapts quickly.
• Poor at maintaining good probability ranking.

SMTF: Swap or Move-To-Front

• For index I from 1 to N-1, Swap towards Front.
• For index N to Max, Fake Move To Front
• Compromise of STF and FMTF
• Uses STF for high probability symbols, benefiting from its better probability rankings.
• Uses FMTF for larger indices, allowing quicker adaptation.
• A variation is to leave it up to the encoder whether STF or FMTF-like behavior is used.
  • Ex: Coded 1..Max+1 use STF (as 0..Max), Index 0 escapes to an FMTF index.

MTF: proper MTF

• For index(I)==0, do nothing.
• Else:
  • Move I to temporary(T).
  • For J=I to 1
    • Move J-1 into J
  • Move T to index 0.
• Big drawback: Slow.