Избыточность ( теория информации)

В теории информации, избыточность измеряет дробную разницу между энтропией H (X) ансамбля X и его максимально возможное значение $log\; \; (|\; AX\; |)\; \{\backslash \; displaystyle\; \backslash \; log\; (|\; \{\backslash \; mathcal\; \{A\}\}\; \_\; \{X\}\; |)\}$. Неформально это количество потраченного впустую «пространства», используемого для передачи определенных данных. Сжатие данных - это способ уменьшить или устранить нежелательную избыточность, в то время как контрольные суммы - это способ добавления желаемой избыточности для целей обнаружения ошибок при обмене данными по шумному канал ограниченной емкости.

• 1 Количественное определение
• 2 Другие понятия
• 3 См. Также
• 4 Ссылки

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

$r\; =\; lim\; n\; \to \; \infty \; 1\; n\; H\; (M\; 1,\; M\; 2,\dots \; M\; n),\; \{\backslash \; displaystyle\; r\; =\; \backslash \; lim\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; H\; (M\_\; \{1\},\; M\_\; \{2\},\; \backslash \; dots\; M\_\; \{n\}),\}$

в пределе, когда n стремится к бесконечности, совместной энтропии первых n символов, деленной на n. В теории информации принято говорить о «скорости» или «энтропии » языка. Это уместно, например, когда источником информации является английская проза. Скорость источника без памяти равна просто $H\; (M)\; \{\backslash \; displaystyle\; H\; (M)\}$, поскольку по определению нет взаимозависимости последовательных сообщений источника без памяти.

абсолютная скорость языка или источника - это просто

$R\; =\; log\; \; |\; M\; |,\; \{\backslash \; displaystyle\; R\; =\; \backslash \; log\; |\; \backslash \; mathbb\; \{M\}\; |,\; \backslash ,\}$

логарифм мощности пространства сообщений или алфавита. (Эту формулу иногда называют функцией Хартли.) Это максимально возможная скорость передачи информации, которая может быть передана с этим алфавитом. (Логарифм должен быть взят с базой, соответствующей используемой единице измерения.) Абсолютная скорость равна фактической скорости, если источник не имеет памяти и имеет равномерное распределение.

Абсолютная избыточность затем можно определить как

$D\; =\; R\; -\; r,\; \{\backslash \; displaystyle\; D\; =\; Rr,\; \backslash ,\}$

разность между абсолютной скоростью и скоростью.

Величина $DR\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{D\}\; \{R\}\}\}$называется относительной избыточностью и дает максимально возможное коэффициент сжатия данных, когда он выражается как процент, на который можно уменьшить размер файла. (При выражении в виде отношения исходного размера файла к размеру сжатого файла величина $R:\; r\; \{\backslash \; displaystyle\; R:\; r\}$дает максимальный коэффициент сжатия, который может быть достигнут.) Дополняет концепция относительной избыточности - это эффективность, определяемая как $r\; R,\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{r\}\; \{R\}\},\}$, так что $r\; R\; +\; DR\; =\; 1\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{r\}\; \{R\}\}\; +\; \{\backslash \; frac\; \{D\}\; \{R\}\}\; =\; 1\}$. Источник без памяти с равномерным распределением имеет нулевую избыточность (и, следовательно, 100% эффективность) и не может быть сжат.

Мера избыточности между двумя переменными - это взаимная информация или ее нормализованный вариант. Мера избыточности среди многих переменных определяется общей корреляцией.

Избыточность сжатых данных относится к разнице между ожидаемой длиной сжатых данных $n\; \{\backslash \; displaystyle\; n\}$сообщения $L\; (M\; n)\; \{\backslash \; displaystyle\; L\; (M\; ^\; \{n\})\; \backslash ,\; \backslash !\}$(или ожидаемая скорость передачи данных $L\; (M\; n)\; /\; n\; \{\backslash \; displaystyle\; L\; (M\; ^\; \{n\})\; /\; n\; \backslash ,\; \backslash !\}$) и энтропия $nr\; \{\backslash \; displaystyle\; nr\; \backslash ,\; \backslash !\}$(или коэффициент энтропии $r\; \{\backslash \; displaystyle\; r\; \backslash ,\; \backslash !\}$). (Здесь мы предполагаем, что данные являются эргодическими и стационарными, например, источником без памяти.) Хотя разница в скорости $L\; (M\; n)\; /\; n\; -\; r\; \{\backslash \; displaystyle\; L\; (M\; ^\; \{n\})\; /\; nr\; \backslash ,\; \backslash !\}$может быть сколь угодно малым, поскольку $n\; \{\backslash \; displaystyle\; n\; \backslash ,\; \backslash !\}$увеличивается, фактическая разница $L\; (M\; n)\; -\; nr\; \{\backslash \; displaystyle\; L\; (M\; ^\; \{n\})\; -\; nr\; \backslash ,\; \backslash !\}$, не может, хотя теоретически может быть ограничено сверху единицей в случае Источники без памяти с конечной энтропией.

• Кодирование с минимальной избыточностью
  • Кодирование Хаффмана
• Сжатие данных
• Функция Хартли
• Негентропия
• Теорема кодирования источника
• Избыточная полнота

• Реза, Фазлолла М. (1994) [1961]. Введение в теорию информации. Нью-Йорк: Довер [Макгроу-Хилл]. ISBN 0-486-68210-2.
• Шнайер, Брюс (1996). Прикладная криптография: протоколы, алгоритмы и исходный код на C. Нью-Йорк: John Wiley Sons, Inc. ISBN 0-471-12845-7.
• Auffarth, B; Lopez-Sanchez, M.; Серкидес, Дж. (2010). «Сравнение мер избыточности и релевантности для выбора признаков в классификации тканей компьютерной томографии». Достижения в области интеллектуального анализа данных. Приложения и теоретические аспекты. Springer. С. 248–262. CiteSeerX 10.1.1.170.1528.