Код Хаффмана

Алгоритм Хаффмана — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m₂ с более чем двумя символами.

Этот метод кодирования состоит из двух основных этапов:

1. Построение оптимального кодового дерева.
2. Построение отображения код-символ на основе построенного дерева.

Кодирование Хаффмана

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

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

Символ	А	Б	В	Г	Д
Частота	15	7	6	6	5

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

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

Символ	А	Б	В	Г	Д
Код	0	100	101	110	111

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

При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ). Заметим, что энтропия источника, независимым образом порождающего символы с указанными частотами, составляет ~2,1858 бита на символ, то есть избыточность построенного для такого источника кода Хаффмана, понимаемая как отличие среднего числа бит на символ от энтропии, составляет менее 0,05 бит на символ.

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

Адаптивное сжатие

Адаптивное сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании.

В создании алгоритма адаптивного кодирования Хаффмана наибольшие сложности возникают при разработке процедуры обновления модели очередным символом. Теоретически можно было бы просто вставить внутрь этой процедуры полное построение дерева кодирования Хаффмана, однако, такой алгоритм сжатия имел бы неприемлемо низкое быстродействие, так как построение Н-дерева — это слишком большая работа, и производить её при обработке каждого символа неразумно. К счастью, существует способ модифицировать уже существующее Н-дерево так, чтобы отобразить обработку нового символа. Наиболее известными алгоритмами перестроения являются алгоритм Фоллера-Галлагера-Кнута (FGK) и алгоритм Виттера.

Все алгоритмы перестроения дерева при считывании очередного символа, включают в себя две операции:

Первая — увеличение веса узлов дерева. Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу. Затем увеличиваем вес родителя, чтобы привести его в соответствие с новыми значениями веса потомков. Этот процесс продолжается до тех пор, пока мы не доберемся до корня дерева. Среднее число операций увеличения веса равно среднему количеству битов, необходимых для того, чтобы закодировать символ.

Вторая операция — перестановка узлов дерева — требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный вес узла стал больше, чем вес следующего по порядку узла. Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то дерево перестанет быть деревом Хаффмана.

Чтобы сохранить упорядоченность дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве (при этом родители каждого из узлов тоже изменятся). На этом операция перестановки заканчивается.

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

Биграммная модель

Существует разновидность алгоритма Хаффмана, использующая контекст. В данном случае размер контекста равен единице (биграммный — два символа, триграммный — три и так далее). Это метод построения префиксного кода для моделей высших порядков, уже не источника без памяти. Он использует результат (предыдущей операции) операции над предыдущей буквой совместно с текущей буквой. Строится на основе цепи Маркова с глубиной зависимости <math>r = 1</math>.

Алгоритм:

1. Строится таблица в виде квадрата — распределение вероятностей на биграммах. Сразу вычисляется стартовая схема, с помощью которой будет кодироваться только первая буква. Строками в таблице, например, являются предыдущие буквы, а столбцами текущие.
2. Вычисляются вероятности для кодовых деревьев для контекстов.
3. По контекстам длины <math>r = 1</math> строятся остальные кодовые деревья, с помощью которых будут кодироваться все остальные символы (кроме первого).
4. Выполняется кодирование, первый символ кодируется согласно стартовой схеме, все последующие — исходя из кодовых деревьев для контекстов (предыдущего символа).

Декодирование выполняется аналогично: из стартовой кодовой схемы получаем первый контекст, а затем переходим к соответствующему кодовому дереву. Более того, декодеру необходима таблица распределения вероятностей.

Пример:

Допустим, сообщение, которое надо закодировать «abcabcabc». Нам заранее известна таблица частот символов (на основе других данных, например, статистических данных по словарю):

	a	b	c	Сумма
a	<math>\tfrac{3}{16}</math>	<math>\tfrac{1}{16}</math>	<math>\tfrac{1}{16}</math>	<math>\tfrac{5}{16}</math>
b	<math>\tfrac{1}{8}</math>	<math>\tfrac{1}{16}</math>	<math>\tfrac{1}{8}</math>	<math>\tfrac{5}{16}</math>
c	<math>\tfrac{1}{8}</math>	<math>\tfrac{1}{8}</math>	<math>\tfrac{1}{8}</math>	<math>\tfrac{6}{16}</math>

Имеем стартовую схему: <math>(a = \tfrac{5}{16}, b = \tfrac{5}{16}, c = \tfrac{6}{16})</math>. Сортируем по убыванию: <math>(c = \tfrac{6}{16}, a = \tfrac{5}{16}, b = \tfrac{5}{16})</math> и строим кодовое дерево Хаффмана.

