Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
Coding redundancy
There are different compression algorithms in image
processing. Normal uncompressed images (bitmap images)
use 8 bits code representation.
Huffman coding is based on coding
redundancy and uses variable length code of symbols.
The algorithm prepares the table of symbols according to
the frequencies of the symbols. Then, every symbol is
assigned a code in such a way that the most frequent
symbol is assigned the shortest code and the
least frequent symbol is assigned the longer code.
The average length of compressed
representation is calculated
using the following formula:
where - rk is the
kth symbol
- l(rk) is the code length of
it and
-
pk(r
k) is the probability of the
kth symbol
As an example, the following table lists 4 symbols
with their frequencies and code lengths.
Symbol |
Length of Code |
Frequency |
a | 2 |
0.26 |
b | 1 |
0.46 |
c | 3 |
0.24 |
d | 3 |
0.04 |
According to the given info, the average length is:
Lavg = (2x0.26) + (1x0.46) + (3x0.24)
+ (3x0.04) = 1.82
Then, the compression ratio is
C = (Length Before Compression) / (Length After
Compression)
C = 8 / 1.82 = 4.396
And coding redundancy is
R = (1-1/C)*100 = (1 - 1/4.396)*100 = 77.25
Question: Write a program that is going
to read symbols with their code length and frequencies.
Then, your program will calculate and show
the coding redundancy.
Note: Length Before Compression is
fixed and it's 8.
Input specification
In the beginning, you will be given an integer (n):
the number of symbols used where n is between 1 and 200.
Then, in each of the following n lines, you will
be given three information: a symbol and two numbers.
- the symbol: at most three chars long string
- frequency: a floating point number between 0 and 1
- code length: an integer between 1 and 16
Output specification
Show a floating point number with 2 digits
precision.
Sample Input I
4
a 0.26 2
b 0.47 1
c 0.24 3
d 0.03 3
|
Sample Output I
77.5
|
Для отправки решений необходимо выполнить вход.
|