CODEWITHSUNDEEP
algorithmencodingcompression
UdevV
UdevV

Reputation: 25

Probabilistic compression. How to decompress output values?

How to decompress output value?

Algorithm

1 initialize 256*256 table (for symbol codes) with zeros

2 initialize table address (x,y) with 00 (x axis) 00 (y axis)

3 if input symbol is equal to stored in table symbol (x,y): output symbol=0, else output symbol =prefix 1+input symbol (1symbol) and table value is changed to the value of input symbol

4 new address - (x-value of address = y-value), y-value=input symbol

5 check the next symbol using new address

For example

Initialize 256*256 table by zeros

input - 30(h), 30, 30, 30, 35

address 00 00

input=30, value (00,00) not the same, value (00,00)=30, output=130 (add prefix 1)

new address (x=y,y=input)=00 30, input=30, value (00,30) not the same, value (00,30)=30, output=130

new address=30 30, input=30, value (30,30) not the same, value (30,30)=30, output=130

new address=30 30, input=30, value (30,30) the same, output=0

new address=30 30, input=35, value (30,30) not the same, output=135

OUTPUT = 130 130 130 0 135. How to get input (30 30 30 30 35)?

Upvotes: 1

Views: 58

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

The idea is to alternately decompress the next symbol and update the table the same way that the compressor did.

address is now 0,0
read 130
begins with a 1, so table[0,0] <- 30
write table[0,0] -> 30
address is now 0,30
read 130
begins with a 1, so table[0,30] <- 30
write table[0,30] -> 30
address is now 30,30
read 130
begins with a 1, so table[30,30] <- 30
write table[30,30] -> 30
address is still 30,30
read 0
is 0, so don't update table
write table[30,30] -> 30
address is still 30,30
read 135
begins with a 1, so table[30,30] <- 35
write table[30,30] -> 35
address is now 30,35

Upvotes: 1

Related Questions