Код префиксный что это значит

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

Пре́фиксный код в теории кодирования — код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует. Хотя префиксный код состоит из слов разной длины, эти слова можно записывать без разделительного символа.

Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом:

Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и то же сообщение можно трактовать несколькими способами.

Определение

Так называемые «префиксы» могут быть получены путём последовательного отбрасывания последнего знака кодовой комбинации. Например, для кодовой комбинации 11101101 префиксами будут 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

Если промежутков или других знаков препинания между кодовыми комбинациями нет, то для однозначного декодирования комбинации 111011101 ни одна из кодовых комбинаций не может быть представлена перечисленными вариантами (префиксами). Код называется префиксным, если ни одна из его комбинаций не является префиксом другой комбинации того же кода. Часть кодовой комбинации, которая дополняет префикс до самой комбинации, называется суффиксом. Префиксные коды наглядно могут быть представлены с помощью кодовых деревьев. Если ни один узел кодового дерева не является вершиной данного кода, то он обладает свойствами префикса. Узлы дерева, которые не соединяются с другими, называются конечными. Комбинации, которые им соответствуют, являются кодовыми комбинациями префиксного кода.

Примеры

Любой код со словом фиксированной длины, очевидно, является префиксным. Рассмотрим несколько нетривиальных примеров.

• Телефонные номера в стационарных сетях.
• UTF-8.
• Код Хаффмана, применяемый для сжатия данных.
• Синтаксис Паскаля и других языков с LL(1)-синтаксисом (если считать символом лексему, а словом — оператор). Поэтому для определения типа оператора транслятору Паскаля не приходится возвращать считанные символы в поток либо запоминать их в стеке.

Код Морзе не является префиксным. В него, кроме точки и тире, входит также символ-разделитель — пауза длиной в тире.

См. также

Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным.

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Префиксный код» в других словарях:

префиксный код — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN prefix code … Справочник технического переводчика

код Хаффмана — Префиксный код, в котором длина кодирующего слова обратно пропорциональна встречаемости кодируемого элемента. [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в целом… … Справочник технического переводчика

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

Универсальный код — для целых чисел в сжатии данных префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение монотонно… … Википедия

Универсальный код (сжатие данных) — Универсальный код для целых чисел в сжатии данных префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распространение … … Википедия

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

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

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

Первичный алфавит — Эта статья о коде в теории информации, другие значения этого слова см. в код (значения). Код правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков) (или сигналов). Кодом также называется… … Википедия

Неравенство Крафта — Макмиллана — В теории кодирования, неравенство Крафта Макмиллана даёт необходимое и достаточное условие существования разделимых и префиксных кодов, обладающих заданным набором длин кодовых слов. Содержание 1 Предварительные определения 2 … Википедия

Источник

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

Определение:

Кодирование информации (англ. information coding) — отображение данных на кодовые слова.

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

Содержание

Код [ править ]

Определение:

Пусть [math]U[/math] — множество исходных символов, [math]Z[/math] — кодовый алфавит, [math]Z^*[/math] — множество всех строк конечной длины из [math]Z[/math] . Код (англ. code) — отображение [math]c : U \rightarrow Z^*[/math] и [math]c^* : U^* \rightarrow Z^*[/math] так, что [math]c^*(x_1 x_2 . x_n) = c(x_1)c(x_2)..c(x_n)[/math]

Виды кодов [ править ]

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

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

Примеры кодов [ править ]

• ASCII — блочный.
• Код Хаффмана (англ. Huffman code) — префиксный.
• Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.

Однозначно декодируемый код [ править ]

Определение:

Однозначно декодируемый код (англ. uniquely decodable code) — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.

Пусть есть код заданный следующей кодовой таблицей:

[math]a_1 \rightarrow b_1[/math]

[math]a_2 \rightarrow b_2[/math]

[math]a_k \rightarrow b_k[/math]

Код является однозначно декодируемым, только тогда, когда для любых строк, составленных из кодовых слов, вида:

Всегда выполняются равенства:

Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.

Префиксный код [ править ]

Определение:

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

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

Пример кодирования [ править ]

[math] c(a) = 00 [/math]

[math] c(b) = 01 [/math]

[math] c(c) = 1 [/math]

Закодируем строку [math]abacaba[/math] :

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

[math]00\ 01\ 00\ 1\ 00\ 01\ 00[/math]

Преимущества префиксных кодов [ править ]

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

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

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

Пример неудачного декодирования [ править ]

Предположим, что последовательность [math]abacaba[/math] из примера передалась неверно и стала:

[math]c^<**>(abacaba) = 0001001\ 1\ 00100[/math]

Разобьем ее согласно словарю:

[math] 00\ 01\ 00\ 1\ 1\ 00\ 1\ 00[/math]

[math]a\quad b\quad a\ c\ c\quad a\ c\ a[/math]

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

Не префиксный однозначно декодируемый код [ править ]

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

[math] c(a) = 1 [/math]

[math] c(b) = 12 [/math]

[math] c(c) = 31 [/math]

Закодируем [math]abbca[/math] , получим кодовую строку: [math]11212311[/math]

Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица.

После декодирования получаем: [math]abbca[/math]

Источник

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

• Пре́фиксный код в теории кодирования — код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует. Хотя префиксный код состоит из слов разной длины, эти слова можно записывать без разделительного символа.

Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом:

0 10 0 11 0 11 10

Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и то же сообщение можно трактовать несколькими способами.

0 10 0 11 0 11 10

0 100 11 0 11 10

Связанные понятия

В области математики и теории информации линейный код — это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.

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

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

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

Источник

Код префикса — Prefix code

