© Иван Рощин, Москва

Носители информации: назад к бумаге?

(«Радиомир. Ваш компьютер» 1—3/2004)
Исправленная версия.

Много лет назад для хранения машинно-читаемой информации использовали бумажные носители — перфокарты и перфоленты. В отдельных случаях, для хранения небольшого количества информации, бумагу используют и сейчас (штрих-коды). Но для хранения больших объёмов информации теперь используют магнитные и оптические носители. Значит ли это, что использование бумаги для этой цели уже не имеет смысла?

А как вообще можно хранить на бумаге большой объём машинно-читаемой информации? На первый взгляд, очень просто: подготовить изображение, содержащее нужную информацию (например, белый пиксел — 0, чёрный — 1), и с помощью принтера напечатать это изображение на бумаге. А для чтения информации — использовать сканер.

Так, на рис. 1 вы можете увидеть, как при этом будет выглядеть исполняемый файл моей программы Text Corrector, размер которого — 848 байтов (6784 бита). Он представлен в виде чёрно-белого изображения размером 100x68, при этом даже остались неиспользуемые 16 пикселов.

Рис. 1

Вычислим, сколько информации (в мегабайтах) может уместиться на одной странице формата A4 (210x297 мм), если печать производится с разрешением 600 dpi (т.е. 600 точек на дюйм — один дюйм равен 25,4 мм):

Немало! Сравним это с тем объёмом информации, который умещается на одной странице при печати обычного, человеко-читаемого :–) текста. Например, в этом журнале страница содержит примерно 6000 символов текста. Если считать, что каждый символ кодируется одним байтом, получим 6000 байтов. А при использовании вышеописанного способа на той же странице можно уместить в (4,15*2²⁰)/6000~=700 раз больше информации. Да ещё учтём, что текст можно предварительно сжать: если считать, что он сжимается в три раза, получим, что на одной странице можно поместить информацию, содержащуюся примерно на 2000 страницах текста!

Ну как, ещё не упали со стула? :–) А теперь подумаем, почему же такой способ хранения информации не используют. Точнее — может, кто-то и использует, просто я об этом не знаю, но даже если так, всё равно получается, что этот способ не распространён. Может быть, не знают о нём? С одной стороны, в самом деле, публикации на эту тему мне не попадались. Но с другой стороны — понятно, что этот способ слишком очевиден, так что наверняка не я один задумывался над его использованием.

Так в чём же дело? Видимо, есть у этого способа какие-то недостатки. :–) Возможно, кто-то и хотел бы его использовать, но из-за этих недостатков посчитал способ непригодным. С другой стороны, может быть, остались незамеченными какие-то его достоинства.

В общем, я решил изложить здесь свои соображения по поводу этого способа, рассматривая его с разных сторон. Может быть, что-то в моих рассуждениях окажется новым, на что не обратили внимания те, кто раньше шёл по этому пути.

При использовании дискет, компакт-дисков и других подобных носителей информации, если мы что-то записали на них, то потом то же самое и прочитаем. С бумагой не так. Пиксел напечатанного изображения не будет в точности соответствовать пикселу считанного изображения из-за несовпадения растра. Так, на рис. 2 а изображён в увеличенном виде левый верхний угол рис. 1, а на рис. 2 б — изображение, которое может получиться при его сканировании. (На самом деле у меня нет ни принтера, ни сканера, так что для получения этого изображения мне пришлось написать специальную программу, которая пытается моделировать искажения, возникающие при сканировании.)

Рис. 2

а)

б)

Таким образом, прочитанное со сканера изображение придётся дополнительно обработать, чтобы извлечь записанную информацию. А для этого надо знать, как именно искажается изображение при печати и последующем сканировании, и разработать специальный алгоритм, восстанавливающий исходное изображение.

Замечу, что имеет смысл архивировать исходные данные перед печатью, чтобы уменьшить их размер. На это будет затрачено некоторое время, но зато сократится расход бумаги и красителя, уменьшится время печати и последующего сканирования (в итоге даже можем получить выигрыш во времени).

