Кодирование информации — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Префиксный код)
Строка 6: Строка 6:
 
В более узком смысле кодированием информации называют представление информации в виде кода.
 
В более узком смысле кодированием информации называют представление информации в виде кода.
 
Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
 
Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
 +
 +
Рассмотрим пример кодирования с помощью [[http://neerc.ifmo.ru/mediawiki/index.php/Кодирование_информации#.D0.9F.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D1.8B.D0.B9_.D0.BA.D0.BE.D0.B4: префиксного кода]].
 +
 +
Пусть U {{---}} множество исходных символов, Z {{---}} кодовый алфавит, Z* {{---}} строчки из Z.
 +
Код {{---}} отображение c : U <tex>\rightarrow</tex> Z*. c* : U* <tex>\rightarrow</tex> Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn)
 +
U = {a,b,c}; Z = {0,1};
 +
c(a) = 00; c(b) = 01; c(c) = 1;
 +
Закодируем строку: abacaba
 +
c*(abacaba) = 0001001000100
 +
Такой код можно однозначно разбить на слова:
 +
00 01 00 1 00 01 00
 +
поэтому он является префиксным.
  
 
== Код ==
 
== Код ==
Строка 13: Строка 25:
 
}}
 
}}
 
==== Виды кодов ====
 
==== Виды кодов ====
* '''Код фиксированной длины''' (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
+
* [http://neerc.ifmo.ru/mediawiki/index.php/Представление_символов,_таблицы_кодировок: '''Код фиксированной длины'''] (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
 
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
 
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
 
* '''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
 
* '''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
Строка 30: Строка 42:
  
 
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла.
 
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла.
 
Рассмотрим пример кодирования с помощью префиксного кода.
 
 
Пусть U {{---}} множество исходных символов, Z {{---}} кодовый алфавит, Z* {{---}} строчки из Z.
 
Код {{---}} отображение c : U <tex>\rightarrow</tex> Z*. c* : U* <tex>\rightarrow</tex> Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn)
 
U = {a,b,c}; Z = {0,1};
 
c(a) = 00; c(b) = 01; c(c) = 1;
 
Закодируем строку: abacaba
 
c*(abacaba) = 0001001000100
 
Такой код можно однозначно разбить на слова:
 
00 01 00 1 00 01 00
 
поэтому он является префиксным.
 
  
 
==== Недостатки префиксных кодов ====
 
==== Недостатки префиксных кодов ====

Версия 02:57, 27 ноября 2011

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

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

Рассмотрим пример кодирования с помощью [префиксного кода].

Пусть U — множество исходных символов, Z — кодовый алфавит, Z* — строчки из Z. 
Код — отображение c : U [math]\rightarrow[/math] Z*. c* : U* [math]\rightarrow[/math] Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn)
U = {a,b,c}; Z = {0,1};
c(a) = 00; c(b) = 01; c(c) = 1;
Закодируем строку: abacaba
c*(abacaba) = 0001001000100

Такой код можно однозначно разбить на слова:

00 01 00 1 00 01 00

поэтому он является префиксным.

Код

Определение:
Код — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется кодовым словом.

Виды кодов

  • Код фиксированной длины (fixed-length code) — кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется равномерным или блоковым кодом.
  • Код переменной длины (variable-length code) — кодирование производится с помощью строк переменной длины. Также называется неравномерным кодом.
  • Разделимый код — код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.

Примеры кодов

  • Азбука Морзе
  • ASCII

Префиксный код

Определение:
Префиксный код — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.

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

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

Недостатки префиксных кодов

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

Пример:

Возьмём строку abacaba, и закодируем ее аналогично предыдущему примеру.
c*(abacaba) = 0001001000100
Предположим, что последовательность передалась неверно и стала:
0001001100100
Разобьем ее согласно словарю:
00 01 00 1 1 00 1 00
a  b  a  c c a  c a

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

  • Необходимость хранить словарь декодировки символов.

Примеры префиксных кодов

  • Код Хаффмана
  • Код Шеннона-Фано
  • UTF-8 — префиксный, так как является блоковым.

Литература

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Издательство: «Вильямс», 2011 г. - 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
  • Джеймс Андерсон. Дискретная математика и комбинаторика — Издательство: «Вильямс», 2004 г. - 960 стр. — ISBN 978-0-13-086998-2
  • Ф. А. Новиков. Дискретная математика для программистов — Издательство: «Питер», 2001 г. - 304 стр. — ISBN 5-94723-741-5 978-5-94723-741-2