česky
previous main page content next

Move-to-front

Main features

  • method used in Burrows-Wheeler transformation
  • doesn't compress data, but decreases redundantion
  • uses push down store

Time and space complexities

Time complexity of algorithm: O(n)
Space complexity of algorithm: O(|Σ|)

Description

This method consists of inserting input alphabet into a push down store and using of it's indexes. Everytime each element is used, it is moved to the beginning of the push down store (index is set to 0) and other indexes are re-counted to keep their linearity.

Pseudo-code


 1:  begin 
 2:     insert all symbols of input alphabet into push down store
 3:     while (!EOF) do
 4:      begin
 5:        output(position of symbol in buffer)
 6:        move symbol to front of buffer
 7:      end
 8:  end

References

  1. David Hoksza: Burrows-Wheeler transformation. Reboot.cz.
  2. Arturo San Emeterio Campos: Move to front.

Example