29
правок
Изменения
м
Нет описания правки
|about=неравенство Крафта
|statement=
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>.
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен:
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center>
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i - l_j</tex> неотрицательно при <tex> i \in \mathbb{N}geqslant j </tex> , и <tex> r \in \mathbb{N} </tex>. Следовательно числитель — натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма: <tex> \sum\limits_{j = 1}^{i} r ^{-l_j} \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.#Поставим для всех слов из одной группы одинаковый символ :Заметим, что при этом только последняя группа будет <tex> \leqslant \dfrac{1}{r} </tex>, остальные будут равны <tex> \Rightarrowdfrac{1}{r} </tex> ''у .#Выберем для каждой группы свой начальный символ''. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен.
#:'''База:''' Если При <tex> l_n = 0 </tex>, то процедура корректнакорректность процедуры очевидна.
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> .
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> .