Выше упоминалось, что при печати с разрешением 600 dpi на странице можно уместить 4,15 МБ информации. Но всегда ли это значение достижимо на практике? Очевидно, нет. При печати, может быть, принтер не позволит использовать абсолютно всю площадь листа. Не каждый принтер может печатать с высоким разрешением. При печати точки могут расплываться, так что при последующем сканировании (даже с высоким разрешением) разобрать напечатанное уже не удастся. Фактическое максимальное разрешение печати зависит от многих факторов: от конкретной модели принтера, от используемой бумаги, от используемых чернил (для струйного принтера), от используемого тонера (для лазерного принтера) и, возможно, даже от температуры и влажности воздуха. :–) Только экспериментально можно проверить, с каким разрешением можно печатать, сохраняя разборчивость каждого пиксела.

Объём полезной хранимой информации уменьшается ещё и по той причине, что бумага — недостаточно надёжный носитель, чтобы пренебречь возможными ошибками при его использовании. Если, например, на бумаге попадётся тёмное пятнышко — это будет означать уже несколько ошибочных пикселов. Или лист бумаги может быть повреждён уже после печати (например, если он был сложен пополам — впоследствии при сканировании пикселы, расположенные в районе сгиба, могут быть прочитаны с ошибкой; или если лист намок, а потом высох и покоробился).

Чтобы обнаруживать ошибки, придётся хранить контрольные суммы (CRC) записанных данных. А если мы хотим ещё и автоматически исправлять ошибки, придётся хранить избыточную информацию для их исправления. Как именно формировать эту избыточную информацию и какой объём она займёт по сравнению с полезной информацией — отдельный вопрос, зависящий от количества и характера ошибок, которые предполагается исправлять.

Вроде бы понятно, что существует ограничение: разрешение сканера должно быть не меньше разрешения, с которым было напечатано изображение, иначе в одном пикселе получаемого при сканировании изображения будет суммироваться яркость нескольких пикселов напечатанного изображения, и восстановить напечатанное изображение не получится. А нельзя ли как-нибудь преодолеть это ограничение, тем самым расширив область применения описываемого способа хранения информации?

Известны алгоритмы (например, описанные в [1]), позволяющие за счёт наличия нескольких различных изображений какого-либо объекта с низким разрешением построить результирующее изображение этого объекта с большим разрешением. О практической разработке в этой области рассказывается в [2]: обрабатывая последовательность изображений с разрешением 32x32, удавалось добиться разрешения не хуже, чем 256x256.

То есть теоретически достаточно несколько раз выполнить сканирование одного и того же напечатанного изображения, каждый раз немного сдвигая лист бумаги, а затем обработать полученные изображения с помощью такого алгоритма, чтобы повысить разрешение. Так, на рис. 3 вы можете видеть четыре изображения буквы «A» с низким разрешением и полученное на их основе изображение с более высоким разрешением (опять же замечу, что исходные четыре изображения я получил не в результате реального сканирования, а с помощью специальной программы; результирующее изображение, впрочем, честно рассчитывалось по первым четырём).

Рис. 3

+

+

+

=

Далее я попробую рассказать о ситуациях, когда бумага может в чём-то оказаться выгоднее по сравнению с другими носителями данных (дискеты, компакт-диски).

Хранить данные на бумаге может быть дешевле по сравнению с дискетами (конечно, речь идёт о неизменяемых данных, иначе дискеты выгоднее за счёт их повторного использования). Так что, может быть, вы захотите сэкономить на дискетах, пусть и не так удобно возиться с бумагой. По крайней мере, я бы не отказался хранить часть своих данных, к которым сравнительно редко приходится обращаться (например, архивные копии), именно таким образом.

Кстати, стоимость печати информации на бумаге можно уменьшить за счёт использования… уже использованной бумаги! Да-да! Как же это возможно?

