Написано в сотрудничестве с Р. Бухрадзе и К. Перминовым



## 1\. Введение



Offline oбмен сообщениями сейчас является одним из наиболее популярных способов общения ([1][1], [2][2], [3][3]) — судя по аудитории способов общения и динамике её роста.



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



Максимально достигаемый объём сжатия, гарантирующий однозначное восстановление данных, определяется работами К. Шеннона по теории информации, и в общем-то является непреодолимым так как изъятие не только избыточной, но и смысловой информации не позволит однозначно восстановить исходное сообщение. Стоит отметить, что отказ от точного восстановления в некоторых случаях и не является критически важным и используется для эффективного сжатия [графических][4], [видео][5] и [музыкальных][6] данных, где потеря несущественных элементов оправдана, однако о общем случае целостность данных, куда важнее их размера.



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


[Читать дальше →][7]

[1]: http://www.the-village.ru/village/business/figures/250115-messenger
[2]: https://spark.ru/startup/546dae36cfa4a/blog/17709/messendzheri-i-boti-vozmozhnosti-dlya-prodvizheniya
[3]: https://habrahabr.ru/post/293656/
[4]: https://ru.wikipedia.org/wiki/JPEG
[5]: https://ru.wikipedia.org/wiki/MPEG-4
[6]: https://ru.wikipedia.org/wiki/MP3
[7]: https://habrahabr.ru/post/318848/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut