Архиваторы: Избыточности не существует.

Эээ... Ну вот этого не знаю, ибо трудов Шеннона не читал. Либо всё слишком очевидно, чтобы на этом заострять внимание, либо он таки заостряет на этом внимание, я не знаю.

 

http://www.sendspace.com/file/e78jx6 (~ 7 Mb)
Не могу сказать, что зачитываюсь ими на ночь, но так, навскидку, ничего не вспоминается. Или пропустил, в свое время?

 

Ой нет, увольте, читать книгу в 7 метров, чтобы там найти чего-то про информацию и способы её представления, ради того чтобы кого-то просветить номером страницы и параграфа - увольте, но не с руки как-то. =)

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

 

Упаси, Бог! И в мыслях не держал. Просто поделиться хорошим сборником

Кто же станет возражать против очевидного?

 

gazlan

Повторю, что в шенноновской теории и в ее современной интерпретации речь идет не об избыточности конкретного сообщения ("объекта"), а об избыточности источника сообщений (или языка), генерирующего сообщения из некоторого набора символов (алфавита). Соотв-но мат.определение избыточности это - единица минус отношение (_реальной_) энтропии источника к максимальной (_воображаемой_) энтропии, которую он мог бы обеспечить, используя тот же набор символов (т.е. при их случайном равновероятном чередовании).
Это определение есть и у самого Шеннона в "Мат.теории связи", и во всех учебниках по теории информации, и в интернете кучу ссылок можно найти, в т.ч. и в википедии (по кр.мере в англ.варианте - redundancy)

 

leo

Мутноватое какое-то определение (хоть и классическоие и общепринятое). Лично я избыточность понимаю так - в посте #102 ссылка на книгу в формате djvu занимающую 7Мб. Если бы эта книга была бы в текстовом формате с поддержкой формул и векторных рисунков то занимала бы меньше места. Если этот текстово-векторный формат ещё и заархивировать то он займёт ещё меньше места. Информация (во всяком случае полезная) при этом одна и таже, а избыточность соотвенно разная, но это ещё вовсе не означает что самый компакный вариант (заархивированный текст) совсем не имеет избыточности. Поэтому как в этом (не туманно абстрактном, а вполне конкретном, практически значимом случае) определить количество "чистой" информации и её избыточность в перечисленных представлениях совершенно непонятно и приведённое выше "классическое" определение никакой ясности в этот вопрос не вносит, скорее только запутывает, наводя на мысль что эти разные форматы соответствуют разным "алфавитам". Но информация то одна и таже, и даже "низкоуровневый" алфавит во всех форматах одинаковый - двоичный

ЗЫ: кстати формат djvu помимо чисто "алфавитной" избыточности несёт в себе и лишнюю "шумовую" информацию о неидеальностях пиксельного представления границ шрифтов, типографских дефектах, погрешностях сканирования и т.п. которая читателя книги в общем то совсем не интересует )

 

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

Y_Mur

IMHO, никак. У Колмогорова есть интересные рассуждения на эту тему (на примере "Войны и мира"). Шеннон вводит "абсолютный (термодинамический) нуль отсчета" как энтропию белого шума и уже от него отсчитывается "количество информации".

P.S.
Еще на тему разделяемой модели
Вчера, в блоге Садальского:

http://stanis-sadal.livejournal.com/?skip=10

 