Для контекста «a» имеем:

• <math>p(a / a) = p(a, a) / p(a) = \tfrac{3}{16} \div \tfrac{5}{16} = \tfrac{3}{5}</math>,
• <math>p(b / a) = p(b, a) / p(a) = \tfrac{1}{16} \div \tfrac{5}{16} = \tfrac{1}{5}</math>,
• <math>p(c / a) = p(c, a) / p(a) = \tfrac{1}{16} \div \tfrac{5}{16} = \tfrac{1}{5}</math>.

Для контекста «b» имеем:

• <math>p(a / b) = p(a, b) / p(b) = \tfrac{1}{8} \div \tfrac{5}{16} = \tfrac{2}{5}</math>,
• <math>p(b / b) = p(b, b) / p(b) = \tfrac{1}{16} \div \tfrac{5}{16} = \tfrac{1}{5}</math>,
• <math>p(c / b) = p(c, b) / p(b) = \tfrac{1}{8} \div \tfrac{5}{16} = \tfrac{2}{5}</math>.

Для контекста «c» имеем:

• <math>p(a / c) = p(a, c) / p(c) = \tfrac{1}{8} \div \tfrac{6}{16} = \tfrac{1}{3}</math>,
• <math>p(b / c) = p(b, c) / p(c) = \tfrac{1}{8} \div \tfrac{6}{16} = \tfrac{1}{3}</math>,
• <math>p(c / c) = p(c, c) / p(c) = \tfrac{1}{8} \div \tfrac{6}{16} = \tfrac{1}{3}</math>.

Примечание: здесь p(x, y) не равно p(y, x).

Строим кодовые деревья для каждого контекста. Выполняем кодирование и имеем закодированное сообщение: (00, 10, 01, 1, 10, 01, 1, 10, 01).

• 00 — из кода буквы «a» для стартовой схемы,
• 10 — из кода буквы «b» для контекста «a»,
• 01 — из кода буквы «c» для контекста «b»,
• 1 — из кода буквы «a» для контекста «c».

Переполнение

В процессе работы алгоритма сжатия вес узлов в дереве кодирования Хаффмана неуклонно растет. Первая проблема возникает тогда, когда вес корня дерева начинает превосходить вместимость ячейки, в которой он хранится. Как правило, это 16-битовое значение и, следовательно, не может быть больше, чем 65535. Вторая проблема, заслуживающая ещё большего внимания, может возникнуть значительно раньше, когда размер самого длинного кода Хаффмана превосходит вместимость ячейки, которая используется для того, чтобы передать его в выходной поток. Декодеру все равно, какой длины код он декодирует, поскольку он движется сверху вниз по дереву кодирования, выбирая из входного потока по одному биту. Кодер же должен начинать от листа дерева и двигаться вверх к корню, собирая биты, которые нужно передать. Обычно это происходит с переменной типа «целое», и, когда длина кода Хаффмана превосходит размер типа «целое» в битах, наступает переполнение.

Можно доказать, что максимальную длину код Хаффмана для сообщений с одним и тем же входным алфавитом будет иметь, если частоты символов образует последовательность Фибоначчи. Сообщение с частотами символов, равными числам Фибоначчи до Fib (18), — это отличный способ протестировать работу программы сжатия по Хаффману.

Масштабирование весов узлов дерева Хаффмана

Принимая во внимание сказанное выше, алгоритм обновления дерева Хаффмана должен быть изменен следующим образом: при увеличении веса нужно проверять его на достижение допустимого максимума. Если мы достигли максимума, то необходимо «масштабировать» вес, обычно разделив вес листьев на целое число, например, 2, а потом пересчитав вес всех остальных узлов.

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

Правильно организованное дерево Хаффмана после масштабирования может иметь форму, значительно отличающуюся от исходной. Это происходит потому, что масштабирование приводит к потере точности нашей статистики. Но со сбором новой статистики последствия этих «ошибок» практически сходят на нет. Масштабирование веса — довольно дорогостоящая операция, так как она приводит к необходимости заново строить все дерево кодирования. Но, так как необходимость в ней возникает относительно редко, то с этим можно смириться.

Выигрыш от масштабирования

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

Применение

