Алгоритм Хаффмана — Викиконспекты

фПНУЛЙК РПМЙФЕИОЙЮЕУЛЙК ХОЙЧЕТУЙФЕФ
лБЖЕДТБ ЧЩЮЙУМЙФЕМШОПК ФЕИОЙЛЙ

лХТУ: фЕПТЙС ЙОЖПТНБГЙЙ
мБВПТБФПТОБС ТБВПФБ 1
"бМЗПТЙФН ЛПДЙТПЧБОЙС иБЖЖНЕОБ"
уПДЕТЦБОЙЕ | рПНПЭШ | фЕПТЙС | йОФЕТБЛФЙЧОПЕ ПВХЮЕОЙЕ | дПРХУЛ | чЩРПМОЕОЙЕ ТБВПФЩ


фЕПТЕФЙЮЕУЛБС ЮБУФШ



бМЗПТЙФН иБЖЖНЕОБ

пДЙО ЙЪ РЕТЧЩИ БМЗПТЙФНПЧ ЬЖЖЕЛФЙЧОПЗП ЛПДЙТПЧБОЙС ЙОЖПТНБГЙЙ ВЩМ РТЕДМПЦЕО иБЖЖНЕОПН Ч 1952 ЗПДХ. ьФПФ БМЗПТЙФН УФБМ ВБЪПК ДМС ВПМШЫПЗП ЛПМЙЮЕУФЧБ РТПЗТБНН УЦБФЙС ЙОЖПТНБГЙЙ. оБРТЙНЕТ, ЛПДЙТПЧБОЙЕ РП иБЖЖНЕОХ ЙУРПМШЪХЕФУС Ч РТПЗТБННБИ УЦБФЙС ARJ, ZIP, RAR, Ч БМЗПТЙФНЕ УЦБФЙС ЗТБЖЙЮЕУЛЙИ ЙЪПВТБЦЕОЙК У РПФЕТСНЙ JPEG, Б ФБЛЦЕ ЧУФТПЕОП Ч УПЧТЕНЕООЩЕ ЖБЛУ-БРРБТБФЩ.

ьЖЖЕЛФЙЧОПЕ ЛПДЙТПЧБОЙЕ РП иБЖЖНЕОХ УПУФПЙФ Ч РТЕДУФБЧМЕОЙЙ ОБЙВПМЕЕ ЧЕТПСФОЩИ (ЮБУФП ЧУФТЕЮБАЭЙИУС) ВХЛЧ ДЧПЙЮОЩНЙ ЛПДБНЙ ОБЙНЕОШЫЕК ДМЙОЩ, Б НЕОЕЕ ЧЕТПСФОЩИ — ЛПДБНЙ ВПМШЫЕК ДМЙОЩ (ЕУМЙ ЧУЕ ЛПДПЧЩЕ УМПЧБ НЕОШЫЕК ДМЙОЩ ХЦЕ ЙУЮЕТРБОЩ). ьФП ДЕМБЕФУС ФБЛЙН ПВТБЪПН, ЮФПВЩ УТЕДОСС ДМЙОБ ЛПДБ ОБ ВХЛЧХ ЙУИПДОПЗП УППВЭЕОЙС ВЩМБ НЙОЙНБМШОПК.

дП ОБЮБМБ ЛПДЙТПЧБОЙС ДПМЦОЩ ВЩФШ ЙЪЧЕУФОЩ ЧЕТПСФОПУФЙ РПСЧМЕОЙС ЛБЦДПК ВХЛЧЩ, ЙЪ ЛПФПТЩИ ВХДЕФ УПУФПСФШ УППВЭЕОЙЕ. оБ ПУОПЧБОЙЙ ЬФПК ФБВМЙГЩ ЧЕТПСФОПУФЕК УФТПЙФУС ЛПДПЧПЕ ДЕТЕЧП иБЖЖНЕОБ, У РПНПЭША ЛПФПТПЗП РТПЙЪЧПДЙФУС ЛПДЙТПЧБОЙЕ ВХЛЧ.

рПУФТПЕОЙЕ ЛПДПЧПЗП ДЕТЕЧБ иБЖЖНЕОБ

