Префиксные коды и их генерация.

Генерация префиксных кодов.

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

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

Условие Фано (англ. Fano condition, в честь Роберта Фано) — в теории кодирования — достаточное условие построения самотерминирующегося кода (в другой терминологии, префиксного кода). Обычная формулировка этого условия выглядит так: Никакое кодовое слово не может быть началом другого кодового слова. (Википедия).

Для создания двоичных префиксных кодов  создана следующая программа (среда PascalABC):

Program coder;

type

  st= string[10];

const

  n = 1000;

var

  i,j: integer;

  m0, m: integer;

  a: array [1..1000,1..2] of st;

  x,y: integer;

Begin

  m0:=2;

  for i := 3 to n do

    a[i,2] := '0';

  a[1,1] := '0';

  a[2,1] := '1';

  a[1,2] := '1';

  a[2,2] := '1';

  writeln ('Введите количество кодовых слов m = ');

  readln (m);

  x := 1;

  y := 3;

  while m0 < m do

    begin

      a[x,2] := '0'; dec(m0);

      a[y,2] := '1'; a[y,1] := a[x,1]+'0'; inc(m0); inc(y);

      a[y,2] := '1'; a[y,1] := a[x,1]+'1'; inc(m0); inc(y);

      inc(x);

   end;

  writeln;

  writeln('Префиксные коды:');

  for i := 1 to y do

    if a[i,2]='1' then writeln (a[i,1]);

end.

Краткое описание документа:

Материал (программа на языке Паскаль) создан в дополнение к §6. Кодирование для изучения процесса формирования двоичных префиксных кодов.

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