1632
правки
Изменения
м
Код Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']] — набор условных обозначений (для такого кода любое слово, составленное из кодовых слов) для предоставления информации, можно декодировать только единственным способом.
Префиксный код — кодМы можем ее однозначно декодировать, не имеющий ни одного кодового словатак как знаем, которое являлось бы префиксом любого другого кодового слова данного кода.Любой префиксный код является однозначно декодируемымчто слева от двойки и справа от тройки всегда стоит единица.
Код, состоящий из слов 0, 10, 11 является префиксным, то есть строку 100111010можно разбить на слова единственным образомПосле декодирования получаем: 10 0 11 10 10<tex>abbca</tex>
rollbackEdits.php mass rollback
{{Определение|id=def1|definition='''Кодирование информации''' (англ. ''information coding'') — процесс преобразования информации из одной формы в другуюотображение данных на кодовые слова.}}Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической переработкиобработки.
В более узком смысле кодированием информации называют представление информации в виде кода.
Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
== Код ==
{{Определение
|id=def2
|definition=Пусть <tex>U</tex> {{---}} множество исходных символов, <tex>Z</tex> {{---}} кодовый алфавит, <tex>Z^*</tex> {{---}} множество всех строк конечной длины из <tex>Z</tex>.<br> '''Код''' (англ. ''code'') {{---}} отображение <tex>c : U \rightarrow Z^*</tex> и <tex>c^* : U^* \rightarrow Z^*</tex> так, что <tex>c^*(x_1 x_2 ... x_n) = c(x_1)c(x_2)..c(x_n)</tex>
}}
==== Виды кодов ====
* '''[[Представление символов, таблицы кодировок | Код фиксированной длины]]''' (англ. ''fixed-length code'') {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
* '''Код переменной длины''' (англ. ''variable-length code'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
** [[Кодирование информации#Префиксный код | '''Префиксный код''']] {{---}} код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого.
==== Примеры кодов ====
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.* Азбука Морзе— не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз. == Однозначно декодируемый код =={{Определение|id=def3|definition='''Однозначно декодируемый код''' (англ. ''uniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.}}Пусть есть код заданный следующей кодовой таблицей: <tex>a_1 \rightarrow b_1</tex> <tex>a_2 \rightarrow b_2</tex> <tex> \dots </tex> <tex>a_k \rightarrow b_k</tex> Код является однозначно декодируемым, только тогда, когда для любых строк, составленных из кодовых слов, вида: <tex>b_{i_1} b_{i_2} \dots b_{i_n} = b_{j_1} b_{j_2} \dots b_{j_m}</tex> Всегда выполняются равенства: <tex>n = m </tex> <tex> b_{i_1} = b_{j_1}</tex> <tex> b_{i_2} = b_{j_2} </tex> <tex> \dots </tex> * ASCII<tex> b_{i_n} = b_{j_m}</tex> Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
== Префиксный код ==
{{Определение
|id=def4
|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
}}
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
=== Пример кодирования ===
<tex>U = \{ a, b, c \}</tex>
<tex> Z = \{ 0, 1 \}</tex>
<tex> c(a) = 00 </tex>
<tex> c(b) = 01 </tex>
<tex> c(c) = 1 </tex>
Закодируем строку <tex>abacaba</tex> :
<tex>c^*(abacaba) = 0001001000100</tex>
Такой код можно однозначно разбить на слова:
<tex>00\ 01\ 00\ 1\ 00\ 01\ 00</tex>
=== Преимущества префиксных кодов ===
* Однозначно декодируемый и разделимый
* Удается получить более короткие коды, чем с помощью кода фиксированной длины.
* Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.
=== Недостатки префиксных кодов ===
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
=== Пример неудачного декодирования ===
Предположим, что последовательность <tex>abacaba</tex> из примера передалась неверно и стала:
<tex>c^{**}(abacaba) = 0001001\ 1\ 00100</tex>
Разобьем ее согласно словарю:
<tex> 00\ 01\ 00\ 1\ 1\ 00\ 1\ 00</tex>
<tex>a\quad b\quad a\ c\ c\quad a\ c\ a</tex>
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
=== Не префиксный однозначно декодируемый код ===
Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:
<tex>U = \{ a, b, c \}</tex>
<tex>Z = \{ 1, 2, 3 \}</tex>
<tex> c(a) = 1 </tex>
<tex> c(b) = 12 </tex>
<tex> c(c) = 31 </tex>
Закодируем <tex>abbca</tex>, получим кодовую строку: <tex>11212311</tex>
==== Примеры префиксных кодов ==См. также ==* Код Хаффмана[[Представление символов, таблицы кодировок]]* Код Шеннона-Фано[[Неравенство Крафта]]* UTF-8[[Неравенство Макмиллана]]
== Ссылки Источники информации ==* [http://ruen.wikipedia.org Википедия — свободная энциклопедия/wiki/Prefix_code Wikipedia {{---}} Prefix code]* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 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* Алексеев В.Б. «Дискретная математика (II семестр)»[[Категория: Дискретная математика и алгоритмы]][[Категория: Представление информации]]