дМС ЙММАУФТБГЙЙ БМЗПТЙФНБ иБЖЖНЕОБ ТБУУНПФТЙН ЗТБЖЙЮЕУЛЙК УРПУПВ РПУФТПЕОЙС ДЕТЕЧБ ЛПДЙТПЧБОЙС. рЕТЕД ЬФЙН ЧЧЕДЕН ОЕЛПФПТЩЕ ПРТЕДЕМЕОЙС, РТЙОСФЩЕ ДМС ПРЙУБОЙС БМЗПТЙФНБ иБЖЖНЕОБ У ЙУРПМШЪПЧБОЙЕН ЬФПЗП УРПУПВБ.

зТБЖ — УПЧПЛХРОПУФШ НОПЦЕУФЧБ ХЪМПЧ Й НОПЦЕУФЧБ ДХЗ, ОБРТБЧМЕООЩИ ПФ ПДОПЗП ХЪМБ Л ДТХЗПНХ.

дЕТЕЧП — ЗТБЖ, ПВМБДБАЭЙК УМЕДХАЭЙНЙ УЧПКУФЧБНЙ:

  • ОЙ Ч ПДЙО ЙЪ ХЪМПЧ ОЕ ЧИПДЙФ ВПМЕЕ ПДОПК ДХЗЙ;
  • ФПМШЛП Ч ПДЙО ХЪЕМ ОЕ ЧИПДЙФ ОЙ ПДОПК ДХЗЙ (ЬФПФ ХЪЕМ ОБЪЩЧБЕФУС ЛПТОЕН ДЕТЕЧБ);
  • РЕТЕНЕЭБСУШ РП ДХЗБН ПФ ЛПТОС, НПЦОП РПРБУФШ Ч МАВПК ХЪЕМ.

мЙУФ ДЕТЕЧБ — ХЪЕМ, ЙЪ ЛПФПТПЗП ОЕ ЧЩИПДЙФ ОЙ ПДОПК ДХЗЙ. ч РБТЕ ХЪМПЧ ДЕТЕЧБ, УПЕДЙОЕООЩИ НЕЦДХ УПВПК ДХЗПК, ФПФ, ЙЪ ЛПФПТПЗП ПОБ ЧЩИПДЙФ, ОБЪЩЧБЕФУС ТПДЙФЕМЕН, ДТХЗПК ЦЕ — ТЕВЕОЛПН.

дЧБ ХЪМБ ОБЪЩЧБАФУС ВТБФШСНЙ, ЕУМЙ ЙНЕАФ ПДОПЗП Й ФПЗП ЦЕ ТПДЙФЕМС.

дЧПЙЮОПЕ ДЕТЕЧП — ДЕТЕЧП, Х ЛПФПТПЗП ЙЪ ЧУЕИ ХЪМПЧ, ЛТПНЕ МЙУФШЕЧ, ЧЩИПДЙФ ТПЧОП РП ДЧЕ ДХЗЙ.

дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ — ДЧПЙЮОПЕ ДЕТЕЧП, Х ЛПФПТПЗП ЛБЦДЩК ХЪЕМ ЙНЕЕФ ЧЕУ, Й РТЙ ЬФПН ЧЕУ ТПДЙФЕМС ТБЧЕО УХННБТОПНХ ЧЕУХ ЕЗП ДЕФЕК.