Y_Mur
Не надо подливать масла в огонь
Во-первых, "на пальцах" здесь уже уже с десяток раз пытались объяснить понятие избыточности, но ТС это не устравивает и ему подавай "классику".
Во-вторых, классическое определение как раз ничего не затуманивает, а объясняет другими более абстрактными словами\понятиями. Да, русский текст можно записать в разных по объему алфавитах - ограниченном алфавите кода Бодо, в расширенном алфавите ANSI или в сверхрасширенном UNICODE. Но энтропия (или "чистая информация") этого текста будет одинаковой во всех этих алфавитах (при этом не важно, как конкретно ее расчитывать, т.е. насколько глубоко учитывать межсимвольные связи, главное чтобы было единообразно для любых алфавитов). А вот основная составляющая избыточности - максимальная энтропия источника - разумеется будет разной для разных кодировок, т.к. неиспользуемые (или крайне редко используемые) символы алфавита будут давать нулевой вклад в реальную энтропию источника, и "весомый" вклад в его максимальную энтропию (в предположении, что все символы равновероятны). Поэтому, если источник выдает сырой (несжатый) текст, то его максимальная удельная энтропия в расчете на 1 символ всегда равна логарифму из объема используемого алфавита. В общем случае максимальная удельная энтропия (в т.ч. и для сжатых сообщений) = средней длине сообщения в битах, деленной на число символов в сообщении.
Вывод: не важно, можем мы или не можем расчитать реальную энтропию ("чистую информацию") источника или конкретного сообщения, главное в классической формуле избыточности то, что она показывает основные тенденции:
1) классический вывод: при заданном алфавите источника (Hmax = const) его избыточность тем больше, чем больше статистических связей\ограничений в выходных сообщениях (т.е. чем меньше реальное значение H)
2) очевидный вывод, на котором в класс.теории не заостряют внимание: если взять сообщения с фикс.реальной энтропией H, то избыточность источника будет тем выше, чем больше (в среднем) бит он использует для кодирования\представления одного символа. Например (в десятый раз повторяю , если взять простой русский текст без учета регистра, то Hmax для юникода = 16 бит/симв, для анси - 8, для Бодо - ~5, для Хаффмана - 4.4 бит/симв. Соотв-но не важно как мы считаем реальное значение H (посимвольно или более сложно) - очевидно, что чем больше Hmax, тем выше избыточность источника

 

gazlan

А мне "кажется", т.к. за понятием "источник сообщения" скрывается именно не конкретный "объект", а "представление" этого объекта. Например, для системы связи (или для архиватора) источником может быть телеграфный аппарат, выдающий символы в кодах Бодо, а может быть виндовый блокнот, сохраняющий файлы либо в анси, либо в юникоде, или Adobe Acrobat и т.д. и т.п. Текст м.б. одним и тем же, а его "представление" и соотв-но избыточность - разная.

А твое заявление в #31

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

 

Угу. Потому вам и "кажется". Реально, информация почти целиком определяется моделью. Само сообщение (его биты и их логарифмы) это маленькая часть пазла. Помните историю, как четверо слепых ощупывали слона? Невозможно восприятие вне парадигмы. Если вы прошли по линку в моем предыдущем (#107) ответе, то могли видеть, что сообщение "поразил дракона" совершенно по разному интерпретировано в двух разных, хотя и очень близких моделях. И ориентироваться на "логарифм объема используемого алфавита" попросту неверно.

Нет, мы уже договорились, что избыточность спрятана именно в модели.

 

gazlan
Мда, ты похоже безнадежно болен...
Источник существует сам по себе (например, txt-файл на диске), а система передачи или архиватор сами по себе. Пока архиватор не проанализирует файл, для него существует только Hmax = размеру файла в битах. Может оказаться, что в этом txt содержится хорошо зашифрованный текст или вообще случайный набор символов и соотв-но его избыточность будет близка к 0 и следовательно его не удасться существенно сжать и проще оставить как есть.
А может, наоборот он содержит кучу повторяющихся символов и его можно значительно сжать элементарным RLE, или еще лучше LZW (который, к слову сказать, юникодный текст сожмет больше ансишного -> зависимость не только от "содержания", но и от "кодировки"). Т.е. конкретный текст (или источник, который его выдал) может содержать некоторую "теоретическую избыточность" по Шеннону, но упрощенный алгоритм RLE может устранить только часть этой избыточности, заложенную в его модели, алгоритм LZW - свою часть, бОльшую чем RLE, а некий идеальный\абстрактный алгоритм - практически всю "теоретическую" избыточность.
Другими словами есть теоретическая\потенциальная избыточность, присущая данному источнику (расчитывается по Шеннону), а есть избыточность, реально устраняемая конкретным архиватором, заложенная в его модели и расчитывается она в шенновских терминах вообще элементарно - как единица минус отношение длины сжатого сообщения к длине исходного в битах.
Причем если используются динамические алгоритмы сжатия, то архиватор устраняя часть избыточности сообщения, вынужден добавить в него свою "избыточность" = "информацию" для декодера. Т.е. с точки зрения декодера это служебная информация (заранее неизвестная дельта к его модели), но с точки зрения передачи сообщения по каналу или его хранения на диске - это избыточность, т.к. теоретически возможны другие, статические методы сжатия, которые не будут добавлять к сообщению этих "лишних" битов

 

Диагноз по фотографии?

Со всем, изложенным ниже я согласен - и не могу вспомнить, чтобы когда-либо возражал против этого. В использованных мною ранее определениях это выглядит как "модель + синхросигнал". Поясните, пожалуйста: в чем вы видите несогласованность в наших взглядах?

 

gazlan

Развивая эту мысль можно сказать - один человек прочитав книгу из #102 поймёт её всю, другой только 25%, третий 5%, четвёртый не поймёт в ней ничего - вывод - книгу вообще нельзя считать самостоятельным сообщением и пытаться как-то измерить количество информации в ней, соответсвенно рассуждения об избыточности в ней из #107, #108 совершенно беспочвенны...
Не могу согласиться с такой постановкой вопроса - имхо всё таки содержимое книги должно иметь более менее объективную оценку количества заключённой в неё информации.

 

Представьте, что эта книга даже не на незнакомом вам языке, а просто в нечитаемой кодировке. Ее "объективная" информативность не изменилась ни на бит, но в вашей модели это просто шум. В шифровании это еще прозрачнее. Есть ключ и алгоритм (модель) - сообщение может быть прочитано. Нет - это практически чистый шум
(почти случайный текст).

 

Трансформаторы

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

Отображения равномерных кодов в равномерные тривиально (Ex: KOI8R-Win1251), а неравномерных в неравномерные можно рассматривать просто как двойное (каскадное) преобразование.
Отанавливаться на очевидных (кольцо) групповых свойствах подстановок я не буду.

Желательна некоторая компактная (алгебраическая) форма записи такого отображения (из одного алфавита в другой).

Пусть имеются (равномощные) алфавиты A1 и A2 и некоторое отображение (которое будем называть Трансформацией T), взаимооднозначно связывающее элементы (Литеры) из A1 и A2, так что любому a1(i) сопоставлен a2(j) и наоборот.

Оператор, переводящий текст x записанный в алфавите A1 в текст y, записанный в алфавите A2 будем называть Трансформатором T(1,2).

y = Tx (*)

В силу естественной упорядоченности алфавитов, каждой литере можно сопоставить ее номер (последовательный индекс).

Предлагаю записывать Трансформатор T(1,2) как диагональную матрицу n*n (n - мощность алфавита), где на (i,i)-ом месте находится j - индекс подставляемой литеры второго алфавита.

В силу постулированной биективности трансформации, матрица T невырождена и имеет обратную.

Уравнение (*) будем называть Законом Ома для участка информационной цепи, а T - информационным импедансом.

Последовательному (каскадному) применению трансформаций соответствует перемножение импедансов (слева). Так, например, импеданс LZH может быть получен произведением импедансов LZ и H.

 

gazlan
Ацки жжош.

А гуру не отзываются потому, что такой бред никто комментировать не захочет.
Ведь видно сразу, что автор ни теории не знает и ни единого сколь либо серъезного алгоритма сжатия не написал.
Но мнение, как полагается, имеет.

 

Translit