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

Забыл сказать: да, это НЕ вызывает возражений. Но это и есть то, что я называю разделяемой моделью и синхросигналом.

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

 

gazlan

Нет. В этом постулате ошибка.

 

Признаться, не вижу в чем, можно подробнее?

Well. Изменим формулировку, уберем "испорченное".
Пусть теперь, декодер - обычный транслятор (текст-2-текст), обрабатывающий входной поток в соответствии с некоторой (бесконфликтной) грамматикой. Входной поток считаем синтаксически правильным. Все ограничения (связи) сосредоточены в разделяемой модели (сжатый текст псевдослучаен).
Вопросы:
1. Где происходит восстановление избыточности?
2. Является ли эта (семантическая) избыточность избыточностью по Шеннону?

 

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

Вам уже ответили несколько раз на эти вопросы. Восстановление происходит в декодере, да, является.

 

"Порчу" я понимаю как отличие от оригинального сообщения, а не как нарушение структуры сжатого.

Пример же с испорченным битом некорректен. Например, если изменить (на один бит) поле размера записи в несжатом DBF-файле, то программа чтения (DBF Reader) точно также не сможет обработать (некорректно выдаст) весь оставшийся поток. Избыточность здесь ни при чем. И даже больше - если сжатый поток по размеру меньше оригинального, то восстановление при ошибке (ECC) обойдется дешевле - просто в силу меньшего размера. Опора на избыточность исходного текста (скажем, пропуск гласных букв при письме) требует
совсем иной модели восстановления.

 

И совершенно неправильно понимаете. Порча - это изменение сообщения, приводящее к неправильному декодированию этого сообщения. Поэтому оно и называется "порча", а не как-то иначе.

Для DBF-а существует repair-утилиты, если вы не знали, как раз пытающиеся на основании избыточности файла восстановить из него хоть что-то - фиксированный размер записей тому способствует. А вот если бы бит был замещен в сжатом в RAR DBF файле, то никакая repair-утилита уже бы не помогла. Что опять таки доказывает вашу неправоту по отношению к избыточности.

 

Кажется, мы о разном.

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

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

Я знаю и про repair утилиты для DBF и про ключ 'r' (Repair archive) в RAR, но не понимаю как это соотносится с приведенным вами примером, где никакая коррекция ошибок НЕ используется

 

А кто сказал что это так? =) Вы как раз аппелируете к смыслу "порчи", т.к. действительно, чтобы восстановить испорченное сообщение в первозданном (неиспорченном) виде, требуется чтобы кодированное сообщение было априори более избыточно чем восстановленное. Как пример - CD-диски, на которых хранится примерно на 30% больше бит, чем заявлено на обложке (600-700Мб), за счёт кодов коррекции Рида-Соломона, позволяет читать даже зацарапанный диск.
Это всё известно, но тут как раз семантика слова "порча" заключается именно в смысле "порча", как я его описал.

То о чём вы говорите, порчей не является и не требует "большую избыточность первого по отношению ко второму" никоим образом.

 

ОК. Забудем про "порчу".
Вы согласны, что если второе сообщение выводится из первого, то это означает, что первое содержит всю информацию из второго + правила вывода?
Если же считать правила вывода "упрятанными" в декодер, то какое основание приписывать эту информацию выводимому сообщению?

 

Правила вывода содержаться в декодере.

Никаких. В декодированном сообщении тем более нет никаких правил вывода.

Но о чём это вы тут? Я не понял к чему эти выводы.

 

Да все о том же: пытаюсь понять "физический" смысл понятия "избыточность". Пока она мне видится фиктивной величиной, зависящей от "системы отсчета" (метода кодирования).

 

А. Ну нет. Пока оно занимает место на накопителях информации и напрягает каналы передачи данных - фиктивным оно не будет. =)

 

gazlan

Никто ее сообщению и не приписывает. В #78 ты наконец-то сделал правильный вывод, о том, что избыточность это характеристика не самого сообщения, а его исходной кодировки\модели\_системы_координат_. Если в твоей модели заложены некие знания, позволяющие представить сообщение (точнее некий класс\вид сообщений) в более "компактном виде", то можно говорить о том, что исходная кодировка является "избыточной" для данного вида сообщений. В итоге эту "избыточность" можно не хранить для каждого сообщения и не передавать по каналу связи, а заложить ее в алгоритм кодирования\декодирования. Т.е. одно и то же сообщение может быть представлено в разных кодировках (моделях) с разной степенью избыточности.
Например, возвращаясь к нашим баранам , кодировка русского текста в формате юникод явлется очень избыточной, т.к. "модель" юникода предполагает любое\случайное чередование символов из множества различных кодовых страниц. Если мы знаем\определяем, что весь текст принадлежит одной странице, то можем использовать менее избыточную кодировку анси. Но для связного текста она ес-но тоже является избыточной, т.к. преполагает случайное чередование симолов, поэтому можно заюзать другие модели, учитывающие реальную (или среднюю) статистику\корреляцию символов в сообщении (или классе сообщений). В итоге, чем более "хитрую" модель мы используем и чем более "компактным" (в общем случае в среднем для всего класса сообщений) в итоге получается закодированное сообщение по сравнению с исходным, тем больше "избыточности" было в исходном представлении сообщения по сравнению с нашей "хитрой" кодировкой/моделью.

Использование избыточности для коррекция ошибок никак не влияет на определение самой избыточности как меры соотношения "компактностей" представления сообщений в разных кодировках\моделях. Поэтому приплетать сюда возможности коррекции совершенно незачем

 

Попытаюсь пояснить, почему я говорю о "фиктивности".

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

А теперь вспомним, что и Huf и LZW являются просто способами переименования. Для Huf равномерные коды кодируются неравномерными, для LZW - в точности наоборот.

Иными словами, три разных способа разбиения/именования на битовые блоки дают три разных оценки.

Следовательно, эти оценки относятся к способу разбиения (структуре и содержанию словаря), но не к самому объекту.

 

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

 

в классической теории избыточность определяется в зависимости от "модели"

 

gazlan

Угу, иди для начала книжки почитай Я уже приводил классическое определение избыточности - в ней фигурирует максимальная энтропия источника сообщений при заданном алфавите или длине исх.сообщения, т.е. если у тебя есть исходное сообщение длиной 100 бит, то соотв-но максимальная энтропия и есть 100 бит в преположении их случайного чередования. Если есть сообщения произвольной длины, используюшие "алфавит" анси, то соотв-но макс.энтропия будет 8 бит/символ, а в "алфавите" юникод - 16 бит/символ. А энтропия русского текста как ни крути ~3-4 бит/символ - вот тебе и разная избыточность в разных кодировках

 

Статистической. Семантика остается за бортом.

 

Ну разумеется. Объект - сообщение. А предмет оценки избыточности - его представление. В чём ты тут увидел подвох?

 

Мне кажется, что это разделение: Объект (как инвариант) и его представление (как набор чисел в данной системе координат) нигде явно не проводится.