MovetoFront

Move-to-Front (MTF) refers to two related ideas in computer science: a self-organizing heuristic for dynamic lists and a transform used in data compression.

Move-to-Front as a heuristic: In a list of items, when an item is accessed, it is moved to the front of the list. This rule aims to keep recently used elements near the front, exploiting temporal locality and improving access times in scenarios where the access pattern favors recently referenced items. It is used in certain caching schemes, data structures, and indexing systems where minimizing search costs for frequently accessed elements is desirable.

Move-to-Front transform in data compression: The MTF transform is applied after the Burrows-Wheeler Transform (BWT) in some compressors. It maintains an ordered list of symbols (initially in a chosen order). For each symbol in the input sequence, the encoder outputs the symbol’s 0-based position in the current list and then moves that symbol to the front of the list. The decoder mirrors this process. The transform tends to produce many small integers when the input exhibits locality, which can improve the efficiency of subsequent entropy coding steps.

Complexity: Naively, locating a symbol in the list takes O(n) time per symbol, with O(1) to move it to the front. With advanced data structures (for example, Fenwick trees or balanced trees), the position can be found and updated in O(log n) time per symbol.

Applications: The MTF transform is a standard component of many BWT-based compression tools, such as those used in bzip2-style pipelines. The heuristic is also studied in the context of self-organizing lists and adaptive data structures.