WikiDer > Избыточность (теория информации)
Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. (Июнь 2016 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В Теория информации, избыточность измеряет дробную разницу между энтропия H (X) ансамбля Икс, и его максимально возможное значение .[1][2] Неформально это количество потраченного впустую «пространства», используемого для передачи определенных данных. Сжатие данных это способ уменьшить или устранить нежелательную избыточность, в то время как контрольные суммы являются способом добавления желаемой избыточности в целях обнаружение ошибок при общении по шумной канал ограниченного емкость.
Количественное определение
При описании избыточности необработанных данных ставка источника информации - средний энтропия за символ. Для источников без памяти это просто энтропия каждого символа, в то время как в наиболее общем случае случайный процесс, это
в пределе, поскольку п уходит в бесконечность совместная энтропия из первых п символы, разделенные на п. В теории информации принято говорить о «скорости» или «энтропия"языка. Это уместно, например, когда источником информации является английская проза. Скорость источника без памяти просто , поскольку по определению нет взаимозависимости последовательных сообщений источника без памяти.[нужна цитата]
В абсолютная ставка языка или источника просто
то логарифм из мощность пространства сообщений или алфавита. (Эту формулу иногда называют Функция Хартли.) Это максимально возможная скорость передачи информации с использованием этого алфавита. (Логарифм должен быть приведен к основанию, соответствующему используемой единице измерения.) Абсолютная скорость равна фактической скорости, если источник не имеет памяти и имеет равномерное распределение.
В абсолютная избыточность тогда можно определить как
разница между абсолютной ставкой и ставкой.
Количество называется относительная избыточность и дает максимально возможное степень сжатия данных, когда выражается в процентах, на которые можно уменьшить размер файла. (При выражении в виде отношения исходного размера файла к размеру сжатого файла количество дает максимально достижимую степень сжатия.) В дополнение к концепции относительной избыточности эффективность, определяется как так что . Источник без памяти с равномерным распределением имеет нулевую избыточность (и, следовательно, 100% эффективность) и не может быть сжат.
Прочие понятия
Мера избыточность между двумя переменными находится взаимная информация или нормализованный вариант. Мера избыточности среди многих переменных определяется полная корреляция.
Избыточность сжатых данных относится к разнице между ожидал длина сжатых данных Сообщения (или ожидаемая скорость передачи данных ) и энтропия (или скорость энтропии ). (Здесь мы предполагаем, что данные эргодический и стационарный(например, источник без памяти.) Хотя разница в скорости может быть сколь угодно малым, поскольку увеличился, фактическая разница , не может, хотя теоретически может быть ограничено сверху значением 1 в случае источников без памяти с конечной энтропией.
Смотрите также
- Кодирование с минимальной избыточностью
- Сжатие данных
- Функция Хартли
- Негэнтропия
- Теорема исходного кода
- Неполнота
Рекомендации
- ^ Здесь предполагается - множества, на которых определены распределения вероятностей.
- ^ Маккей, Дэвид Дж. (2003). «2.4 Определение энтропии и связанных с ней функций». Теория информации, логический вывод и алгоритмы обучения. Издательство Кембриджского университета. п. 33. ISBN 0-521-64298-1.
В избыточность измеряет дробную разницу между H (X) и его максимально возможное значение,
- Реза, Фазлолла М. (1994) [1961]. Введение в теорию информации. Нью-Йорк: Довер [Макгроу-Хилл]. ISBN 0-486-68210-2.
- Шнайер, Брюс (1996). Прикладная криптография: протоколы, алгоритмы и исходный код на C. Нью-Йорк: John Wiley & Sons, Inc. ISBN 0-471-12845-7.
- Ауффарт, B; Lopez-Sanchez, M .; Серкидес, Дж. (2010). «Сравнение показателей избыточности и релевантности для выбора признаков в классификации тканей компьютерной томографии». Достижения в области интеллектуального анализа данных. Приложения и теоретические аспекты. Springer. С. 248–262. CiteSeerX 10.1.1.170.1528.