бМЗПТЙФН РПУФТПЕОЙС ДЕТЕЧБ ЛПДЙТПЧБОЙС иБЖЖНЕОБ ФБЛПЧ:

  1. вХЛЧЩ ЧИПДОПЗП БМЖБЧЙФБ ПВТБЪХАФ УРЙУПЛ УЧПВПДОЩИ ХЪМПЧ ВХДХЭЕЗП ДЕТЕЧБ ЛПДЙТПЧБОЙС. лБЦДЩК ХЪЕМ Ч ЬФПН УРЙУЛЕ ЙНЕЕФ ЧЕУ, ТБЧОЩК ЧЕТПСФОПУФЙ РПСЧМЕОЙС УППФЧЕФУФЧХАЭЕК ВХЛЧЩ Ч УППВЭЕОЙЙ.
  2. чЩВЙТБАФУС ДЧБ УЧПВПДОЩИ ХЪМБ ДЕТЕЧБ У ОБЙНЕОШЫЙНЙ ЧЕУБНЙ. еУМЙ ЙНЕЕФУС ВПМЕЕ ДЧХИ УЧПВПДОЩИ ХЪМПЧ У ОБЙНЕОШЫЙНЙ ЧЕУБНЙ, ФП НПЦОП ВТБФШ МАВХА РБТХ.
  3. уПЪДБЕФУС ЙИ ТПДЙФЕМШ У ЧЕУПН, ТБЧОЩН ЙИ УХННБТОПНХ ЧЕУХ.
  4. тПДЙФЕМШ ДПВБЧМСЕФУС Ч УРЙУПЛ УЧПВПДОЩИ ХЪМПЧ, Б ДЧПЕ ЕЗП ДЕФЕК ХДБМСАФУС ЙЪ ЬФПЗП УРЙУЛБ.
  5. пДОПК ДХЗЕ, ЧЩИПДСЭЕК ЙЪ ХЪМБ-ТПДЙФЕМС, УФБЧЙФУС Ч УППФЧЕФУФЧЙЕ ВЙФ 1, ДТХЗПК — 0.
  6. рХОЛФЩ 2, 3, 4, 5 РПЧФПТСАФУС ДП ФЕИ РПТ, РПЛБ Ч УРЙУЛЕ УЧПВПДОЩИ ХЪМПЧ ОЕ ПУФБОЕФУС ФПМШЛП ПДЙО ХЪЕМ. ьФПФ ХЪЕМ ВХДЕФ СЧМСФШУС ЛПТОЕН ДЕТЕЧБ. еЗП ЧЕУ РПМХЮБЕФУС ТБЧОЩН ЕДЙОЙГЕ — УХННБТОПК ЧЕТПСФОПУФЙ ЧУЕИ ВХЛЧ УППВЭЕОЙС.

фЕРЕТШ, ДЧЙЗБСУШ РП ЛПДПЧПНХ ДЕТЕЧХ УЧЕТИХ ЧОЙЪ Й РПУМЕДПЧБФЕМШОП ЧЩРЙУЩЧБС ДЧПЙЮОЩЕ ГЙЖТЩ, УППФЧЕФУФЧХАЭЙЕ ДХЗБН, НПЦОП РПМХЮЙФШ ЛПДЩ ВХЛЧ ЧИПДОПЗП БМЖБЧЙФБ.

дМС РТЙНЕТБ ТБУУНПФТЙН РПУФТПЕОЙЕ ДЕТЕЧБ ЛПДЙТПЧБОЙС иБЖЖНЕОБ ДМС РТЙЧЕДЕООПЗП Ч ФБВМЙГЕ 1 БМЖБЧЙФБ ЙЪ ЧПУШНЙ ВХЛЧ.

фБВМЙГБ 1
вХЛЧБ z1 z2 z3 z4 z5 z6 z7 z8
чЕТПСФОПУФШ 0.22 0.20 0.16 0.16 0.10 0.10 0.04 0.02

рПУФТПЕОЙЕ ДЕТЕЧБ ОБЮЙОБЕН УП УРЙУЛБ МЙУФШЕЧ (УН. ТЙУ. 1) Й ЧЩРПМОСЕН РП ЫБЗБН.


тЙУ. 1. уРЙУПЛ УЧПВПДОЩИ ХЪМПЧ-МЙУФШЕЧ.