Префикс кода представляет собой тип кода системы отличается своим владении «приставкой собственности», который требует , чтобы не весь код слово в системе , которая является префиксом (начальный сегмент) любого другого кодового слова в системе. Это тривиально верно для кода с фиксированной длиной, поэтому только в качестве предмета рассмотрения в коде с переменной длиной .

Например, код с кодовыми словами <9, 55>имеет свойство префикса; код, состоящий из <9, 5, 59, 55>, нет, потому что «5» является префиксом «59», а также «55». Код префикса — это уникально декодируемый код : при наличии полной и точной последовательности получатель может идентифицировать каждое слово, не требуя специального маркера между словами. Однако есть однозначно декодируемые коды, которые не являются кодами префикса; например, обратная сторона префиксного кода все еще однозначно декодируется (это суффиксный код), но это не обязательно префиксный код.

Коды префикса также известны как префикс коды , свободный , префиксные коды состояния и мгновенные коды . Хотя кодирование Хаффмана является лишь одним из многих алгоритмов получения префиксных кодов, префиксные коды также широко называются «кодами Хаффмана», даже если код не был создан с помощью алгоритма Хаффмана. Термин « код без запятых» иногда также применяется как синоним для кодов без префиксов, но в большинстве математических книг и статей (например) код без запятых используется для обозначения самосинхронизирующегося кода , подкласса префиксных кодов.

Используя префиксные коды, сообщение может быть передано как последовательность сцепленных кодовых слов без каких — либо внеполосных маркеров или (альтернативно) специальных маркеров между словами для кадрирования слов в сообщении. Получатель может однозначно декодировать сообщение, многократно находя и удаляя последовательности, которые образуют допустимые кодовые слова. Обычно это невозможно с кодами, в которых отсутствует свойство префикса, например <0, 1, 10, 11>: получатель, читающий «1» в начале кодового слова, не будет знать, было ли это полное кодовое слово » 1 », или просто префикс кодового слова« 10 »или« 11 »; поэтому строку «10» можно интерпретировать либо как одиночное кодовое слово, либо как объединение слов «1», затем «0».

Коды Хаффмана переменной длины , телефонные коды стран , часть ISBN для страны и издателя , вторичные коды синхронизации, используемые в стандарте беспроводной связи UMTS W-CDMA 3G, и наборы команд (машинный язык) большинства компьютерных микроархитектур являются кодами префикса.

Коды префикса не являются кодами исправления ошибок . На практике сообщение может сначала быть сжато префиксным кодом, а затем снова закодировано канальным кодированием (включая исправление ошибок) перед передачей.

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

СОДЕРЖАНИЕ

Методы

Если каждое слово в коде имеет одинаковую длину, код называется кодом фиксированной длины или блочным кодом (хотя термин « блочный код» также используется для кодов с исправлением ошибок фиксированного размера при канальном кодировании ). Например, буквы ISO 8859-15 всегда имеют длину 8 бит. Буквы UTF-32 / UCS-4 всегда имеют длину 32 бита. Ячейки ATM всегда имеют длину 424 бита (53 байта). Код фиксированной длины с фиксированной длиной k битов может кодировать до исходных символов. 2 k <\ displaystyle 2 ^ >

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

Усеченное двоичное кодирование — это прямое обобщение кодов фиксированной длины для случаев, когда количество символов n не является степенью двойки. Исходным символам присваиваются кодовые слова длины k и k +1, где k выбирается так, чтобы 2 k k + 1 .

Кодирование Хаффмана — более сложный метод построения префиксных кодов переменной длины. Алгоритм кодирования Хаффмана принимает в качестве входных данных частоты, которые должны иметь кодовые слова, и создает префиксный код, который минимизирует средневзвешенное значение длин кодовых слов. (Это тесно связано с минимизацией энтропии.) Это форма сжатия данных без потерь, основанная на энтропийном кодировании .

Некоторые коды отмечают конец кодового слова специальным символом «запятая», отличным от обычных данных. Это в некоторой степени аналогично пробелам между словами в предложении; они отмечают, где заканчивается одно слово и начинается другое. Если каждое кодовое слово заканчивается запятой, и запятая не появляется где-либо еще в кодовом слове, код автоматически освобождается от префиксов. Однако современные системы связи отправляют все в виде последовательностей «1» и «0» — добавление третьего символа было бы дорогостоящим, а использование его только в конце слова было бы неэффективным. Код Морзе — это повседневный пример кода переменной длины с запятой. Длинные паузы между буквами и еще более длинные паузы между словами помогают людям распознать, где заканчивается одна буква (или слово) и начинается следующая. Точно так же кодирование Фибоначчи использует цифру «11» для обозначения конца каждого кодового слова.

Связанные понятия

Код суффикс представляет собой набор слов ни один из которых представляет собой суффикс любой другой; эквивалентно, набор слов, противоположных префиксному коду. Как и в случае с префиксным кодом, представление строки в виде конкатенации таких слов уникально. Код Bifix представляет собой набор слов , который является одновременно префикс и суффикс кода. Код оптимального префикса является префикс кодом с минимальной средней длиной. То есть, предположим , что алфавит п символов с вероятностями для префикса кода C . Если C ‘ — это другой префиксный код и длины кодовых слов C’ , то . п ( А я ) <\ displaystyle p (A_ )> λ я ′ <\ displaystyle \ lambda '_ <я>> ∑ я знак равно 1 п λ я п ( А я ) ≤ ∑ я знак равно 1 п λ я ′ п ( А я ) <\ displaystyle \ sum _ ^ <\ lambda _ p (A_ )> \ leq \ sum _ ^ <\ lambda '_ < i>p (A_ )> \!>

Коды префиксов, используемые сегодня

Примеры префиксных кодов включают:

Методы

Обычно используемые методы для построения префиксных кодов включают коды Хаффмана и более ранние коды Шеннона – Фано , а также универсальные коды, такие как:

Источник