Кодирование Хаффмана широко применяется при сжатии данных, в том числе при сжатии фото- и видеоизображений (JPEG, MPEG), в популярных архиваторах (PKZIP, LZH и др.), в протоколах передачи данных HTTP (Deflate), MNP5 и MNP7 и других.

Модификации

В 2013 году была предложена модификация алгоритма Хаффмана, позволяющая кодировать символы дробным количеством бит - ANS. На базе данной модификации реализованы алгоритмы сжатия Zstandard (Zstd, Facebook, 2015-2016) и LZFSE (Apple, OS X 10.11, iOS 9, 2016).

Литература

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — 1296 с. — ISBN 0-07-013151-1.
• Д. Сэломон. Сжатие данных, изображения и звука. — М.: Техносфера, 2004. — 368 с. — 3000 экз. — ISBN 5-94836-027-X.

Ссылки

• [www.webcenter.ru/~xander/HuffmanCode/huffcode.html Код Хаффмана] ([web.archive.org/web/20070927224229/www.webcenter.ru/~xander/HuffmanCode/huffcode.html WebArchive])
• [rain.ifmo.ru/cat/view.php/vis/data-compression/huffman-tree-2001 Визуализатор построения дерева для m₂=2]
• [rain.ifmo.ru/cat/view.php/vis/data-compression/huffman-tree-2003 Визуализатор кодирования букв русского алфавита]
• [algolist.manual.ru/compress/standard/huffman.php Сжатие по алгоритму Хаффмана] на algolist.manual.ru
• [habrahabr.ru/post/144200/ Хабрахабр: Алгоритм Хаффмана на пальцах]
• [habrahabr.ru/post/132289/ Хабрахабр: Алгоритмы используемые при сжатии данных]
• [habrahabr.ru/post/142242/ Хабрахабр: Сжатие информации без потерь. Часть первая]

Отрывок, характеризующий Код Хаффмана

