Тексты и кодирование

Тексты и кодирование Информатика. Лекция №2

Знаки

Знаки – это символы, отображающие объекты окружающего мира и имеющие определенное значение.

С древних времен их использовали для хранения информации и ее передачи на расстояния.

Классификация знаков

Физическая природа знака

Алфавит

1. Зрительные знаки

Буквы, цифры, дорожные знаки,

2. Слуховые знаки

ноты, знаки хим.элементов

Сигналы звонка, колокола,

3. Осязательные знаки

свистка, гудка

Азбука Брайля (для слабовидящих),

4. Обонятельные знаки

Рукопожатия и т.д.

Аромотерапия,

5. Вкусовые знаки

запах парфюма, газа

Кисловатый вкус

вызывает аппетит.

Знаковая система

Знаковая система – это набор знаков и правил для представления информации.

Человек в своей жизни использует знаковые системы, которые называются языками .

Языки

естественные

формальные

человек использует для обмена информацией с механизмами.

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

Текстовая информация

Текстовая информация – это информация, выраженная с помощью естественных и формальных языков в письменной форме.

К текстовой информации относятся:

► Буквы русского алфавита

► Буквы латинского алфавита

► Цифры

► Знаки

► Математические символы

Кодирование информации

Кодирование – это преобразование информации из одной формы представления в другую.

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

10010010

Декодирование информации

Декодирование — преобразование информации в форму, удобную для восприятия.

10010010

Виды кодов

Код

Равномерный

Неравномерный

код переменной длины

код постоянной длины

Однозначно декодируемый код

Однозначно декодируемый код - это код, который можно расшифровать единственным способом .

Пример:

Пусть для кодирования фразы «МАМА МЫЛА ЛАМУ» выбран такой код:

М

00

А

1

Ы

Л

01

У

0

10

пробел

11

9

Двоичное кодирование

Двоичное кодирование – один из распространенных способов представления информации. 

► 66 букв русского языка;

► 56 букв английского языка;

► 10 цифр (0-9);

► знаки препинания.

Для кодирования 1 символа в ПК используется 1 байт информации .

Равномерный код. Формула Хартли

N = 2 i

где

N — это количество вариантов,

i — это количество бит, не обходимых для кодирования.

Равномерный код.

Во фразе «МАМА МЫЛА ЛАМУ» 6 символов, поэтому можно использовать 3-битный код:

8 = 2 3

Равномерный код неэкономичен.

М

000

А

Ы

001

Л

010

У

011

100

пробел

101

Неравномерный код.

М

01

А

00

Ы

1011

Л

100

У

пробел

1010

11

Неравномерное кодирование основывается на условии Фано:

Никакое кодовое слово не совпадает с началом другого кодового слова .

Неравномерный код

Префиксные коды – это коды, для которых выполняется условие Фано.

Все сообщения, закодированные с помощью префиксных кодов, декодируются однозначно.

Задание

Расшифруйте зашифрованный код

1000001101011010001001101101110000

М

01

А

00

Ы

1011

Л

100

У

пробел

1010

11

Обратное условие Фано

Никакое кодовое слово не совпадает с окончанием другого кодового слова.  

Постфиксные коды – это коды для которых выполняется обратное условие Фано.

М

10

А

Ы

00

1101

Л

У

001

0101

пробел

11

Сжатие данных

Сжатие – это кодирование информации с помощью специального кода, приводящее к уменьшению ее объема.

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

Алгоритм Хаффмана

Идея основана на частоте встречаемости символа.

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

Символ, который встречается реже всего, получает очень длинный код.

Алгоритм Хаффмана

Пример:

Дано сообщение:

aaabcbeeffaabfffedbac

Производится последовательное объединение наиболее редких символов, постепенно создается граф.

a

b

c

d

e

f

Алгоритм Хаффмана

Задание

Используя алгоритма Хаффмана, закодируйте сообщение: Хаффман

Таблицы кодировок

При обработке текстовой информации в компьютере каждый символ представляется двоичным кодом .

Присвоение знаку конкретного двоичного кода – это вопрос соглашения, которое фиксируется в кодовой таблице .

Кодовая таблица ASCII

ASCII - первая распространенная кодировочная таблица.

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

Каждому символу отводится 7 бит, а значит, всего было закодировано 128 символов.

Кодовая таблица ASCII

Коды от 0 до 32 – функциональные клавиши

Современные кодовые таблицы

Mac

КОИ-8

Windows

MS-DOS

ISO

Кодировка Unicode

1 символ - 2 байта (16 бит), которыми можно закодировать 65 536 символов .

Тексты, созданные в одной кодировке, не будут правильно отображаться в другой!

Задание

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Задание

Построить код Хаффмана для фразы «на дворе трава, на траве дрова»