Class: Omnizip::Algorithms::BZip2::Mtf

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/algorithms/bzip2/mtf.rb

Overview

Move-to-Front (MTF) Transform

MTF is a data transformation that exploits locality of reference. It maintains a list of symbols and moves accessed symbols to the front of the list. This tends to concentrate frequently accessed symbols at low indices, making the data more compressible.

After BWT, the data often has runs of the same character. MTF converts these to runs of low numbers (often 0), which are then efficiently compressed by RLE.

The algorithm:

  1. Initialize symbol list [0, 1, 2, ..., 255]
  2. For each byte in input:
    • Find its position in the symbol list
    • Output that position
    • Move the byte to the front of the list

Instance Method Summary collapse

Instance Method Details

#decode(data) ⇒ String

Decode MTF-encoded data

Parameters:

  • data (String) —

    MTF-encoded indices

Returns:

  • (String) —

    Original data



71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/omnizip/algorithms/bzip2/mtf.rb', line 71

def decode(data)
  return "".b if data.empty?

  symbols = init_symbol_list
  result = []

  data.each_byte do |index|
    # Get byte at this index
    byte = symbols[index]
    result << byte

    # Move byte to front
    symbols.delete_at(index)
    symbols.unshift(byte)
  end

  result.pack("C*")
end

#encode(data) ⇒ String

Encode data using Move-to-Front transform

Parameters:

  • data (String) —

    Input data to transform

Returns:

  • (String) —

    MTF-encoded data (byte indices)



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/omnizip/algorithms/bzip2/mtf.rb', line 48

def encode(data)
  return "".b if data.empty?

  symbols = init_symbol_list
  result = []

  data.each_byte do |byte|
    # Find position of byte in symbol list
    index = symbols.index(byte)
    result << index

    # Move byte to front
    symbols.delete_at(index)
    symbols.unshift(byte)
  end

  result.pack("C*")
end