Изменения

Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, где <tex>i\in \left [ 1, n \right ]</tex>.

Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex>, удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex>.Если некоторое <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> l_i </tex> в порядке увеличения индекса. Несложно понять, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex>. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву.

Если некоторое <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> l_i </tex> в порядке увеличения индекса. Несложно понять, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> , то на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо <tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{l_i-1}} \right ) </tex> делится на <tex>\dfrac{1}{r^{l_i}}</tex> , потому что каждый член слева делятся на <tex> \dfrac{1}{r^{l_i}} </tex> . Получаем, что остаток набираемой группы до <tex>\dfrac{1}{r}</tex> всегда делится на текущую величину <tex> r ^{-l_i} </tex> . А раз остаток делится, то взяв <tex> l_i </tex> в группу мы не перепрыгнем через максимальное значение. У всех слов из одной группы будет одна и та же начальная буква. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву. Доказательство корректности проведём по индукции по величине <tex> l_n </tex>.

'''Переход: ''' (очевиден) Допустим, что процедура корректна для <tex> l_n = w </tex>. Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex>.

Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex>.