оБ РЕТЧПН ЫБЗЕ ЙЪ МЙУФШЕЧ ДЕТЕЧБ ЧЩВЙТБАФУС ДЧБ У ОБЙНЕОШЫЙНЙ ЧЕУБНЙ z7 Й z8. пОЙ РТЙУПЕДЙОСАФУС Л ХЪМХ-ТПДЙФЕМА, ЧЕУ ЛПФПТПЗП ХУФБОБЧМЙЧБЕФУС Ч 0.04+0.02=0.06. ъБФЕН ХЪМЩ z7 Й z8 ХДБМСАФУС ЙЪ УРЙУЛБ УЧПВПДОЩИ. хЪЕМ z7 УППФЧЕФУФЧХЕФ ЧЕФЧЙ 0 ТПДЙФЕМС, ХЪЕМ z8 — ЧЕФЧЙ 1. дЕТЕЧП ЛПДЙТПЧБОЙС РПУМЕ РЕТЧПЗП ЫБЗБ РТЙЧЕДЕОП ОБ ТЙУ. 2.


тЙУ. 2. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ РЕТЧПЗП ЫБЗБ.

оБ ЧФПТПН ЫБЗЕ "ОБЙМЕЗЮБКЫЕК" РБТПК ПЛБЪЩЧБЕФУС МЙУФ z6 Й УЧПВПДОЩК ХЪЕМ (z7+z8). дМС ОЙИ УПЪДБЕФУС ТПДЙФЕМШ У ЧЕУПН 0.16. хЪЕМ z6 УППФЧЕФУФЧХЕФ ЧЕФЧЙ 0 ТПДЙФЕМС, ХЪЕМ (z7+z8) — ЧЕФЧЙ 1. оБ ДБООПН ЫБЗЕ ДЕТЕЧП ЛПДЙТПЧБОЙС ЧЩЗМСДЙФ УМЕДХАЭЙН ПВТБЪПН (УН. ТЙУ. 3).


тЙУ. 3. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ ЧФПТПЗП ЫБЗБ.

оБ ФТЕФШЕН ЫБЗЕ ОБЙНЕОШЫЙЕ ЧЕТПСФОПУФЙ ЙНЕАФ z5, z4, z3 Й УЧПВПДОЩК ХЪЕМ (z6+z7+z8). фБЛЙН ПВТБЪПН, ОБ ДБООПН ЫБЗЕ НПЦОП УПЪДБФШ ТПДЙФЕМС ДМС z5 Й (z6+z7+z8) У ЧЕУПН 0.26, РПМХЮЙЧ РТЙ ЬФПН ДЕТЕЧП ЛПДЙТПЧБОЙС, РТЕДУФБЧМЕООПЕ ОБ ТЙУ. 4. пВТБФЙФЕ ЧОЙНБОЙЕ, ЮФП Ч ДБООПК УЙФХБГЙЙ ЧПЪНПЦОЩ ОЕУЛПМШЛП ЧБТЙБОФПЧ УПЕДЙОЕОЙС ХЪМПЧ У ОБЙНЕОШЫЙНЙ ЧЕУБНЙ. рТЙ ЬФПН ЧУЕ ФБЛЙЕ ЧБТЙБОФЩ ВХДХФ РТБЧЙМШОЩНЙ, ИПФС Й НПЗХФ РТЙЧЕУФЙ Л ТБЪМЙЮОЩН ОБВПТБН ЛПДПЧ, ЛПФПТЩЕ, ЧРТПЮЕН, ВХДХФ ПВМБДБФШ ПДЙОБЛПЧПК ЬЖЖЕЛФЙЧОПУФША ДМС ЪБДБООПЗП ТБУРТЕДЕМЕОЙС ЧЕТПСФОПУФЕК.


тЙУ. 4. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ ФТЕФШЕЗП ЫБЗБ.

оБ ЮЕФЧЕТФПН ЫБЗЕ "ОБЙМЕЗЮБКЫЕК" РБТПК ПЛБЪЩЧБАФУС МЙУФШС z3 Й z4. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РТЙЧЕДЕОП ОБ ТЙУ. 5.


тЙУ. 5. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ ЮЕФЧЕТФПЗП ЫБЗБ.

оБ РСФПН ЫБЗЕ ЧЩВЙТБЕН ХЪМЩ У ОБЙНЕОШЫЙНЙ ЧЕУБНЙ 0.22 Й 0.20. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ РСФПЗП ЫБЗБ РТЙЧЕДЕОП ОБ ТЙУ. 6.


тЙУ. 6. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ РСФПЗП ЫБЗБ.