Пусть мы имеем ненужный лист бумаги с напечатанным на нём текстом. При этом закрашена, как правило, лишь небольшая часть площади листа. При описании картриджей для принтеров обычно указывается, на печать какого количества страниц их хватит, из расчёта 5% заполнения страницы. Так что за основу можно взять это значение.

Тогда, если считать, что в печатаемом изображении количество белых и чёрных пикселов одинаково, то лишь 2,5% пикселов окажутся ошибочными. В самом деле, ошибки будут возникать лишь на белых пикселах, которые при печати попали на уже закрашенный участок бумаги и потом прочитались как чёрные. А если чёрный пиксел при печати попадёт на уже закрашенный участок бумаги, это не приведёт к ошибке.

Зная характер возникающих ошибок, можно разработать формат с избыточной информацией, позволяющий исправлять эти ошибки. Естественно, избыточной информации придётся добавлять больше, чем при печати на чистом листе, но, как мне кажется, не очень много по сравнению с объёмом полезной информации.

Попробуем оценить величину избыточности кода, необходимую для исправления ошибок, возникающих при печати на уже использованной бумаге. Как известно, в теории информации доказывается, что любому конечному уровню помех соответствует определённая величина избыточности кода, являющаяся необходимой и достаточной для того, чтобы вероятность правильного приёма сообщений была как угодно близка к единице.

Считаем, что в кодируемом сообщении поровну нулей и единиц, 0 кодируется белым пикселом, а 1 — чёрным, относительное количество уже имеющихся на бумаге чёрных пикселов равно k (т.е. вероятность того, что печатаемый пиксел попадёт на уже имеющийся на бумаге чёрный пиксел, равна k), и все другие источники ошибок отсутствуют.

Величина необходимой избыточности кода равна потере информации при передаче сообщения. В [6] потеря информации обозначается H_y(x) и приводится формула для её вычисления:

Hy(x) = –		pi		pi(j) log pi(j),
	(i)		(j)

Если в качестве единицы потери информации принять бит, то основание логарифма в этой формуле должно равняться двум.

Рассмотрим потерю информации при передаче одного бита. В нашем случае p₀ (вероятность приёма 0) будет равна 0,5*(1–k), а p₁ (вероятность приёма 1) равна 0,5*(1+k).

Если был принят 0 — значит, точно был передан 0, т.е. p₀(0)=1 и p₀(1)=0. Если же был принят 1, то вероятность того, что был передан 0, равна k/(1+k), а вероятность того, что был передан 1, равна 1/(1+k), т.е. p₁(0)=k/(1+k) и p₁(1)=1/(1+k).

На рис. 4 показана зависимость H_y(x) от k при изменении k от 0 до 1.

Рис. 4

При k=0,05 (т.е. когда на бумаге уже имеется 5% чёрных пикселов) потеря информации при передаче одного бита равна примерно 0,145 бита. То есть при передаче одного бита теоретически можно передать 1–0,145=0,855 бита полезной информации (а 0,145 бита — это будет избыточная информация, необходимая для исправления ошибок при передаче). Иными словами, за счёт добавления избыточной информации придётся увеличить размер передаваемых данных в 1/0,855~=1,17 раза.

Правда, теория не даёт ответа на вопрос, каким именно образом надо кодировать данные, чтобы исправлять все ошибки при таком уровне избыточности. Утверждается лишь, что такой код существует.

Итак, при печати на уже использованной бумаге сводятся к нулю расходы на бумагу и одновременно решается проблема утилизации использованной бумаги. :–) С другой стороны, я не знаю: возможно, печать на уже использованной бумаге может повредить какой-либо модели принтера?

Продолжу рассказ о возможных преимуществах бумаги.

Дискеты не в такой степени надёжны, как хотелось бы. Иногда вроде бы без видимой причины «не читается» один или несколько секторов, и происходит потеря информации. Наверно, каждый сможет вспомнить такие случаи. А при хранении информации на бумаге, как мне кажется, можно достичь большей надёжности за счёт автоматического добавления избыточной информации, позволяющей восстановить записанные данные даже при их повреждении.

