These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else


Compression through self-organizing search



Download 186.06 Kb.
Page11/24
Date03.05.2017
Size186.06 Kb.
#18863
1   ...   7   8   9   10   11   12   13   14   ...   24

Compression through self-organizing search

  • General Approach
    • Maintain two arrays:
      • One is indexed on the original byte codes and is storing a position value (call this Array1)
          • 'A' (ASCII 65) is in position 0 (i.e. at the front of the list)
      • One is indexed on the position and is storing a byte code (call this Array2)
          • Code at position 0 is 65 ('A')
  • Code Value
  • 0
  • 1
  • 2
  • 65
  • 83
  • Position
  • 2
  • 25
  • 120
  • 0
  • 1
  • Position
  • 0
  • 1
  • 2
  • 25
  • 120
  • Code Value
  • 65
  • 83
  • 0
  • 1
  • 2

Compression through self-organizing search

  • Compression:
    • When we read in a byte / character, do the following:
      • Using Array1, find the position, pos, of the character in Array2
      • Output the correct code value, as explained in the next slides
      • Update Array2 using the correct heuristic (MTF or Transpose) and also update Array1 accordingly
    • Idea is that frequently seen characters will end up close to the front of the array

Compression through self-organizing search

    • Idea of the output:
      • Initial bits will be the binary representation of a number from 0 to 7, or 3 bits
        • This is equal to the (number of bits – 1) required to represent pos in binary when leading 0s are removed
        • The –1 is necessary 3 (unsigned) bits can represent 0-7, but our number of bits is 1-8
      • Next bits are the value of pos in binary, with leading 0s removed
        • For example, the pos value 9, or 00001001, can be represented in 4 bits
      • Clearly, the positions closer to the front can be represented by fewer bits

Compression through self-organizing search

        • Output is generated as follows:
          • Shift out the leading (8 – Bits Needed) bits from the position in binary
          • Append the result to the leading 3 bits (Bits Needed-1 in binary)
  • Bits Needed
  • (minus 1)
  • (in binary)
  • Pos
  • Pos in binary
  • Output
  • 1
  • 0
  • 000
  • 0
  • 00000000
  • 0000
  • 1
  • 0
  • 1
  • 00000001
  • 0001
  • 2
  • 1
  • 001
  • 2
  • 00000010
  • 00110
  • 2
  • 1
  • 3
  • 00000011
  • 00111
  • 3
  • 2
  • 010
  • 4
  • 00000100
  • 010100
  • 3
  • 2
  • 5
  • 00000101
  • 010101
  • 3
  • 2
  • 6
  • 00000110
  • 010110
  • 3
  • 2
  • 7
  • 00000111
  • 010111
  • 4
  • 3
  • 011
  • 8
  • 00001000
  • 0111000

Compression Example

  • Original Data: ABCABAABC
  • Code Value
  • 0
  • 1
  • 65
  • 66
  • 67
  • Position
  • 0
  • 1
  • 65
  • 66
  • 67
  • Position
  • 0
  • 1
  • 65
  • 66
  • 67
  • Code Value
  • 0
  • 1
  • 65
  • 66
  • 67

Download 186.06 Kb.

Share with your friends:
1   ...   7   8   9   10   11   12   13   14   ...   24




The database is protected by copyright ©sckool.org 2022
send message

    Main page