оБ ЫЕУФПН ЫБЗЕ ПУФБЕФУС ФТЙ УЧПВПДОЩИ ХЪМБ У ЧЕУБНЙ 0.42, 0.32 Й 0.26. чЩВЙТБЕН ОБЙНЕОШЫЙЕ ЧЕУБ 0.32 Й 0.26. дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ ЫЕУФПЗП ЫБЗБ РТЙЧЕДЕОП ОБ ТЙУ. 7.


тЙУ. 7.

дЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ РПУМЕ ЫЕУФПЗП ЫБЗБ.

оБ УЕДШНПН ЫБЗЕ ПУФБЕФУС ПВЯЕДЙОЙФШ ДЧЕ ПУФБЧЫЙЕУС УЧПВПДОЩЕ ЧЕТЫЙОЩ, РПУМЕ ЮЕЗП РПМХЮБЕН ПЛПОЮБФЕМШОПЕ ДЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ, РТЙЧЕДЕООПЕ ОБ ТЙУ. 8.


тЙУ. 8. пЛПОЮБФЕМШОПЕ ДЕТЕЧП ЛПДЙТПЧБОЙС иБЖЖНЕОБ.

оБ ПУОПЧБОЙЙ РПУФТПЕООПЗП ДЕТЕЧБ ВХЛЧЩ РТЕДУФБЧМСАФУС ЛПДБНЙ, ПФТБЦБАЭЙНЙ РХФШ ПФ ЛПТОЕЧПЗП ХЪМБ ДП МЙУФБ, УППФЧЕФУФЧХАЭЕЗП ОХЦОПК ВХЛЧЕ. ч ТБУУНПФТЕООПН РТЙНЕТЕ ВХЛЧЩ ЧИПДОПЗП БМЖБЧЙФБ ЛПДЙТХАФУС ФБЛ, ЛБЛ РПЛБЪБОП Ч ФБВМЙГЕ 2.

фБВМЙГБ 2
вХЛЧБ z1 z2 z3 z4 z5 z6 z7 z8
лПД 10 11 000 001 011 0100 01010 01011

чЙДОП, ЮФП ОБЙВПМЕЕ ЧЕТПСФОЩЕ ВХЛЧЩ ЪБЛПДЙТПЧБОЩ УБНЩНЙ ЛПТПФЛЙНЙ ЛПДБНЙ, Б ОБЙВПМЕЕ ТЕДЛЙЕ — ЛПДБНЙ ВПМШЫЕК ДМЙОЩ. рТЙЮЕН ЛПДЩ РПУФТПЕОЩ ФБЛЙН ПВТБЪПН, ЮФП ОЙ ПДОБ ЛПДПЧБС ЛПНВЙОБГЙС ОЕ УПЧРБДБЕФ У ОБЮБМПН ВПМЕЕ ДМЙООПК ЛПНВЙОБГЙЙ. ьФП РПЪЧПМСЕФ ПДОПЪОБЮОП ДЕЛПДЙТПЧБФШ УППВЭЕОЙС ВЕЪ ЙУРПМШЪПЧБОЙС ТБЪДЕМЙФЕМШОЩИ УЙНЧПМПЧ.

дМС ЪБДБООЩИ Ч ФБВМЙГЕ 1 ЧЕТПСФОПУФЕК НПЦОП РПУФТПЙФШ Й ДТХЗЙЕ РТБЧЙМШОЩЕ ЧБТЙБОФЩ ЛПДПЧПЗП ДЕТЕЧБ иБЖЖНЕОБ. пДОП ЙЪ ДПРХУФЙНЩИ ДЕТЕЧШЕЧ РТЙЧЕДЕОП ОБ ТЙУ. 9. лПДЩ ВХЛЧ ЧИПДОПЗП БМЖБЧЙФБ ДМС ДБООПЗП ЛПДПЧПЗП ДЕТЕЧБ РТЙЧЕДЕОЩ Ч ФБВМЙГЕ 3.


тЙУ. 9. бМШФЕТОБФЙЧОЩК ЧБТЙБОФ ДЕТЕЧБ ЛПДЙТПЧБОЙС иБЖЖНЕОБ.