– Что князь? – спросила она.
– Их сиятельство с ними в том же доме стоят.
«Стало быть, он жив», – подумала княжна и тихо спросила: что он?
– Люди сказывали, все в том же положении.
Что значило «все в том же положении», княжна не стала спрашивать и мельком только, незаметно взглянув на семилетнего Николушку, сидевшего перед нею и радовавшегося на город, опустила голову и не поднимала ее до тех пор, пока тяжелая карета, гремя, трясясь и колыхаясь, не остановилась где то. Загремели откидываемые подножки.
Отворились дверцы. Слева была вода – река большая, справа было крыльцо; на крыльце были люди, прислуга и какая то румяная, с большой черной косой, девушка, которая неприятно притворно улыбалась, как показалось княжне Марье (это была Соня). Княжна взбежала по лестнице, притворно улыбавшаяся девушка сказала: – Сюда, сюда! – и княжна очутилась в передней перед старой женщиной с восточным типом лица, которая с растроганным выражением быстро шла ей навстречу. Это была графиня. Она обняла княжну Марью и стала целовать ее.
– Mon enfant! – проговорила она, – je vous aime et vous connais depuis longtemps. [Дитя мое! я вас люблю и знаю давно.]
Несмотря на все свое волнение, княжна Марья поняла, что это была графиня и что надо было ей сказать что нибудь. Она, сама не зная как, проговорила какие то учтивые французские слова, в том же тоне, в котором были те, которые ей говорили, и спросила: что он?
– Доктор говорит, что нет опасности, – сказала графиня, но в то время, как она говорила это, она со вздохом подняла глаза кверху, и в этом жесте было выражение, противоречащее ее словам.
– Где он? Можно его видеть, можно? – спросила княжна.
– Сейчас, княжна, сейчас, мой дружок. Это его сын? – сказала она, обращаясь к Николушке, который входил с Десалем. – Мы все поместимся, дом большой. О, какой прелестный мальчик!
Графиня ввела княжну в гостиную. Соня разговаривала с m lle Bourienne. Графиня ласкала мальчика. Старый граф вошел в комнату, приветствуя княжну. Старый граф чрезвычайно переменился с тех пор, как его последний раз видела княжна. Тогда он был бойкий, веселый, самоуверенный старичок, теперь он казался жалким, затерянным человеком. Он, говоря с княжной, беспрестанно оглядывался, как бы спрашивая у всех, то ли он делает, что надобно. После разорения Москвы и его имения, выбитый из привычной колеи, он, видимо, потерял сознание своего значения и чувствовал, что ему уже нет места в жизни.
Несмотря на то волнение, в котором она находилась, несмотря на одно желание поскорее увидать брата и на досаду за то, что в эту минуту, когда ей одного хочется – увидать его, – ее занимают и притворно хвалят ее племянника, княжна замечала все, что делалось вокруг нее, и чувствовала необходимость на время подчиниться этому новому порядку, в который она вступала. Она знала, что все это необходимо, и ей было это трудно, но она не досадовала на них.
– Это моя племянница, – сказал граф, представляя Соню, – вы не знаете ее, княжна?
Княжна повернулась к ней и, стараясь затушить поднявшееся в ее душе враждебное чувство к этой девушке, поцеловала ее. Но ей становилось тяжело оттого, что настроение всех окружающих было так далеко от того, что было в ее душе.
– Где он? – спросила она еще раз, обращаясь ко всем.
– Он внизу, Наташа с ним, – отвечала Соня, краснея. – Пошли узнать. Вы, я думаю, устали, княжна?
У княжны выступили на глаза слезы досады. Она отвернулась и хотела опять спросить у графини, где пройти к нему, как в дверях послышались легкие, стремительные, как будто веселые шаги. Княжна оглянулась и увидела почти вбегающую Наташу, ту Наташу, которая в то давнишнее свидание в Москве так не понравилась ей.
Но не успела княжна взглянуть на лицо этой Наташи, как она поняла, что это был ее искренний товарищ по горю, и потому ее друг. Она бросилась ей навстречу и, обняв ее, заплакала на ее плече.
Как только Наташа, сидевшая у изголовья князя Андрея, узнала о приезде княжны Марьи, она тихо вышла из его комнаты теми быстрыми, как показалось княжне Марье, как будто веселыми шагами и побежала к ней.
На взволнованном лице ее, когда она вбежала в комнату, было только одно выражение – выражение любви, беспредельной любви к нему, к ней, ко всему тому, что было близко любимому человеку, выраженье жалости, страданья за других и страстного желанья отдать себя всю для того, чтобы помочь им. Видно было, что в эту минуту ни одной мысли о себе, о своих отношениях к нему не было в душе Наташи.
Чуткая княжна Марья с первого взгляда на лицо Наташи поняла все это и с горестным наслаждением плакала на ее плече.
– Пойдемте, пойдемте к нему, Мари, – проговорила Наташа, отводя ее в другую комнату.
Княжна Марья подняла лицо, отерла глаза и обратилась к Наташе. Она чувствовала, что от нее она все поймет и узнает.
– Что… – начала она вопрос, но вдруг остановилась. Она почувствовала, что словами нельзя ни спросить, ни ответить. Лицо и глаза Наташи должны были сказать все яснее и глубже.
Наташа смотрела на нее, но, казалось, была в страхе и сомнении – сказать или не сказать все то, что она знала; она как будто почувствовала, что перед этими лучистыми глазами, проникавшими в самую глубь ее сердца, нельзя не сказать всю, всю истину, какою она ее видела. Губа Наташи вдруг дрогнула, уродливые морщины образовались вокруг ее рта, и она, зарыдав, закрыла лицо руками.
Княжна Марья поняла все.
Но она все таки надеялась и спросила словами, в которые она не верила:
– Но как его рана? Вообще в каком он положении?
– Вы, вы… увидите, – только могла сказать Наташа.
Они посидели несколько времени внизу подле его комнаты, с тем чтобы перестать плакать и войти к нему с спокойными лицами.
– Как шла вся болезнь? Давно ли ему стало хуже? Когда это случилось? – спрашивала княжна Марья.
Наташа рассказывала, что первое время была опасность от горячечного состояния и от страданий, но в Троице это прошло, и доктор боялся одного – антонова огня. Но и эта опасность миновалась. Когда приехали в Ярославль, рана стала гноиться (Наташа знала все, что касалось нагноения и т. п.), и доктор говорил, что нагноение может пойти правильно. Сделалась лихорадка. Доктор говорил, что лихорадка эта не так опасна.
– Но два дня тому назад, – начала Наташа, – вдруг это сделалось… – Она удержала рыданья. – Я не знаю отчего, но вы увидите, какой он стал.
– Ослабел? похудел?.. – спрашивала княжна.
– Нет, не то, но хуже. Вы увидите. Ах, Мари, Мари, он слишком хорош, он не может, не может жить… потому что…