Да, при записи на дискету тоже можно добавлять избыточную информацию (например, упаковав данные RAR’ом с установленной соответствующей опцией). Но об этом должен заботиться сам пользователь, и далеко не все пользуются этим. К тому же избыточная информация, добавленная к файлам, не поможет, если из-за повреждения каталога окажется утраченной информация о расположении файлов на диске, то есть просто не будет доступа к файлам.

Для записи компакт-дисков требуется достаточно мощный компьютер, дорогой пишущий привод. А для печати и сканирования можно использовать практически любой компьютер — может быть, даже ZX Spectrum.

При записи данных на компакт-диск или дискету приходится вручную делать надписи об их содержимом на наклейке, этикетке (или прямо на компакт-диске специальным маркером), чтобы не перепутать, на каком диске что записано. А при записи данных на бумажном носителе эти сведения могут быть напечатаны автоматически, одновременно с печатью содержимого!

Справедливости ради отмечу, что при записи компакт-дисков также имеется возможность автоматически сформировать в неиспользуемой области диска видимое невооружённым глазом произвольное изображение или текст (например, с описанием содержимого диска) (см. [5]). Но понятно, что с бумаги читать всё-таки удобнее.

Может быть, кто-то скажет, что не так удобно возиться со сканером по сравнению с дискетой. Но кто сказал, что сканеры и в будущем останутся такими же, как сейчас? Возможно даже, они исчезнут как самостоятельное устройство, а будут совмещены с экраном, как описано в [3]. Просто прикладываешь лист бумаги к экрану — и информация уже в памяти компьютера! Это даже проще, чем вставить дискету в дисковод!

Можно представить ситуацию, когда надо передать информацию с одного компьютера на другой, но традиционные способы по каким-либо причинам не подходят. Например, перенести информацию на дискетах нельзя, потому что на одном из компьютеров нет дисковода; связать компьютеры сетевым кабелем или вытащить винчестер из одного компьютера и подключить к другому — также по каким-то причинам нельзя или неудобно. В этом случае использование бумаги в качестве промежуточного носителя информации может быть единственным выходом; надо только, чтобы можно было подключить принтер к компьютеру-источнику информации и сканер — к компьютеру-приёмнику.

И ещё одна немаловажная проблема — моральное старение носителей информации и устройств для чтения этих носителей. Легко ли сейчас найти компьютер с дисководом 5,25"? Нет? А значит, нелегко и прочитать информацию, записанную на таких дискетах. Через несколько лет ситуация может повториться и с дискетами 3,5": уже сейчас производители выпускают компьютеры без этих дисководов. Вполне возможно, та же судьба ожидает и другие используемые в настоящее время носители информации.

А для чтения информации с бумажных носителей не нужно никаких специальных устройств, кроме сканера. Возможно, в будущем сканеры будут выглядеть не так, как сейчас (опять же, см. [3]), но исчезновения их, по-видимому, ожидать не приходится.

С помощью сканера и сейчас можно было бы без особого труда прочитать информацию, скажем, с перфокарты. Надо только знать, каким образом эта информация была закодирована. Замечу, что при печати информации на бумаге можно автоматически печатать на том же листе бумаги и инструкцию (на естественном человеческом языке) по «расшифровке» напечатанной информации.

Кстати, печать может производиться и типографским способом, при этом каждая копия будет очень дешёвой. Сейчас к некоторым книгам, журналам прилагают компакт-диск или дискету, но это заметно удорожает издание. А можно было бы печатать информацию в машинно-читаемом виде прямо в книге, журнале (может быть, и не всю информацию, которая на диске, а лишь наиболее важную). Тогда, если часть тиража продаётся с диском, а часть — без него, покупатель сам сможет решить, что для него лучше: купить версию с диском (более удобно пользоваться, но дороже) или без диска (придётся возиться со сканером, но зато экономия!).

