Изменения

Перейти к: навигация, поиск

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

4655 байт добавлено, 08:40, 16 октября 2011
Нет описания правки
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической переработки.
В более узком смысле кодированием информации называют представление информации в виде кода.
Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
== Код ==
'''Код — набор условных обозначений ''' — правило (кодовых словалгоритм) для предоставления информациисопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''. '''Код фиксированной длины''' (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом. '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''. '''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
==== Примеры кодов ====
== Префиксный код ==
'''Префиксный код ''' — код, в котором никакое кодовое слово не имеющий ни одного кодового слова, которое являлось бы является префиксом любого какого-то другого кодового слова данного кода.Любой префиксный код является однозначно декодируемыми разделимым. Также префиксный код иногда называют ''мнгновенным кодом''. Оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда достижимо при использовании префиксного кода. Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла. '''Кома-код''' {{---}} разновидность префиксного кода, в котором каждый символ кодируется строкой из единиц, в конце которой стоит ноль. Множество строк кода имеет вид {0,10,110,1110,11110,...}. Недостаток кома-кода в том, что элементы кода могут быть очень длинными и занимать большой объём памяти.  Рассмотрим пример кодирования с помощью префиксного кода.
Код Пусть U {{---}} множество исходных символов, Z {{---}} кодовый алфавит, состоящий Z* {{---}} строчки из слов 0Z. Код {{---}} отображение c : U <tex>\rightarrow</tex> Z*. c* : U* <tex>\rightarrow</tex> Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn) U = {a, 10b, 11 является префикснымc}; Z = {0, то есть 1}; c(a) = 00; c(b) = 01; c(c) = 1; Закодируем строку: abacaba 100111010c*(abacaba) = 0001001000100Так как такой код можно однозначно разбить на слова единственным образом: 10 0 11 10 1000 01 00 1 00 01 00он является префиксным.
==== Примеры префиксных кодов ====
* Код Хаффмана
* Код Шеннона-Фано
* UTF-8{{---}} префиксный, так как является блоковым.
== Ссылки ==
* [http://ru.wikipedia.org Википедия — свободная энциклопедия]
== Литература ==* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ {{---}} Издательство: «Вильямс», 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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]
277
правок

Навигация