фБВМЙГБ 3
вХЛЧБ z1 z2 z3 z4 z5 z6 z7 z8
лПД 11 10 011 001 000 0101 01001 01000

йЪ ФБВМЙГЩ 3 ЧЙДОП, ЮФП ЛПДЩ ФБЛЦЕ РПМХЮЙМЙУШ РТЕЖЙЛУОЩНЙ, Й ОБЙВПМЕЕ ЧЕТПСФОЩН ВХЛЧБН УППФЧЕФУФЧХАФ ОБЙВПМЕЕ ЛПТПФЛЙЕ ЛПДЩ.

чПРТПУЩ РТБЛФЙЮЕУЛПК ТЕБМЙЪБГЙЙ БМЗПТЙФНБ

дМС РПЧЩЫЕОЙС ЬЖЖЕЛФЙЧОПУФЙ УЦБФЙС ОЕПВИПДЙНП, ЮФПВЩ РТЙ РПУФТПЕОЙЙ ЛПДПЧПЗП ДЕТЕЧБ ЙУРПМШЪПЧБМЙУШ ДБООЩЕ РП ЧЕТПСФОПУФСН РПСЧМЕОЙС ВХЛЧ ЙНЕООП Ч ЬФПН ЖБКМЕ, Б ОЕ ХУТЕДОЕООЩЕ РП ВПМШЫПНХ ЛПМЙЮЕУФЧХ ФЕЛУФПЧ. йУИПДС ЙЪ ЬФПЗП, ОЕПВИПДЙНБ УФБФЙУФЙЛБ ЧУФТЕЮБЕНПУФЙ ВХЛЧ УЦЙНБЕНПЗП ЖБКМБ, ЛПФПТБС НПЦЕФ ВЩФШ РПМХЮЕОБ РТЕДЧБТЙФЕМШОЩН РТПИПДПН РП ЖБКМХ.

дМС ХУЛПТЕОЙС ТБВПФЩ РТЙОСФП ПРТЕДЕМСФШ ОЕ ЧЕТПСФОПУФЙ РПСЧМЕОЙС ВХЛЧ pi, Б ЮБУФПФХ ЧУФТЕЮБЕНПУФЙ (ЛПМЙЮЕУФЧП РПСЧМЕОЙК) ВХЛЧЩ Ч ЖБКМЕ ni. ьФП РПЪЧПМСЕФ УХЭЕУФЧЕООП ХРТПУФЙФШ Й ХУЛПТЙФШ БМЗПТЙФН (ОЕ ОХЦОП НЕДМЕООЩИ ПРЕТБГЙК У РМБЧБАЭЕК ЪБРСФПК Й ПРЕТБГЙК ДЕМЕОЙС). рТЙ ФБЛПН РПДИПДЕ БМЗПТЙФН ТБВПФЩ ОЕ ЙЪНЕОСЕФУС, ФБЛ ЛБЛ ЮБУФПФЩ РТСНП РТПРПТГЙПОБМШОЩ ЧЕТПСФОПУФСН. уФПЙФ ЪБНЕФЙФШ, ЮФП ЧЕУ ЛПТОЕЧПЗП ХЪМБ ДЕТЕЧБ ЛПДЙТПЧБОЙС Ч ФБЛПН УМХЮБЕ ВХДЕФ ТБЧЕО ПВЭЕНХ ЛПМЙЮЕУФЧХ ВХЛЧ Ч ПВТБВБФЩЧБЕНПН ЖБКМЕ.


йОФЕТБЛФЙЧОПЕ ПВХЮЕОЙЕ


рПУМЕ ФПЗП, ЛБЛ ЧЩ ПЪОБЛПНЙМЙУШ У ФЕПТЕФЙЮЕУЛПК ЮБУФША ТБВПФЩ, РТЕДМБЗБЕН ЧБН РПРТБЛФЙЛПЧБФШУС Ч РПУФТПЕОЙЙ ЛПДПЧЩИ ДЕТЕЧШЕЧ иБЖЖНЕОБ У РПНПЭША ЙОФЕТБЛФЙЧОПК ПВХЮБАЭЕК УЙУФЕНЩ. дМС ЬФПЗП ДПУФБФПЮОП РЕТЕКФЙ РП ЬФПК УУЩМЛЕ.