В моих статьях, публикуемых в этом журнале, часто не приводятся исходные тексты программ — из-за слишком большого их объёма. А можно было бы печатать и исходные тексты, и исполняемые файлы этих программ в машинно-читаемом виде — много места это бы не потребовало.

Вроде бы понятно, что при этом для хранения информации потребуется дополнительный объём бумаги, что также удорожит издание. Но можно… вообще не использовать дополнительно ни одного квадратного сантиметра бумаги и вместе с тем хранить нужную информацию. Как?

Если текст печатается не на белом фоне, то информацию можно хранить непосредственно в фоне текста. Допустим, фон должен быть светло-жёлтым (50% белого и 50% жёлтого). Тогда можно вместо равномерного распределения белых и жёлтых пикселов (рис. 5 а) добиться того же оттенка, закодировав исходные данные так, что 0 будет представлен белым пикселом, а 1 — жёлтым (рис. 5 б).

Рис. 5

а)

б)

При этом, если в исходных данных 0 и 1 расположены в целом равномерно (а если исходные данные получены в результате архивации, то примерно так и будет), то получившийся фон не будет заметно отличаться от исходного (если и будут заметны некоторые неравномерности цвета фона, чтению текста это не помешает). Но теперь в фоне уже хранится «наша» информация, и при сканировании можно будет её извлечь.

Разумеется, при этом придётся обязательно использовать избыточную информацию, так как часть пикселов фона перекрывается пикселами текста, и закодированная в них информация будет потеряна (впрочем, как я уже упоминал, пикселы текста обычно составляют небольшую долю от всей площади страницы). Другой вариант — заранее учесть, какие пикселы фона будут перекрыты текстом, и не использовать их для хранения информации, а при сканировании различать функции пикселов по их цвету: если пиксел белый или жёлтый, то он относится к фону и несёт информацию, а если пиксел чёрный — значит, это пиксел текста (но это годится только для цветного фона).

В случае чёрно-белой печати, когда текст печатается на сером фоне, представляющем собой упорядоченную смесь чёрных и белых пикселов (рис. 6), можно точно так же вместо обязательной упорядоченности расположить пикселы фона в соответствии с кодируемыми данными так, что полученное изображение будет почти неотличимо от исходного.

Рис. 6

Допустим, надо получить изображение, как на рис. 6, но поместить в фон некоторую информацию, количество 0 и 1 в которой примерно равно и они перемешаны более-менее равномерно. Тогда фон формируем так: сначала берём фон с вдвое большей плотностью чёрных пикселов (рис. 7).

Рис. 7

Каждому чёрному пикселу фона ставим в соответствие один бит кодируемой информации, а потом те пикселы, которым соответствуют нулевые биты, делаем не чёрными, а белыми (рис. 8).

Рис. 8

В результате общий оттенок фона заметно не изменится по сравнению с рис. 6, так как соотношение белых и чёрных пикселов в среднем останется тем же самым.

Поверх полученного фона накладываем изображение текста (рис. 9).

Рис. 9

Ещё одна идея использования фона для хранения данных возникла у меня под влиянием публикации [4]. Если чёрные пикселы фона, расположенные в узлах регулярной сетки, находятся на достаточно большом расстоянии друг от друга (промежуток между двумя соседними пикселами по вертикали, горизонтали и диагонали — не менее двух пикселов), то можно сделать так: сдвинуть каждый чёрный пиксел фона на один из восьми соседних пикселов (рис. 10) либо оставить его на месте.

Рис. 10

Как при этом изменяется фон, показано на рис. 11.

Рис. 11

Каждому чёрному пикселу фона будут соответствовать девять возможных вариантов его расположения. Таким образом, каждый такой пиксел будет нести log₂9~=3,17 бита информации.

При этом ещё и обеспечивается общая однородность фона (отсутствие заметных светлых или тёмных участков), какие бы данные ни кодировались, — потому что количество чёрных пикселов не меняется, а меняются только их координаты, причём не более чем на 1 по каждому направлению.

