Изменения

Пусть <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>r</tex>-ичном алфавите для данных символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:

Для доказательства достаточности опишем рекурсивную процедуру[[file:Tree2forkraft.jpg|thumb|300px|Пример разбиения на группы, которая строит код для данного набора длин при <tex> l_i r = 2</tex>, удовлетворяющих неравенству символах ''a, b, c'', где <tex> \sum\limits_{i l_a = 1}^{n} r ^{-l_i} \leqslant 1 </tex>.Если некоторое <tex> l_i 2, l_b = 0 </tex>2, то <tex> n l_c = 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>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>(\sum\limits r ^{-l_i} = \dfrac{1}{r})</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 \geqslant j </tex> , и <tex> r \in \mathbb{N} </tex>. Следовательно числитель — натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма группы <tex> \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>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>.