Кодирование с изъятием информации. Часть 1-я, философская
Написано в сотрудничестве с Р. Бухрадзе и К. Перминовым
1. Введение
Offline oбмен сообщениями сейчас является одним из наиболее популярных способов общения (1, 2, 3) — судя по аудитории способов общения и динамике её роста.
При этом, ключевым требованием при обмене сообщениями всегда будет являться полное соответствие отправленного сообщения — полученному, то есть передача данных не должна необратимо искажать сами данные. Естественное желание — сэкономить привело к созданию алгоритмов сжатия данных, которые, убирают естественную избыточность данных минимизируя объём хранимых и передаваемых файлов.
Максимально достигаемый объём сжатия, гарантирующий однозначное восстановление данных, определяется работами К. Шеннона по теории информации, и в общем-то является непреодолимым так как изъятие не только избыточной, но и смысловой информации не позволит однозначно восстановить исходное сообщение. Стоит отметить, что отказ от точного восстановления в некоторых случаях и не является критически важным и используется для эффективного сжатия графических, видео и музыкальных данных, где потеря несущественных элементов оправдана, однако о общем случае целостность данных, куда важнее их размера.
Соответственно интересным является вопрос о том, можно-ли не нарушая положения теории информации передать сообщение объёмом меньше, чем минимальный объём, который может быть достигнут при самом лучшем сжатии данных.
2. Пример
Поэтому давайте разберём пример, который позволит изучить особенности передачи информации. И хотя в «английской» традиции участников информационного обмена принято именовать Алиса и Боб, мы же в преддверии нового года воспользуемся более знакомыми любителями месседжинга: Матроскиным и Шариком соответственно.
В качестве же сообщения m выберем:»Поздравляю тебя, Шарик, ты балбес!». Длина его в односимвольной кодировке- len (m) — 34 байта.
Можно заметить, что длина сообщения заметно больше количества информации в нём. Это можно проверить вычеркивая из сообщения сначала каждый десятый символ, потом, (опять же из оригинального сообщения) каждый девятый и так далее до каждого четвёртого, результатом чего будет — »Позравяю ебя Шаик,ты албс!»-26 байт. Соответственно степень «загадочности» будет постепенно повышаться, но, догадаться о чём речь, будет достаточно просто. Более того, «Яндекс» распознаёт данное обращение.
Ещё более высокой степени сокращения длины сообщения при сохранении смысла можно добиться отбрасывая гласные и часть пробелов:»Пздрвл тб,Шрк,т блбс!» — 21 байт, стоит отметить, что хотя поисковики и не справляются таким написанием, восстановить фразу труда не составляет.
Если же посмотреть на количество информации I (m) в этом сообщении определяемое более строго через понятие информационной энтропии, то видно, что объём информации передаваемый в этом сообщении, составляет примерно 34×4,42/8=18,795 байт. Здесь: 4.42 бит/символ среднее количество информации в одном байте русского языка (4, 5), а 8 — приведение от битов к байтам. Это показывает, что воспользовавшись самым лучшим способом сжатия данных необходимо будет затратить не менее 19 байт на передачу сообщения от Матроскина Шарику.
Более того, верно и обратное утверждение о том, что передать нужное нам сообщение без потерь меньше чем за 19 байт невозможно (К. Шеннон, Работы по теории информации и кибернетике., изд. Иностранной литературы, Москва, 1963 г.) Теорема 4. стр. 458.
3. Дальнейшие рассуждения
Однако продолжим… Пусть у Матроскина и у Шарика есть некоторое дополнительное количество информации k и пара функций, одна из которых m'=E (k, m), рассчитывающая пересечение дополнительной информации k и исходного сообщения m 
, а вторая D (k, m') =m — обратная к E. Причём количество информации определяемой по Шеннону, удовлетворяет следующему условию: 
. Соответственно, если нам удастся построить определённую выше пару функций E (k, m) и *D (k, m'), такие, что выполняются следующие два условия:
, 
то это будет означать, что для передачи информации между адресатами может потребоваться меньше информации чем содержится в исходном сообщении.
При этом стоит обратить внимание на то, что по определению указанных функций не происходит нарушения утверждений теории информации.
Похожие, алгоритмы предусматривающие замену передаваемой информации её хешем, активно используются в системах оптимизации сетевого трафика. При этом, однако, в отличие от описываемого алгоритма, для того, чтобы эффективно использовать данный вид оптимизации требуется хотя бы однократная передача данных.
Ввиду того, что сообщения на естественном языке содержат объём данных, больший чем объём информации, то если предварительно сжать исходное сообщение при помощи какого-либо из алгоритмов, обеспечивающих эффективное устранение избыточности, например, арифметического кодирования.
Обозначим применение операции сжатия m»= Ar (m) такой, что 
. Если теперь использовать определённую выше функцию E над предварительно сжатым сообщением, то можно заметить, что и объём передаваемых данных и количество информации передаваемых между адресатами могут оказаться меньше объёма данных и количества информации в исходном сообщении.
То есть, обобщая: в предположении, что существует обратимое преобразование D (k, E (k, m)) =m, такое, что 
применение операций устранения избыточности даёт возможность передать объём и количество информации в объёме не превосходящие соответствующие параметры (длина len (m) и количество информации I (m)) исходного сообщения.
В общем осталось только подобрать функции……
Комментарии (3)
31 декабря 2016 в 01:26
0↑
↓
Ещё более высокой степени сокращения длины сообщения при сохранении смысла можно добиться отбрасывая гласные и часть пробелов: «Пздрвл тб, Шрк, т блбс!»
Думаю, здесь имеет место не сжатие, а хэширование, т.к. однозначно восстановить фразу человеку, не смотревшему «Простоквашино», будет невозможно.
31 декабря 2016 в 01:43
0↑
↓
В общем-то да. Тут скорее расчёт на то, что и смотрели и мультфильм вполне новогодний и фраза простая.
А если серьёзно, то получается так, что если и в тексте и в ключе можно выделить общую информацию, которую можно отбросить, то восстановить данные, по информации меньшей чем минимум достигаемый сжатием, не имея ключа, довольно сложно.
31 декабря 2016 в 08:05
0↑
↓
В общем осталось только подобрать функции
Например, одинаковый словарь у отправителя и получателя. Передаем только индексы слов, получаем уменьшение размера сообщения.В русском языке несколько миллионов словоформ. То есть, достаточно около 3 байт на слово. Старший бит можно сделать признаком знаков препинания, для них достаточно одного байта.
000000 80 000001 81 000002 81 000003 80 000004 82 (20 байт)
Пздрвл тб,Шрк,т блбс! (21 байт)
Можно еще биты поэкономить.