Huffman — Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.

Сжимая файл по алгоритму Хаффмана первое что мы должны сделать — это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.

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

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :

|——————|——|——|——|——|——|——| | cимвол | A | B | C | D | E | F | |——————|——|——|——|——|——|——| | число вхождений | 10 | 20 | 30 | 5 | 25 | 10 | |——————|——|——|——|——|——|——|

Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу как ниже.

|——————|——|——|——|——|——|——| | cимвол | C | E | B | F | A | D | |——————|——|——|——|——|——|——| | число вхождений | 30 | 25 | 20 | 10 | 10 | 5 | |——————|——|——|——|——|——|——|

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из «узлов» D и A новый «узел», частота вхождения для которого будет равна сумме частот D и A :

Частота 30 10 5 10 20 25 Символа C A D F B E | | |—|—| ||-| |15| = 5 + 10 |—|

Номер в рамке — сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый «узел» с суммарной частотой вхождения.

Самая низкая частота теперь у F и нового «узла». Снова сделаем операцию слияния узлов :

Частота 30 10 5 10 20 25 Символа C A D F B E | | | | | | | |—|| | |-|15|| | ||-| | | | | |—| | |—-|25|-| = 10 + 15 |—|

Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все «дерево» не сформировано, т.е. пока все не сведется к одному узлу.

Частота 30 10 5 10 20 25 Символа C A D F B E | | | | | | | | | | | | | | |—|| | | | | |-|15|| | | | | ||-| | | | | | | | | | | |—| | | |—| | | |—-|25|-| |-|45|-| | ||-| ||-| | |—| | | |—-|55|——| | |-|| | | |————| | |—| Root (100) |—-| |————|

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всенда начнинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C — 00. Для следующего символа ( А ) у нас получается — лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим

C = 00 ( 2 бита ) A = 0100 ( 4 бита ) D = 0101 ( 4 бита ) F = 011 ( 3 бита ) B = 10 ( 2 бита ) E = 11 ( 2 бита )

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

|———-|—————-|——————-|—————| | Частота | первоначально | уплотненные биты | уменьшено на | |———-|—————-|——————-|—————| | C 30 | 30 x 8 = 240 | 30 x 2 = 60 | 180 | | A 10 | 10 x 8 = 80 | 10 x 3 = 30 | 50 | | D 5 | 5 x 8 = 40 | 5 x 4 = 20 | 20 | | F 10 | 10 x 8 = 80 | 10 x 4 = 40 | 40 | | B 20 | 20 x 8 = 160 | 20 x 2 = 40 | 120 | | E 25 | 25 x 8 = 200 | 25 x 2 = 50 | 150 | |———-|—————-|——————-|—————| Первоначальный размер файла : 100 байт — 800 бит; Размер сжатого файла : 30 байт — 240 бит; 240 — 30% из 800 , так что мы сжали этот файл на 70%.

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

В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.

Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11. 4 байта 11 раз — 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику — наша таблица будет приблизительно 50 байтов длинны.

Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт — мы получили 20% сжатие информации.

Не плохо. То что мы действительно выполнили — трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным.

Что мы можем получить на этом пути ?

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

Мы получим что можно иметь только : 4 — 2 разрядных кода; 8 — 3 разрядных кодов; 16 — 4 разрядных кодов; 32 — 5 разрядных кодов; 64 — 6 разрядных кодов; 128 — 7 разрядных кодов; Необходимо еще два 8 разрядных кода. 4 — 2 разрядных кода; 8 — 3 разрядных кодов; 16 — 4 разрядных кодов; 32 — 5 разрядных кодов; 64 — 6 разрядных кодов; 128 — 7 разрядных кодов; ——— 254

Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт. Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта.

Все эти подсчеты производились для не префиксных кодов Хаффмана т.е. кодов, которые нельзя идентифицировать однозначно. Например код A — 01011 и код B — 0101. Если мы будем получать эти коды побитно, то получив биты 0101 мы не сможем сказать какой код мы получили A или B , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.

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

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