Когда Наташа привычным движением отворила его дверь, пропуская вперед себя княжну, княжна Марья чувствовала уже в горле своем готовые рыданья. Сколько она ни готовилась, ни старалась успокоиться, она знала, что не в силах будет без слез увидать его.
Княжна Марья понимала то, что разумела Наташа словами: сним случилось это два дня тому назад. Она понимала, что это означало то, что он вдруг смягчился, и что смягчение, умиление эти были признаками смерти. Она, подходя к двери, уже видела в воображении своем то лицо Андрюши, которое она знала с детства, нежное, кроткое, умиленное, которое так редко бывало у него и потому так сильно всегда на нее действовало. Она знала, что он скажет ей тихие, нежные слова, как те, которые сказал ей отец перед смертью, и что она не вынесет этого и разрыдается над ним. Но, рано ли, поздно ли, это должно было быть, и она вошла в комнату. Рыдания все ближе и ближе подступали ей к горлу, в то время как она своими близорукими глазами яснее и яснее различала его форму и отыскивала его черты, и вот она увидала его лицо и встретилась с ним взглядом.
Он лежал на диване, обложенный подушками, в меховом беличьем халате. Он был худ и бледен. Одна худая, прозрачно белая рука его держала платок, другою он, тихими движениями пальцев, трогал тонкие отросшие усы. Глаза его смотрели на входивших.
Увидав его лицо и встретившись с ним взглядом, княжна Марья вдруг умерила быстроту своего шага и почувствовала, что слезы вдруг пересохли и рыдания остановились. Уловив выражение его лица и взгляда, она вдруг оробела и почувствовала себя виноватой.
«Да в чем же я виновата?» – спросила она себя. «В том, что живешь и думаешь о живом, а я!..» – отвечал его холодный, строгий взгляд.
В глубоком, не из себя, но в себя смотревшем взгляде была почти враждебность, когда он медленно оглянул сестру и Наташу.
Он поцеловался с сестрой рука в руку, по их привычке.
– Здравствуй, Мари, как это ты добралась? – сказал он голосом таким же ровным и чуждым, каким был его взгляд. Ежели бы он завизжал отчаянным криком, то этот крик менее бы ужаснул княжну Марью, чем звук этого голоса.
– И Николушку привезла? – сказал он также ровно и медленно и с очевидным усилием воспоминанья.
– Как твое здоровье теперь? – говорила княжна Марья, сама удивляясь тому, что она говорила.
– Это, мой друг, у доктора спрашивать надо, – сказал он, и, видимо сделав еще усилие, чтобы быть ласковым, он сказал одним ртом (видно было, что он вовсе не думал того, что говорил): – Merci, chere amie, d'etre venue. [Спасибо, милый друг, что приехала.]
Княжна Марья пожала его руку. Он чуть заметно поморщился от пожатия ее руки. Он молчал, и она не знала, что говорить. Она поняла то, что случилось с ним за два дня. В словах, в тоне его, в особенности во взгляде этом – холодном, почти враждебном взгляде – чувствовалась страшная для живого человека отчужденность от всего мирского. Он, видимо, с трудом понимал теперь все живое; но вместе с тем чувствовалось, что он не понимал живого не потому, чтобы он был лишен силы понимания, но потому, что он понимал что то другое, такое, чего не понимали и не могли понять живые и что поглощало его всего.
– Да, вот как странно судьба свела нас! – сказал он, прерывая молчание и указывая на Наташу. – Она все ходит за мной.
Княжна Марья слушала и не понимала того, что он говорил. Он, чуткий, нежный князь Андрей, как мог он говорить это при той, которую он любил и которая его любила! Ежели бы он думал жить, то не таким холодно оскорбительным тоном он сказал бы это. Ежели бы он не знал, что умрет, то как же ему не жалко было ее, как он мог при ней говорить это! Одно объяснение только могло быть этому, это то, что ему было все равно, и все равно оттого, что что то другое, важнейшее, было открыто ему.
Разговор был холодный, несвязный и прерывался беспрестанно.
– Мари проехала через Рязань, – сказала Наташа. Князь Андрей не заметил, что она называла его сестру Мари. А Наташа, при нем назвав ее так, в первый раз сама это заметила.
– Ну что же? – сказал он.
– Ей рассказывали, что Москва вся сгорела, совершенно, что будто бы…
Наташа остановилась: нельзя было говорить. Он, очевидно, делал усилия, чтобы слушать, и все таки не мог.
– Да, сгорела, говорят, – сказал он. – Это очень жалко, – и он стал смотреть вперед, пальцами рассеянно расправляя усы.
– А ты встретилась с графом Николаем, Мари? – сказал вдруг князь Андрей, видимо желая сделать им приятное. – Он писал сюда, что ты ему очень полюбилась, – продолжал он просто, спокойно, видимо не в силах понимать всего того сложного значения, которое имели его слова для живых людей. – Ежели бы ты его полюбила тоже, то было бы очень хорошо… чтобы вы женились, – прибавил он несколько скорее, как бы обрадованный словами, которые он долго искал и нашел наконец. Княжна Марья слышала его слова, но они не имели для нее никакого другого значения, кроме того, что они доказывали то, как страшно далек он был теперь от всего живого.
– Что обо мне говорить! – сказала она спокойно и взглянула на Наташу. Наташа, чувствуя на себе ее взгляд, не смотрела на нее. Опять все молчали.
– Andre, ты хоч… – вдруг сказала княжна Марья содрогнувшимся голосом, – ты хочешь видеть Николушку? Он все время вспоминал о тебе.
Князь Андрей чуть заметно улыбнулся в первый раз, но княжна Марья, так знавшая его лицо, с ужасом поняла, что это была улыбка не радости, не нежности к сыну, но тихой, кроткой насмешки над тем, что княжна Марья употребляла, по ее мнению, последнее средство для приведения его в чувства.
– Да, я очень рад Николушке. Он здоров?