Если исходное расстояние между чёрными пикселами фона больше двух пикселов, то можно сдвигать пикселы и на большую величину. При этом у каждого пиксела будет больше возможных положений и, соответственно, он будет нести больше информации.

Теперь попробуем рассмотреть ещё одну интересную проблему. Вот вы печатаете данные: бит 0 представлен белым (незакрашенным) пикселом, бит 1 — чёрным (закрашенным). Если вы сами платите за израсходованный краситель (чернила, тонер, красящая лента), то получается, что чёрный пиксел обходится вам дороже белого. Тогда имеет смысл так перекодировать данные, чтобы уменьшить количество чёрных пикселов (пусть даже за счёт увеличения количества белых пикселов — они ведь дешевле), и таким образом сократить стоимость печати данных.

Приведу пример. Пусть чёрный пиксел стоит в три раза дороже белого. Здесь и далее будем считать, что в исходных данных каждый бит с одинаковой вероятностью равен 0 или 1 (если исходные данные получены в результате архивации, то примерно так и будет).

Примем цену белого пиксела за 1 у.е., тогда цена чёрного — 3 у.е. В среднем нулей в данных столько же, сколько единиц, и при обычном способе печати цена записи одного бита составит (1+3)/2=2 у.е.

А теперь перекодируем исходные данные, заменяя каждые два бита так, как показано ниже:

00 -> 1
01 -> 01
10 -> 001
11 -> 000

Так как в исходных данных в среднем поровну комбинаций 00, 01, 10 и 11, то в среднем два бита исходной информации будут закодированы в (1+2+3+3)/4=2,25 бита, из них нулей будет (0+1+2+3)/4=1,5, а единиц — (1+1+1+0)/4=0,75.

Тогда средняя цена записи двух битов исходной информации после перекодирования равна 1,5*1+0,75*3=3,75 у.е. Средняя цена записи одного бита, соответственно, вдвое меньше и равна 1,875 у.е — меньше первоначальных 2 у.е.

(Замечу, что вышеописанное кодирование не является идеальным: как мы увидим дальше, теоретический минимум цены записи одного бита при данном соотношении цен белого и чёрного пикселов равен примерно 1,81 у.е.)

Итак, в чём же суть проблемы? В том, чтобы узнать, как при заданном соотношении цен белого и чёрного пикселов надо перекодировать исходные данные, чтобы стоимость их записи была наименьшей. По идее, аналогичная проблема должна рассматриваться в теории передачи информации (если время передачи 1 по каналу связи больше времени передачи 0 и надо добиться наименьшего времени передачи данных). Но информации о её решении я не нашёл (не знаю — может, плохо искал), поэтому привожу собственные размышления на эту тему.

Пусть чёрный пиксел в k раз дороже белого (k>1). Как уже упоминалось выше, считаем, что в исходных данных каждый бит с одинаковой вероятностью равен 0 или 1. Пусть мы имеем наилучший (идеальный) для данного k перекодировщик исходных данных, т.е. обеспечивающий в среднем минимальную цену записи одного бита исходной информации после перекодирования (обозначим эту цену C). Как именно работает этот перекодировщик, мы пока не знаем, но это сейчас неважно.

Пусть доля нулей в перекодированных данных в среднем равна x (каждый бит перекодированных данных равен 0 с вероятностью x и равен 1 с вероятностью 1–x). Очевидно, что x>0,5, так как уменьшить C можно только за счёт относительного увеличения количества нулей в данных.

Также очевидно, что размер перекодированных данных будет в среднем больше размера исходных данных. Это следует из того, что количество информации после перекодирования должно сохраниться, а если после перекодирования нулей стало в среднем больше, чем единиц, то каждый бит перекодированных данных будет содержать менее одного бита информации, а значит, для хранения того же количества информации, что было в исходных данных, понадобится больше битов.

