Изменения

Перейти к: навигация, поиск

Неравенство Крафта

16 байт убрано, 17:20, 3 января 2018
м
Нет описания правки
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> .
#Для доказательства корректности разделим длины <tex> l_i </tex> на не более <tex>r</tex>, возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .
#:Пусть у нас есть <tex>n</tex> символов, кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. Давайте разделим данные символы на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса.
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен:
29
правок

Навигация