t1m013y-schinf11

Задание “Код Хаффмана”

Фомин Тимофей

1

Вариант: 22
Слово: двусмысленность

2

двусмысленность
^^^^^^ ^^^ ^ ^^
двусмыленоть - 12 уникальных букв

д - 1
в - 1
у - 1
с - 3
м - 1
ы - 1
л - 1
е - 1
н - 2
о - 1
т - 1
ь - 1

3

д - 1
в - 1
у - 1
м - 1
ы - 1
л - 1
е - 1
о - 1
т - 1
ь - 1
н - 2
с - 3

д - 1 \2
в - 1 / 
у - 1   
м - 1   
ы - 1   
л - 1   
е - 1   
о - 1   
т - 1   
ь - 1   
н - 2   
с - 3   

у - 1 \2
м - 1 / 
ы - 1   
л - 1   
е - 1   
о - 1   
т - 1   
ь - 1   
д - 1 \2
в - 1 / 
н - 2   
с - 3   

ы - 1 \2
л - 1 / 
е - 1   
о - 1   
т - 1   
ь - 1   
у - 1 \2
м - 1 / 
д - 1 \2
в - 1 / 
н - 2   
с - 3   

е - 1 \2
о - 1 / 
т - 1   
ь - 1   
ы - 1 \2
л - 1 / 
у - 1 \2
м - 1 / 
д - 1 \2
в - 1 / 
н - 2   
с - 3   

т - 1 \2
ь - 1 / 
е - 1 \2
о - 1 / 
ы - 1 \2
л - 1 / 
у - 1 \2
м - 1 / 
д - 1 \2
в - 1 / 
н - 2   
с - 3   

т - 1 \2 \ 
ь - 1 /  |4
е - 1 \2 | 
о - 1 /  / 
ы - 1 \2   
л - 1 /    
у - 1 \2   
м - 1 /    
д - 1 \2   
в - 1 /    
н - 2      
с - 3      

ы - 1 \2 \ 
л - 1 /  |4
у - 1 \2 | 
м - 1 /  / 
д - 1 \2   
в - 1 /    
н - 2      
с - 3      
т - 1 \2 \ 
ь - 1 /  |4
е - 1 \2 | 
о - 1 /  / 

д - 1 \2   
в - 1 /    
н - 2      
с - 3      
ы - 1 \2 \ 
л - 1 /  |4
у - 1 \2 | 
м - 1 /  / 
т - 1 \2 \ 
ь - 1 /  |4
е - 1 \2 | 
о - 1 /  / 

д - 1 \2 \ 
в - 1 /  |4
н - 2    / 
с - 3      
ы - 1 \2 \ 
л - 1 /  |4
у - 1 \2 | 
м - 1 /  / 
т - 1 \2 \ 
ь - 1 /  |4
е - 1 \2 | 
о - 1 /  / 

с - 3       \ 
д - 1 \2 \  |7
в - 1 /  |4 | 
н - 2    /  / 
ы - 1 \2 \    
л - 1 /  |4   
у - 1 \2 |    
м - 1 /  /    
т - 1 \2 \    
ь - 1 /  |4   
е - 1 \2 |    
о - 1 /  /    

ы - 1 \2 \  \ 
л - 1 /  |4 | 
у - 1 \2 |  | 
м - 1 /  /  |8
т - 1 \2 \  | 
ь - 1 /  |4 | 
е - 1 \2 |  | 
о - 1 /  /  / 
с - 3       \ 
д - 1 \2 \  |7
в - 1 /  |4 | 
н - 2    /  / 

с - 3       \  \  
д - 1 \2 \  |7 |  
в - 1 /  |4 |  |  
н - 2    /  /  |  
ы - 1 \2 \  \  |  
л - 1 /  |4 |  |15
у - 1 \2 |  |  |  
м - 1 /  /  |8 |  
т - 1 \2 \  |  |  
ь - 1 /  |4 |  |  
е - 1 \2 |  |  |  
о - 1 /  /  /  /  

Дерево:
Huffman
|-0-|-0-с
|   \-1-|-0-|-0-д
|       |   \-1-в
|       \-1-н
\-1-|-0-|-0-|-0-ы
    |   |   \-1-л
    |   \-1-|-0-у
    |       \-1-м
    \-1-|-0-|-0-т
        |   \-1-ь
        \-1-|-0-е
            \-1-о

Словарь:
00   - с
0100 - д
0101 - в
011  - н
1000 - ы
1001 - л
1010 - у
1011 - м
1100 - т
1101 - ь
1110 - е
1111 - о

4

Кол-во уникальных букв: 12; Минимальное необходимое количество бит: 4

Словарь:
д - 0000
в - 0001
у - 0010
с - 0011
м - 0100
ы - 0101
л - 0110
е - 0111
н - 1000
о - 1001
т - 1010
ь - 1011

5

Равномерное кодироавание (8-битный код) по таблице ASCII (кодировка Windows-1251)

Словарь:
д - E4 - 11100100
в - E2 - 11100010
у - F3 - 11110011
с - F1 - 11110001
м - EC - 11101100
ы - FB - 11111011
л - EB - 11101011
е - E5 - 11100101
н - ED - 11101101
о - EE - 11101110
т - F2 - 11110010
ь - FC - 11111100

Результат:
д       в       у       с       м       ы       с       л       е       н       н       о       с       т       ь       
111001001110001011110011111100011110110011111011111100011110101111100101111011011110110111101110111100011111001011111100
120 бит

Равномерное кодирование (4-битный код) по своему словарю

д   в   у   с   м   ы   с   л   е   н   н   о   с   т   ь   
000000010010001101000101001101100111100010001001001110101011
60 бит

Кодирование Хаффмана

д   в   у   с м   ы   с л   е   н  н  о   с т   ь   
0100010110100010111000001001111001101111110011001101
52 бита

Результаты кодирования

Кодировка	Длина
ASCII	120
4bit	60
Хаффман	52