А здесь — реализация на Паскалe.

.

Обзор алгоритмов сжатия без потерь

Метод Хаффмана

Адаптивное сжатие Хаффмана

Следующим шагом в развитии алгоритма Хаффмана стала его адаптивная версия. Адаптивное сжатие Хаффмана позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании. Практически любая форма кодирования может быть конвертирована в адаптивную. В общем случае программа, реализующая адаптивное сжатие, может быть выражена в следующей форме:

ИнициализироватьМодель();Пока не конец сообщения Символ = ВзятьСледующийСимвол(); Закодировать(Символ); ОбновитьМодельСимволом(Символ);Конец пока;

Декодер в адаптивной схеме работает аналогичным образом:

ИнициализироватьМодель();Пока не конец сжатой информации Символ = РаскодироватьСледующий(); ВыдатьСимвол(Символ); ОбновитьМодельСимволом(Символ);Конец пока;

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

Адаптивное кодирование Хаффмана

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

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

Упорядоченное Дерево
Будем говорить, что дерево обладает свойством упорядоченности, если его узлы могут быть перечислены в порядке возрастания веса и в этом перечислении каждый узел находится рядом со своим братом. Пример упорядоченного дерева приведен на рисунке:

Здесь W – вес узла, N – порядковый номер в списке узлов.

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

Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу.

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

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

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

При этом родители каждого из узлов тоже изменяются. На этом операция перестановки заканчивается. После перестановки операция увеличения веса узлов продолжается дальше.

Следующий узел, вес которого будет увеличен алгоритмом, – это новый родитель узла, увеличение веса которого вызвало перестановку. Предположим, что символ A встретился в сообщении еще два раза подряд. Дерево кодирования после двукратного вызова процедуры обновления показано на рисунке:

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

Алгоритм обновления дереваОбновитьМодельСимволом(Символ){ ТекущийУзел = ЛистСоответствующий(Символ); Всегда УвеличитьВес(ТекущийУзел); Если ТекущийУзел = КореньДерева Выход; Если Вес(ТекущийУзел) > Вес(СледующийЗа(ТекущийУзел)) Перестановка(); ТекущийУзел = Родитель(ТекущийУзел); Конец Всегда;}

Проблемы адаптивного кодирования

Хорошо было бы, чтобы кодер не тратил зря кодовое пространство на символы, которые не встречаются в сообщении. Если речь идет о классическом алгоритме Хаффмана, то те символы, которые не встречаются в сообщении, уже известны до начала кодирования, так как известна таблица частот и символы, у которых частота встречаемости равна 0. В адаптивной версии алгоритма мы не можем знать заранее, какие символы появятся в сообщении. Можно проинициализировать дерево Хаффмана так, чтобы оно имело все 256 символов алфавита (для 8-и битовых кодов) с частотой, равной 1. В начале кодирования каждый код будет иметь длину 8 битов. По мере адаптации модели наиболее часто встречающиеся символы будут кодироваться все меньшим и меньшим количеством битов. Такой подход работоспособен, но он значительно снижает степень сжатия, особенно на коротких сообщениях.

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

Чтобы разрешить это противоречие, введем специальный код, который будет означать, что следующий символ закодирован вне контекста модели сообщения. Например, его можно передать в поток сжатой информации как есть, не кодируя вообще. Метод в алгоритме адаптивного кодирования Хаффмана можно записать следующим образом:

ЗакодироватьСимвол(Символ){ Если СимволУжеЕстьВТаблице(Символ) ВыдатьКодХаффманаДля(Символ); Иначе { ВыдатьКодХаффманаДля(ESC); ВыдатьСимвол(Символ); }}

Использование специального символа подразумевает определенную инициализацию дерева до начала кодирования и декодирования: в него помещаются 2 специальных символа: и (конец файла), с весом, равным 1.

Поскольку процесс обновления не коснется их веса, то по ходу кодирования они будут перемещаться на самые удаленные ветви дерева и иметь самые длинные коды.

Добавить комментарий

Закрыть меню