
Compression through selforganizing search

Page  11/24  Date  03.05.2017  Size  186.06 Kb.   #18863 
  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')
Compression through selforganizing 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 selforganizing 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 07, but our number of bits is 18
 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 selforganizing 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 Needed1 in binary)
Compression Example
Share with your friends: 
The database is protected by copyright ©sckool.org 2022
send message

