- •1. Понятие информатики
- •2. Понятие и характерные черты информации
- •Свойства информации
- •3. Виды сигнала как материального носителя информации
- •Преобразования сигнала
- •4. Системы счисления
- •5. Правила перевода чисел
- •Правила перевода целых чисел
- •Правила перевода правильных дробей
- •Правило перевода неправильных дробей
- •6. Кодирование по образцу
- •0001011101000011
- •0010 0000 0001 0010
- •2 0 1 2
- •00010100
- •Ascii-коды
- •Коды, учитывающие частоту информационных элементов
- •Коды Грея
- •7. Криптографическое кодирование
- •Метод простой подстановки
- •Метод Виженера
- •8. Эффективное кодирование
- •Универсальные методы
- •Метод Шеннона-Фано
- •Метод Хаффмена
- •9. Повышение эффективности кодирования универсальными кодами
- •Декодирование эффективных кодов
- •10. Специальные методы эффективного кодирования
- •Методы эффективного кодирования числовых последовательностей
- •2 14 18 27 34
- •2 12 4 9 7.
- •55556666888888
- •5(4)6(4)8(6),
- •Методы эффективного кодирования словарей
- •Методы эффективного кодирования естественно-языковых текстов
- •11. Помехозащитное кодирование
- •Искажение кодовых комбинаций
- •Кодовое расстояние и корректирующая способность кода
- •12. Коды, исправляющие ошибки
- •13. Измерение дискретного сигнала
- •Структурный подход к измерению информации
- •Геометрическая мера
- •Комбинаторная мера
- •Аддитивная мера
- •14. Статистический подход к измерению информации
- •Семантический подход к измерению информации
- •Полезность информации
- •Истинность информации
- •15. Структура компьютера и принципы его функционирования
- •16. Устройство управления
- •17. Арифметико-логическое устройство
- •18.Формы представления целых чисел
- •Формы представления вещественных чисел
- •Коды представления числовых данных
- •19.При сложении целых чисел последовательность шагов следующая:
- •20.Правило сложения вещественных чисел.
10. Специальные методы эффективного кодирования
В зависимости от типа исходного сообщения эти методы делятся на методы эффективного кодирования числовых последовательностей, словарей, текстов. Отличительная черта этих методов – отсутствие необходимости построения кодовой таблицы.
Методы эффективного кодирования числовых последовательностей
Различают два метода – разностное кодирование и кодирование повторений.
Суть разностного кодирования заключается в хранении вместо абсолютных значений либо разностей двух смежных чисел, либо отклонения чисел от их среднего значения. Например, для последовательности чисел:
2 14 18 27 34
первый способ даст последовательность:
2 12 4 9 7.
Этот метод эффективен для медленно меняющихся последовательностей. Его недостаток состоит в том, что для получения значения n-го члена последовательности надо декодировать все предыдущие (n-1) членов последовательности.
Второй способ порождает последовательность:
-17 -5 -1 8 15 ,
поскольку среднее значение для исходной последовательности - 19.
Этот способ эффективен, когда максимальное отклонение от среднего значительно меньше абсолютного значения среднего. Достоинство данного подхода заключается в независимости декодирования любого n-го члена числовой последовательности от декодирования остальных ее составляющих: для этого нужно знать только значение среднего арифметического данной последовательности, что вынуждает хранить это число вместе с самой закодированной последовательностью.
Оба метода могут использоваться не только для эффективного кодирования прикладных массивов данных (тех, которые создает пользователь компьютера), но и для сжатия любой информации во внутреннем представлении.
Кодирование повторений заключается в замене цепочки одинаковых цифровых символов самим символом и числом повторений (возможно включение разделителей). Например, для последовательности:
55556666888888
применение этого способа даст последовательность:
5(4)6(4)8(6),
где круглые скобки играют роль разделителей.
Данный метод может быть использован для эффективного кодирования растровых форматов изображений. Растровыми называются форматы изображений, которые получаются во время ввода изображения путем кодирования каждой точки – пиксела (pixel – PIсture ELement) – двумерного пространства, на котором расположено исходное изображение, даже если эта точка не содержит самого изображения. Очевидно, в общем случае, изображение занимает не все пространство. Тем не менее, кодированию подлежат и «пустоты», при этом те точки, которые содержат изображение, в простейшем случае (для монохромных изображений) кодируются двоичной 1, точки без изображения кодируются двоичным 0.
Методы эффективного кодирования словарей
Словари очень часто применяются в современных прикладных программных продуктах, например, при проверке орфографии в текстовом процессоре WinWord. Для их рационального хранения применяются рассмотренные ниже методы.
Обычно в словарях слова упорядочены по алфавиту, поэтому для эффективного кодирования словарей можно применить метод, аналогичный разностному кодированию для числовых последовательностей: у каждого n-го слова отбрасываются начальные буквы, совпадающие с начальными буквами предыдущего (n-1)-го слова, и заменяются на количество отброшенных букв.
Недостаток данного подхода заключается в необходимости декодировать все (n-1) слов, начиная с базового слова, для декодирования n-го слова словаря.
Второй подход состоит в том, что формируется вспомогательный словарь, в который включаются наиболее часто повторяющиеся части слов. Каждому такому фрагменту назначается код, например, его порядковый номер во вспомогательном словаре. Затем в основном словаре фрагменты слов заменяются их кодами из вспомогательного словаря.