12.1. Коды
Имея $$2^n$$ символов, мы можем кодировать каждый из них $$n$$ битами, поскольку существует $$2^n$$ комбинаций
из $$n$$ битов. Например, можно закодировать $$4=2^2$$
символа А, Г, Т, Ц (используемые при записи геномов) двухбитовыми
комбинациями $$00$$, $$01$$, $$10$$
и $$11$$. Другой пример:
последовательностями из $$8$$ битов (байтами) можно
закодировать $$256$$ символов (и этого хватает на латинские
и русские буквы, знаки препинания и др.).
Более формально: пусть нам дан алфавит,
то есть конечное множество, элементы которого называются символами или буквами этого алфавита. Кодом для алфавита $$A$$ называется функция (таблица) $$\alpha$$,
которая для каждого символа $$a$$ из $$A$$ указывает двоичное
слово $$\alpha(a)$$, называемое кодовым словом, или просто кодом
этого символа. ( Двоичное слово - конечная
последовательность нулей и единиц.)
Не требуется, чтобы коды всех символов имели равные длины.
Мы допускаем, чтобы разные символы имели одинаковые коды.
Согласно нашему определению, разрешается все буквы алфавита
закодировать словом $$0$$ (и даже пустым словом) - но,
конечно, такой код будет бесполезен. Хороший код должен
позволять декодирование (восстановление последовательности
символов по ее коду).
Формально это определяется так. Пусть фиксирован алфавит $$A$$ и код $$\alpha$$ для этого алфавита. Для каждого слова $$P$$ в алфавите $$A$$ (то есть для любой конечной
последовательности букв алфавита $$A$$ ) рассмотрим двоичное слово $$\alpha(P)$$, которое получается, если записать подряд коды всех букв из $$P$$ (без каких-либо разделителей). Код $$\alpha$$ называется однозначным,
если коды различных слов различны: $$\alpha(P)\ne \alpha(P')$$
при $$P\ne P'$$.
12.1.1.
Рассмотрим трехбуквенный алфавит $$\{a,b,c\}$$ и код $$\alpha(a)=0$$, $$\alpha(b)=01$$
и $$\alpha(c)=00$$. Будет ли
этот код однозначным?
Решение. Нет, поскольку слова $$aa$$ и $$c$$ кодируются одинаково.
12.1.2.
Для того же алфавита рассмотрим код $$\alpha(a)=0$$, $$\alpha(b)=10$$ и $$\alpha(c)=11$$. Будет ли этот код однозначным?
Решение. Будет. Чтобы доказать это, достаточно объяснить, как
можно восстановить слово $$P$$ по его коду $$\alpha(P)$$.
Если $$\alpha(P)$$ начинается с нуля, то ясно, что слово $$P$$
начинается
с $$a$$. Если $$\alpha(P)$$ начинается с единицы, то
слово $$P$$
начинается с $$b$$ или с $$c$$ - чтобы узнать, с чего именно,
достаточно посмотреть на второй бит слова $$\alpha(P)$$.
Восстановив первую букву слова $$A$$, мы забываем о ней и о ее
коде, и продолжаем все сначала.
Верно и более общее утверждение. Назовем код префиксным,
если коды букв не являются началами друг
друга (слово $$\alpha(p)$$ не является началом слова $$\alpha(q)$$, если буквы $$p$$ и $$q$$
различны).
12.1.3.
Доказать, что любой префиксный код является однозначным.
Решение. Декодирование можно вести слева направо. Первая буква восстанавливается однозначно: если для двух
букв $$p$$ и $$q$$ слова $$\alpha(p)$$ и $$\alpha(q)$$ являются началами кода, то
одно из слов $$\alpha(p)$$ и $$\alpha(q)$$ является началом другого, что невозможно для префиксного кода. И так далее.
12.1.4.
Привести пример однозначного кода, не являющегося префиксным.
Указание.
Пусть $$\alpha(a)=0$$, $$\alpha(b)=01$$, $$\alpha(c)=11$$.
Этот код является "суффиксным", но не префиксным.
12.1.5.
Найти таблицу для азбуки Морзе.
Объяснить, почему ее
можно использовать на практике, хотя она не является ни префиксным, ни даже однозначным кодом.
12.2. Неравенство Крафта-Макмиллана
Зачем вообще нужны коды с разной длиной кодовых слов? Дело в том,
что на практике разные символы алфавита встречаются
с разной частотой, и выгодно закодировать частые символы
короткими словами. (Это соображение, кстати, учитывалось
при составлении азбуки Морзе.)
Пусть для каждой буквы $$a$$ алфавита $$A$$ фиксирована ее частота $$p(a)$$ - положительное число, причем суммы частот
всех букв равны единице. Тогда для любого кода $$\alpha$$ можно
определить среднюю длину этого кода как сумму$$E = \sum p(a) |\alpha(a)|$$
по всем буквам $$a\in A$$, где $$|\alpha(a)|$$ - длина
кодового
слова $$\alpha(a)$$ буквы $$a$$. (Смысл этого определения:
если
в слове длины $$N$$ буква $$a$$ встречается с частотой $$p(a)$$,
то таких букв будет $$Np(a)$$ и на их кодирование уйдет $$Np(a)|\alpha(a)|$$ битов; общая длина кода будет $$\sum
Np(a)|\alpha(a)|$$ и в среднем на кодирование каждой буквы
уйдет $$E$$ битов.)
Теперь возникает задача: для данных частот построить однозначный
код минимальной средней длины. Теоретически это можно сделать
перебором (если в коде есть хотя бы одно очень длинное кодовое
слово, то его средняя длина велика, поэтому такие коды можно не
рассматривать; остается конечное число вариантов). Но можно
обойтись и без перебора, и в этом разделе мы научимся это
делать.
Для начала поймем, что мешает нам выбирать кодовые слова
короткими. Оказывается, что есть ровно одно препятствие:
длины $$n_1,\ldots,n_k$$ кодовых слов должны удовлетворять
неравенству$$2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k} \le 1,$$
называемому в теории кодирования неравенством Крафта
Макмиллана.
12.2.1.
Проверить, что оно выполнено для рассмотренных выше
примеров однозначных кодов.
12.2.2.
Доказать, что для всякого префиксного кода выполняется неравенство Крафта-Макмиллана.
Решение. Отрезок $$[0,1]$$ можно разбить на две половины.
Назовем левую $$I_0$$, а правую $$I_1$$. Каждую из них
разобьем
пополам: отрезок $$I_0$$ разделится на левую
половину $$I_{00}$$ и правую $$I_{01}$$, аналогично $$I_1$$ делится на $$I_{10}$$ и $$I_{11}$$. И так
далее: любому
двоичному слову $$x$$ соответствует отрезок $$I_x$$. Длина
этого отрезка есть $$2^{-|x|}$$, где $$|x|$$ - длина
слова $$x$$.
Если слово $$x$$ является началом слова $$y$$, то
отрезок $$I_x$$
содержит отрезок $$I_y$$ ; если ни одно из
слов $$x$$ и $$y$$ не
является началом другого, то отрезки $$I_x$$ и $$I_y$$ не
перекрываются (на том знаке, где $$x$$ и $$y$$ впервые
расходятся, $$I_x$$ и $$I_y$$ попадают в разные
половины).
Рассмотрим теперь отрезки, соответствующие словам префиксного
кода. Они не перекрываются. А значит, сумма их длин не больше
единицы, что и дает неравенство Крафта-Макмиллана.
12.2.3.
Пусть даны $$k$$ целых положительных чисел $$n_1,\ldots,n_k$$,
удовлетворяющие неравенству Крафта-Макмиллана. Доказать,
что можно построить префиксный код для $$k$$ -буквенного алфавита
с длинами кодовых слов $$n_1,\ldots,n_k$$.
Решение. И здесь полезно использовать соответствие между словами
и отрезками и представлять себе дело так: у нас есть единичный
отрезок $$[0,1]$$, и мы выделяем его части пользователям по
требованию. Если пользователь приходит с числом $$n_i$$, то это
значит, что ему надо выдать в пользование один из отрезков
длиной $$2^{-n_i}$$, соответствующих кодовым словам
длины $$n_i$$.
(Тем самым годятся не любые отрезки такой длины, а лишь "
правильно расположенные".) Код должен быть префиксным, это
значит, что отрезки разных пользователей не должны
перекрываться. Нам дано, что суммарная длина всех требований не
больше единицы. Как их удовлетворить? Можно отводить место слева
направо, при этом рассматривать требования в порядке убывания
длин (тогда более короткие отрезки будут правильно расположены
после предыдущих более длинных).
12.2.4.
Показать, что выделять кодовые слова (место на отрезке)
можно и в порядке поступления требований (как иногда
говорят, в "режиме on-line"): пользователь приходит
с числом $$n_i$$ и уходит с правильно расположенным отрезком
длины $$2^{-n_i}$$, причем если выполнено неравенство Крафта
Макмиллана, то никто не уйдет обиженным (всем хватит места,
и перераспределять его не придется).
Указание.
Нужно поддерживать свободное пространство как
объединение правильно расположенных отрезков попарно различных
длин, выделяя каждому пользователю кусок из кратчайшего
подходящего отрезка и доразбивая остаток.
12.2.5.
Показать, что неравенство Крафта-Макмиллана
выполняется не только для любого префиксного кода, но и вообще
для любого однозначного кода.
(Именно это доказал Макмиллан; Крафт доказал неравенство для
префиксных кодов.)
Решение. Есть разные способы решить эту задачу; мы приведем
простое и красивое, хотя и несколько загадочное, решение. Пусть
имеется однозначный код с $$k$$ кодовыми словами $$P_1,\ldots,P_k$$.
Нам надо доказать, что их длины $$n_i=|P_i|$$ удовлетворяют
неравенству Крафта-Макмиллана. Представим себе, что вместо
нулей и единиц используются символы $$a$$ и $$b$$ (какая
разница, из чего составлять коды?). Запишем формально сумму всех кодовых
слов как алгебраическое выражение$$P_1 + P_2 + \ldots + P_k$$
(многочлен от $$a$$ и $$b$$, в котором одночлены записаны как
произведения переменных $$a$$ и $$b$$, без возведения
в степень). Теперь (еще более странное на первый взгляд
действие) возведем это выражение в степень $$N$$
(произвольное натуральное число) и раскроем скобки,
сохраняя порядок переменных (не собирая вместе одинаковые
переменные) в одночленах:$$(P_1+P_2+\ldots+P_k)^N=\text{сумма одночленов}.$$
Например, для кода со словами $$0, 10, 11$$ (которые теперь
записываются
как $$a,ba,bb$$ ) и для $$N=2$$ получаем$$\begin{multiline*}
(a+ba+bb)^2= (a+ba+bb)(a+ba+bb) = {} \\
{} = aa + aba + abb + baa +baba+ babb + bba + bbba + bbbb.
\end{multiline*}$$
В этом примере все одночлены в правой части различны (если не
переставлять переменные), и это не случайно: так будет для
любого однозначного кода. В самом деле, по определению
однозначности никакое слово не может быть получено двумя
способами при соединении кодовых слов.
Теперь подставим $$a=b=1/2$$ в наше равенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева
получится$$(2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k})^N$$
(в скобке как раз выражение из неравенства Крафта
Макмиллана). Правую часть мы оценим сверху, сгруппировав
слова по длинам: имеется не более $$2^l$$ слагаемых
длины $$l$$, каждое из которых равно $$2^{-l}$$, и потому
слагаемые данной длины в сумме не превосходят единицы,
а правая часть не превосходит максимальной длины слагаемых,
то есть $$N\max n_i$$. Итак, получаем, что$$(2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k})^N < N max n_i,$$
и это верно при любом $$N$$. Если основание степени в левой
части больше единицы, то при больших $$N$$ это неравенство
нарушится (показательная функция растет быстрее линейной).
Поэтому для однозначного кода выполняется неравенство
Крафта-Макмиллана.
12.3. Код Хаффмена
Теперь задача о коде минимальной средней длины приобретает такую
форму: для данных положительных $$p_1,\ldots,p_k$$, равных
в сумме единице, найти целые положительные $$n_1,\ldots,n_k$$, для которых выполнено неравенство
Крафта-Макмиллана, а сумма$$\sum_{i=1}^k p_i n_i$$
является минимально возможной (среди наборов $$n_1,\ldots,n_k$$,
удовлетворяющих неравенству). Задача 12.2.5. показывает, что средняя длина однозначного кода не
меньше этого минимума, а задача 12.2.3. говорит,
что этот минимум достигается, причем даже для префиксного кода.
Как же найти числа $$n_1,\ldots,n_k$$, доставляющие этот минимум?
12.3.1.
Доказать, что для двух букв оптимальный код состоит из
двух слов длины $$1$$, независимо от частот букв.
Чтобы решить задачу в общем случае, начнем с нескольких простых
замечаний.
12.3.2.
Пусть частоты расположены в убывающем порядке: $$p_1 >
p_2 > \ldots > p_k$$. Доказать, что тогда длины слов оптимального
кода идут в неубывающем порядке: $$n_1\le n_2\le \ldots\le n_k$$.
Решение. Если бы более редкая буква имела бы более короткое
кодовое слово, то, обменяв кодовые слова, мы сократили бы среднюю
длину кода.
12.3.3.
Останется ли утверждение предыдущей задачи в силе, если
частоты расположены в невозрастающем порядке (возможны равные)?
Решение. Нет: если, скажем, имеются три буквы с частотой $$1/3$$,
то оптимальный код будет иметь длины слов $$1,2,2$$ (если бы два
кодовых слова имели длину $$1$$, то на третье уже не осталось бы
места), и они могут идти в любом порядке.
Заметим, однако, что при поиске оптимального кода (для
невозрастающих частот) мы вправе ограничиваться лишь
кодами, в которых длины кодовых слов неубывают (поскольку
кодовые слова для букв одинаковых частот можно переставлять
без изменения средней длины кода).
12.3.4.
Пусть частоты расположены в невозрастающем порядке
( $$p_1\ge p_2\ge\ldots \ge p_k$$ ), а длины слов в оптимальном коде
расположены в неубывающем порядке $$n_1\le n_2\le\ldots\le n_k$$.
Доказать, что $$n_{k-1}=n_k$$ (при $$k\ge 2$$ ).
Решение. Предположим, что это не так, и что есть единственное
самое длинное кодовое слово длины $$n_k$$. Тогда неравенство
Крафта-Макмиллана не может обращаться в равенство, поскольку
все слагаемые, кроме наименьшего (последнего), кратны
удвоенному последнему слагаемому. Значит, в этом
неравенстве есть запас, причем не меньший последнего слагаемого.
А тогда можно уменьшить $$n_k$$ на единицу, не нарушая
неравенства, что противоречит предположению об оптимальности
исходного кода.
Эта задача показывает, что при поиске оптимального кода можно
рассматривать лишь коды, в которых две самые редкие буквы имеют
коды одинаковой длины.
12.3.5.
Как свести задачу отыскания длин кодовых слов
оптимального кода для $$k$$ частот$$p_1\ge p_2\ge \ldots\ge p_{k-2}\ge p_{k-1} \ge p_k$$
к задаче поиска длин оптимального кода для $$k-1$$ частот$$p_1, p_2, \ldots, p_{k-2}, p_{k-1}+p_k$$
(частоты двух самых редких букв объединены)?
Решение. Мы уже знаем, что можно рассматривать лишь коды
с $$n_{k-1}\hm=n_k$$. Неравенство Крафта-Макмиллана тогда
запишется как$$\begin{multiline*}
2^{-n_1}+2^{-n_2}+\ldots+2^{-n_{k-2}}+2^{-n_{k-1}}+2^{-n_k}=\\
=2^{-n_1}+2^{-n_2}+\ldots+2^{-n_{k-2}}+2^{-n} \le 1,
\end{multiline*}$$
если положить $$n_{k-1}=n_k=n+1$$. Таким образом, числа $$n_1,\ldots,n_{k-2},n$$ должны удовлетворять неравенству Крафта
Макмиллана для $$k-1$$ букв. Средняя длины этих двух кодов
будут связаны:$$\begin{multiline*}
p_1 n_1+\ldots+p_{k-2} n_{k-2}+ p_{k-1} n_{k-1}+ p_k n_k = {}\\
{}= p_1 n_1+\ldots+p_{k-2} n_{k-2}+ (p_{k-1}+p_k)n + [p_{k-1}+p_k].
\end{multiline*}$$
Последнее слагаемое (квадратная скобка) не зависит от
выбираемого кода, поэтому минимизировать надо остальное, то есть
как раз среднюю длину кода с длинами слов $$n_1,\ldots,n_{k-2},n$$
для частот $$p_1,p_2,\hm\ldots,p_{k-2},p_{k-1}+p_k$$. После этого
надо положить $$n_{k-1}=n_k=n+1$$, и это даст оптимальный код для
исходной задачи.
Используя эту задачу, несложно составить рекурсивную программу
для отыскания длин кодовых слов. С каждым вызовом число букв
будет уменьшаться, пока мы не сведем задачу к случаю двух букв,
когда оптимальный код состоит из слов $$0$$ и $$1$$. Затем
можно найти и сами кодовые слова (согласно
задаче 12.2.3.). Но проще объединить эти действия
и сразу искать кодовые слова: ведь замена числа $$n$$ на два числа $$n+1$$ соответствует замене кодового слова $$P$$ на два
слова $$P0$$
и $$P1$$ на единицу большей длины (и эта последняя замена
сохраняет префиксность кода).
Код, построенный таким методом, называется кодом Хаффмена.
Мы доказали, что он имеет минимальную среднюю длину
среди всех кодов (для данных частот букв). В следующей задаче
оценивается число операций, необходимых для построения кода Хаффмена.
12.3.6.
Показать, что можно обработать частоты $$p_1,\ldots,p_k$$, сделав $$O(k \log k)$$ операций, после чего $$i$$ -ое кодовое слово
можно указать за время, пропорциональное его длине.
Указание.
Заметим, что оценка времени довольно сильная: только на
сортировку чисел $$p_i$$ уже уходит $$O(k \log k)$$ действий.
Поэтому, применяя предыдущую задачу, нужно использовать
результаты сортировки $$k$$ чисел при сортировке меньшего
количества чисел. Это можно сделать с помощью очереди
с приоритетами, вынимая два минимальных числа и добавляя их
сумму за $$O(\log k)$$ действий. Это позволяет определить,
какие две буквы надо соединять в одну на каждом шаге.
Параллельно с соединением букв можно строить дерево кодов,
проводя ребра (помеченные $$0$$ и $$1$$ ) от соединенной буквы к каждой из ее половинок. При этом требуется $$O(1)$$
действий на каждом шаге. После завершения построение
прослеживать код любой буквы можно
символ за символом.
12.4. Код Шеннона-Фано
Мы видели, как можно построить оптимальный код (имеющий
минимальную среднюю длину) для данного набора частот.
Однако эта конструкция не дает никакой оценки для средней
длины оптимального кода (как функции от частот $$p_i$$ ).
Следующие задачи указывает такую оценку (с абсолютной
погрешностью не более $$1$$ ).
12.4.1.
Показать, что для любых положительных частот $$p_1,\ldots,p_k$$ (в сумме равных единице) существует код
средней длиной не более $$H(p_1,\ldots,p_k)+1$$, где
функция $$H$$ (называемая энтропией Шеннона )
определяется формулой$$H(p_1,\ldots,p_n)= p_1 (- log_2 p_1)+\ldots + p_k (- log_2 p_k)$$
Решение. Если частоты $$p_i$$ представляют собой целые (отрицательные) степени двойки, то это утверждение почти
очевидно. Положим $$n_i=- log p_i$$ (здесь и далее все
логарифмы двоичные). Тогда $$2^{-n_i}=p_i$$ и потому для
чисел $$n_i$$ выполнено неравенство Крафта-Макмиллана. По
задаче 12.2.3. можно построить префиксный код
с длинами кодовых слов $$n_1,\ldots,n_k$$, и средняя длина
этого кода будет равна $$H(p_1,\ldots,p_k)$$ (и даже единицу
добавлять не надо).
Эта единица пригодится, если $$log p_i$$ не целые. В этом
случае надо взять наименьшее $$n_i$$, при котором $$2^{-n_i}
\le p_i$$. Для таких $$n_i$$ выполняется неравенство Крафта
Макмиллана, и они больше $$- log p_i$$ не более чем на
единицу (потому и после усреднения ухудшение будет не более
чем не единицу.
Построенный на основе этой задачи код называется кодом Шеннона-Фано.
Это построение легко извлекается из решения
задачи 12.2.3.: рассматривая числа $$n_i=-\lfloor\ log p_i\rfloor$$ (наименьшие целые числа, для которых $$2^{-n_i}\le p_i$$ ) в порядке убывания, мы отводим для каждого из
них кодовое слово и соответствующий участок отрезка $$[0,1]$$
слева направо.
При этом мы проигрываем в длине кода (по сравнению с оптимальным
кодом) не более единицы: как мы сейчас увидим, средняя длина
любого (в том числе и оптимального) кода не меньше $$H(p_1,\ldots,p_k)$$.
12.4.2.
(Для знакомых с математическим анализом) Доказать, что (при
данных положительных частотах, в сумме дающих единицу) средняя
длина любого (однозначного) кода не меньше $$H(p_1,\ldots,p_k)$$.
Решение. Имея в виду неравенство Крафта-Макмиллана, мы должны доказать такой факт: если$$2^{-n_1}+\ldots 2^{-n_k} \le 1,$$
то$$p_1 n_1 + \ldots + p_k n_k \ge H(p_1,\ldots,p_k).$$
Это верно для любых $$n_i$$, не обязательно целых. Удобно
перейти от $$n_i$$ к величинам $$q_i=2^{-n_i}$$ ; интересующее
нас утверждение тогда гласит, что если $$p_1,\ldots,p_k$$
и $$q_1,\ldots,q_k$$ - два набора положительных чисел,
и сумма чисел в каждом равна единице, то$$p_1 (-log q_1) +\ldots +p_k (-log q_k) \ge
p_1 (-log p_1) +\ldots +p_k (-log p_k).$$
Другими словами, выражение$$p_1 (-log q_1) +\ldots +p_k (-log q_k)$$
(рассматриваемое при фиксированных $$p_i$$ как функция на
множестве всех положительных $$q_1,\ldots,q_k$$, в сумме
равных единице) достигает минимума при $$q_i=p_i$$. Область
определения этой функции есть внутренность симплекса
(треугольника при $$n=3$$, тетраэдра при $$n=4$$ и т.д.) и при приближении к границе одно из $$q_i$$ становится малым, а его
минус логарифм уходит в бесконечность. Значит, минимум
функции достигается внутри области. В точке минимума градиент $$(-p_1/q_1,\ldots,-p_n/q_n)$$ должен быть перпендикулярен
плоскости, на которой функция определена (иначе сдвиг вдоль
этой плоскости уменьшал бы функцию), то есть все $$p_i/q_i$$
равны. Поскольку $$\sum p_i=\sum q_i=1$$, то это означает,
что $$p_i=q_i$$.
Другое объяснение: функция $$log$$ выпукла вверх, поэтому
для любых неотрицательных коэффициентов $$\alpha_i$$, в сумме
равных единице, и для любых точек $$x_i$$ из области
определения логарифма выполняется неравенство$$log \left(\sum \alpha_i x_i\right) \ge \sum \alpha_i log x_i.$$
Остается положить $$\alpha_i=p_i$$, $$x_i=q_i/p_i$$ ; в левой
части
будет логарифм единицы, то есть нуль, а $$\sum p_i \log
(q_i/p_i)$$ есть как раз разность между левой и правой частями
доказываемого неравенства.
Велика ли экономия от использования кодов, описанных в этом
разделе? Это, конечно, зависит от частот букв: если они все
одинаковые, то никакой экономии не будет. Легко заметить,
что в русском языке разные буквы имеют разную частоту.
Если, скажем, в текстах (TeX-файлах) этого курса (на
момент эксперимента) оставить только $$33$$ строчные русские
буквы от "а" до "я", а все остальные символы не
учитывать, то самой частой буквой будет буква "о"
(частота $$0{,}105$$ ), а самой редкой - твердый знак (частота $$0{,}00019$$ ). Значение энтропии Шеннона при этом будет
равно $$4{,}454$$ (сравните с $$5$$ битами, необходимыми для кодирования $$32$$ букв). Выигрыш не так велик. Он будет
больше, если учитывать также и другие символы (прописные
буквы, знаки препинания и др.), которые встречаются
в тексте гораздо реже или вовсе не встречаются.
Наконец, можно кодировать не буквы, а двухбуквенные
комбинации или еще что-нибудь. Именно так поступают
популярные программы сжатия информации (типа zip),
которые позволяют сократить многие тексты в полтора-два
раза (а некоторые другие файлы данных - и в большее число
раз).
12.4.3.
Компания M. утверждает, что ее новая программа суперсжатия
файлов позволяет сжать любой файл длиной больше $$100\,000$$ байтов по крайней мере на $$10\%$$ без потери
информации (можно восстановить исходный файл по его сжатому
варианту). Доказать, что она врет.
