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

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

Пре́фиксный код в теории кодирования — код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово 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

Определение

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

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

Примеры

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

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

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

См. также



Wikimedia Foundation. 2010.

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

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

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

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

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

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

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

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

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

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

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


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»