Попробуем вычислить x. Средняя цена записи одного бита перекодированных данных (обозначим её C') равна x*c₀+(1–x)*c₁, где c₀ — цена белого пиксела, c₁ — цена чёрного пиксела. Теперь определим, сколько битов перекодированных данных будут содержать столько же информации, сколько её содержит один бит исходных данных (а он и содержит один бит информации).

Информационная ёмкость одного бита перекодированных данных (обозначим её H) равна –(x*log₂x+(1–x)log₂(1–x)). При x>0,5 H<1. Для записи одного бита информации, следовательно, потребуется 1/H битов перекодированных данных (больше одного бита).

Из вышесказанного следует, что C=C'/H=(x*c₀+(1–x)*c₁)/–(x*log₂x+(1–x)log₂(1–x)). Так как c₁/c₀=k (по определению), то, если принять c₀=1 (как мы увидим далее, x не зависит от c₀), получим:

Так как C минимальна (по условиям задачи), для определения x достаточно найти минимум вышеприведённой функции C(x). Значение x, при котором достигается минимум, и будет искомым. Минимум можно искать либо численным методом, либо попробовать вывести формулу (приравнять нулю производную функции C(x) и решить полученное уравнение — но этот способ я не пробовал).

На рис. 12 приведены графики функции C(x) при k=1,2,3,4,5. Минимумы отмечены красными точками. Видно, что лишь при k=1, то есть когда цена белого пиксела равна цене чёрного, выгодным является равная доля нулей и единиц в перекодированных данных (то есть можно их вообще не перекодировать). А с ростом k доля нулей в перекодированных данных также должна возрастать, чтобы C была минимальной.

Рис. 12

Значения x, при которых достигается минимум C, и соответствующие минимальные значения C приведены в табл. 1. Также там приведён получаемый выигрыш от перекодирования — на сколько процентов дешевле получается запись информации (т.е. на сколько процентов минимальное C меньше, чем C(0,5)).

На рис. 13 вы можете увидеть график зависимости x от k при изменении k от 1 до 10.

Рис. 13

Итак, мы смогли определить некоторые характеристики идеального перекодировщика: среднюю долю нулей в перекодированных данных (отсюда легко находится и среднее соотношение нулей и единиц в перекодированных данных) и среднюю цену записи одного бита исходных данных после перекодирования. Таким образом, при разработке своего перекодировщика мы получили возможность ориентироваться на эти характеристики.

Далее я приведу две различных идеи перекодирования.

Первая идея: построить префиксный код с соотношением 0 и 1, близким к теоретически оптимальному. Исходные данные будем кодировать группами по n битов (чем больше n, тем лучше), для чего построим дерево с 2ⁿ листьями. Строим дерево сверху вниз, и при каждом разветвлении выбираем соотношение количеств листьев в двух получающихся поддеревьях (с вершиной 0 и с вершиной 1) так, чтобы оно было возможно ближе к теоретически оптимальному соотношению (и, конечно, чтобы получилось хотя бы по одному листу в каждом поддереве). Поэтому и выгоднее брать большое n — тогда соотношения будут более близки к оптимальным.

Я не располагаю каким-либо доказательством того, что полученный по этому алгоритму префиксный код будет лучшим из всех возможных префиксных кодов для данного n.

Интуитивное обоснование алгоритма следующее: так как каждая развилка в дереве соответствует одному биту для какой-то группы кодов (так, самая верхняя развилка соответствует первому биту для всех кодов), и по условиям задачи все коды равновероятны, то, выбирая соотношение количеств листьев в поддеревьях возможно более близким к оптимальному, мы добиваемся, чтобы соотношение нулей и единиц в этом бите для этой группы кодов было близко к оптимальному. А так как, в свою очередь, каждый бит каждого кода соответствует какой-то развилке дерева, то соотношение нулей и единиц в битах кода будет в среднем достаточно близко к оптимальному: в первых битах кода — особенно близко, а в последующих битах — в среднем всё менее близко (понятно, что когда мы делим большое целое число на два целых числа в нужной пропорции, погрешность в среднем будет меньше, чем когда мы делим меньшее число в той же пропорции). В последнем бите двух самых длинных кодов соотношение нулей и единиц будет всегда 1:1 — поэтому такое кодирование заведомо неидеально.

Продемонстрирую работу алгоритма на примере. Пусть k=3, тогда x~=0,68 (см. табл. 1), отсюда отношение количества нулей к количеству единиц должно быть равно примерно 2,13. Пусть n=4, т.е. кодируем группами по четыре бита.

Четыре бита — значит, в дереве будет 16 листьев. Разбиваем их на две части так, чтобы количество листьев в первой части относилось к количеству листьев во второй части возможно ближе к 2,13. Получаем 11 листьев в первой части и 5 во второй. Таким образом, в поддереве с вершиной 0 будет 11 листьев, а в поддереве с вершиной 1 — 5 листьев. Итак, первый уровень дерева будет выглядеть следующим образом:

Второй уровень. Аналогично разбиваем 11 на 7 и 4, а 5 — на 3 и 2:

Третий уровень. Разбиваем 7 на 5 и 2, 4 — на 3 и 1, 3 — на 2 и 1, 2 — на 1 и 1:

Четвёртый уровень. Разбиваем 5 на 3 и 2, 2 — на 1 и 1, 3 — на 2 и 1:

Пятый уровень. Разбиваем 3 на 2 и 1, 2 — на 1 и 1:

Шестой уровень. Разбиваем 2 на 1 и 1:

Дерево построено, теперь произвольным образом (так как вероятности всех комбинаций в исходных данных одинаковы) сопоставляем 16 комбинаций с 16 полученными кодами — например, так:

0000 -> 000000
0001 -> 000001
0010 -> 00001
0011 -> 00010
0100 -> 00011
0101 -> 0010
0110 -> 0011
0111 -> 01000
1000 -> 01001
1001 -> 0101
1010 -> 011
1011 -> 1000
1100 -> 1001
1101 -> 101
1110 -> 110
1111 -> 111

Количество нулей во всех 16 кодах — 44, единиц — 25. Соотношение 44/(44+25)~=0,64, что достаточно близко к теоретически оптимальному ~0,68. В среднем на кодирование четырёх битов надо затратить 44/16=2,75 нулей и 25/16=1,5625 единиц. Тогда цена четырёх битов — 2,75+3*1,5625=7,4375 у.е. Цена одного бита в четыре раза меньше и примерно равна 1,86 у.е. А если бы мы не перекодировали данные — цена была бы равна 2 у.е.

Вторая идея перекодирования — использовать арифметическое сжатие «наоборот». Известно, что если в исходных данных соотношение 0 и 1 отличается от 1:1, то можно сжать их с помощью арифметического метода. Размер сократится, а нулей и единиц станет примерно поровну. А у нас обратная ситуация: имеются исходные данные, где нулей и единиц примерно поровну (по условиям задачи), а надо получить данные большего размера, но с заданным соотношением нулей и единиц. Тогда можно считать исходные данные упакованными арифметическим методом и распаковать их, получив нужное соотношение 0 и 1 (а размер вырастет). При чтении же — наоборот, сжимаем считанные данные, и в результате получаем исходные данные. Вот такая идея. На практике не проверял. :–)

Источники

1. FIDO-конференция RU.ALGORITHMS, тема «Восстановление изображения».
2. «Паучий глаз». «Компьютерра» 14/2001, стр. 11.
3. «Приложите лицо к экрану…». «Компьютерра» 14—15/2003, стр. 10.
4. В.Иванченко. «…Достать чернил и плакать». «Компьютерра» 14/2000, стр. 12.
5. «И написал в уголке…». «Компьютерра» 25/2002, стр. 6.
6. М.А.Карцев. «Арифметика цифровых машин». Москва, «Наука», 1969.