1632
правки
Изменения
м
'''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.<tex>a_1 \rightarrow b_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>
Пусть 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
поэтому он является префиксным.
* Необходимость хранить словарь декодировки символов.
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'' (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины— префиксный. Также он называется ''равномерным'' или ''блоковым'' кодом* Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
== Однозначно декодируемый код =={{Определение|id=def3|definition='''Код переменной длиныОднозначно декодируемый код''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длиныангл. Также называется ''неравномерным кодомuniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.}}Пусть есть код заданный следующей кодовой таблицей:
<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> <tex> b_{i_n} =b_{j_m}</tex>* Азбука Морзе * ASCIIЗаметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
== Префиксный код ==
{{Определение
|id=def4
|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
}}
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
=== Пример кодирования ===
<tex>U = \{ a, b, c \}</tex>
<tex> Z = \{ 0, 1 \}</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> Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица. После декодирования получаем: <tex>abbca</tex>
== Ссылки См. также ==* [http://ru.wikipedia.org Википедия — свободная энциклопедия[Представление символов, таблицы кодировок]]* [[Неравенство Крафта]]* [http://konishchevdmitry.blogspot.com/2010/01/blog-post.html Что такое выравнивание, и как оно влияет на работу ваших программ[Неравенство Макмиллана]]
== Литература Источники информации ==* [http://en.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 семестр)»
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]