Когда привели к князю Андрею Николушку, испуганно смотревшего на отца, но не плакавшего, потому что никто не плакал, князь Андрей поцеловал его и, очевидно, не знал, что говорить с ним.
Когда Николушку уводили, княжна Марья подошла еще раз к брату, поцеловала его и, не в силах удерживаться более, заплакала.
Он пристально посмотрел на нее.
– Ты об Николушке? – сказал он.
Княжна Марья, плача, утвердительно нагнула голову.
– Мари, ты знаешь Еван… – но он вдруг замолчал.
– Что ты говоришь?
– Ничего. Не надо плакать здесь, – сказал он, тем же холодным взглядом глядя на нее.

Когда княжна Марья заплакала, он понял, что она плакала о том, что Николушка останется без отца. С большим усилием над собой он постарался вернуться назад в жизнь и перенесся на их точку зрения.
«Да, им это должно казаться жалко! – подумал он. – А как это просто!»
«Птицы небесные ни сеют, ни жнут, но отец ваш питает их», – сказал он сам себе и хотел то же сказать княжне. «Но нет, они поймут это по своему, они не поймут! Этого они не могут понимать, что все эти чувства, которыми они дорожат, все наши, все эти мысли, которые кажутся нам так важны, что они – не нужны. Мы не можем понимать друг друга». – И он замолчал.

Маленькому сыну князя Андрея было семь лет. Он едва умел читать, он ничего не знал. Он многое пережил после этого дня, приобретая знания, наблюдательность, опытность; но ежели бы он владел тогда всеми этими после приобретенными способностями, он не мог бы лучше, глубже понять все значение той сцены, которую он видел между отцом, княжной Марьей и Наташей, чем он ее понял теперь. Он все понял и, не плача, вышел из комнаты, молча подошел к Наташе, вышедшей за ним, застенчиво взглянул на нее задумчивыми прекрасными глазами; приподнятая румяная верхняя губа его дрогнула, он прислонился к ней головой и заплакал.
С этого дня он избегал Десаля, избегал ласкавшую его графиню и либо сидел один, либо робко подходил к княжне Марье и к Наташе, которую он, казалось, полюбил еще больше своей тетки, и тихо и застенчиво ласкался к ним.
Княжна Марья, выйдя от князя Андрея, поняла вполне все то, что сказало ей лицо Наташи. Она не говорила больше с Наташей о надежде на спасение его жизни. Она чередовалась с нею у его дивана и не плакала больше, но беспрестанно молилась, обращаясь душою к тому вечному, непостижимому, которого присутствие так ощутительно было теперь над умиравшим человеком.


Князь Андрей не только знал, что он умрет, но он чувствовал, что он умирает, что он уже умер наполовину. Он испытывал сознание отчужденности от всего земного и радостной и странной легкости бытия. Он, не торопясь и не тревожась, ожидал того, что предстояло ему. То грозное, вечное, неведомое и далекое, присутствие которого он не переставал ощущать в продолжение всей своей жизни, теперь для него было близкое и – по той странной легкости бытия, которую он испытывал, – почти понятное и ощущаемое.