{

  ╥шя√ фрээ√ї фы  ЁхрышчрЎшш └─└╧╥╚┬═╬├╬ ьхЄюфр ёцрЄш  ╒рЇьрэр 

  Типы данных для реализации АДАПТИВНОГО метода сжатия Хафмана }
{---------------------------------------------------------------------------
(c) Copyright	 Aleksandrov O.E., 2005

   Molecular Physics department, USTU, Ekaterinsburg, K-2, 620002, RUSSIA
   phone 375-41-46
   E-mail: aleks@dpt.ustu.ru

(c) Copyright Александров О.Е., 2005

   620002, Екатеринбург, К-2, УГТУ, Кафедра молекулярной физики
   тел. 375-41-46
   E-mail: aleks@dpt.ustu.ru
----------------------------------------------------------------------------}
Unit DHufType;

INTERFACE
  USES HufTypes;

const
  cMin_MaxTotalCounter=cBaseNodeCount+1024;{ значение по-умолчанию для частоты сброса счетчиков }
  cRootNode=cMaxNodeCount-1;
  cRootNode_UpperNode=(cRootNode div 2)-1;

type

{ ╥шя√ фрээ√ї фы  їЁрэхэш  └─└╧╥╚┬═╬├╬ фхЁхтр }
{ Типы данных для хранения АДАПТИВНОГО дерева }

  { ═юьхЁ ўхЄэюую єчыр т фхЁхтх ╒рЇЇьрэр }
  { Номер четного узла в дереве Хаффмана }
  tHalfIndex=Low(tIndex)..(High(tIndex) div 2);
  tHalfIndexEx=Low(tHalfIndex)..High(tHalfIndex)+cBaseNodeCount;
  { ёё√ыъш эр ёыхфє∙шщ єчхы фхЁхтр }
  { ссылки на следущий узел дерева }
  tNextNodes=packed array[tHalfIndex] of tIndex;
  tNextNodesEx=packed array[tHalfIndexEx] of tIndex;
  tHalfCounter=cMin_MaxTotalCounter..High(tFriquency);

  { счетчик в 64 бита }
  tVeryLongCounter=
  {$IfDef Delphi}
     int64
  {$Else}
     packed array[0..3] of word
  {$EndIf Def Delphi};
  tBitOfByteCounter=0..7;
  tVeryLongCounterWordsNumber=0..((SizeOF(tVeryLongCounter) div 2)-1);

  { ёўхЄўшъ фы  сшЄ } { счетчик для бит }
  tVeryLongBitCounter=record
    { 3-ї сшЄэ√щ ёўхЄўшъ фы  сшЄ 0..7 }
    { 3-х битный счетчик для бит 0..7 }
    BitCount:tBitOfByteCounter;
    { 64 сшЄэ√щ срщЄют√щ ёўхЄўшъ }
    { 64 битный байтовый счетчик }
    ByteCount:tVeryLongCounter;
  end;

  { ─рээ√х єчыр фшэрьшўхёъюую фхЁхтр ╒рЇЇьрэр }
  { Данные узла динамического дерева Хаффмана }
  tNodeData=packed record
    { ёўхЄўшъ єчыр }
    { счетчик узла }
    Counter:tFriquency;
    { ёё√ыър эр яЁхф√фє∙шх єчы√ (i ш i+1), юс·хфшэхэшхь ъюЄюЁ√ї яюыєўхэ ¤ЄюЄ єчхы.
     ╤ё√ыър шфхЄ эр ўхЄэ√щ єчхы ш = (i div 2).
       ─ы  срчют√ї єчыют ёё√ыър шфхЄ эр ¤ыхьхэЄ ьрёёштр NextNode[b+256], уфх b -
      чэрўхэшх срщЄр, ўЄю ¤ътштры. ёё√ыъх эр NodeRef[b] }
    { ссылка на предыдущие узлы (i и i+1), объединением которых получен этот узел. Ссылка идет на четный узел и = (i div 2); }
    UpperNode:tHalfIndexEx;
    {$IfDef Delphi }Filler:word;{$EndIf Delphi}
  end;

  { Массив узлов динамического дерева Хаффмана - для хранения дерева}
  tNodesData=packed array[tIndex] of tNodeData;
  { ╠рёёшт срчют√ї єчыют фшэрьшўхёъюую фхЁхтр ╒рЇЇьрэр, ъЁюьх фтєї яхЁт√ї срчют√ї єчыют - фы  яхЁхёЄЁюхэш  фхЁхтр }
  { Массив базовых узлов динамического дерева Хаффмана, кроме двух первых базовых узлов - для перестроения дерева }
  tBaseNodesDataEx=packed array[2..cBaseNodeCount] of tNodeData;

  { ╠рёёшт ёё√ыюъ эр срчют√х єчы√ фшэрьшўхёъюую фхЁхтр ╒рЇЇьрэр т ьрёёштх єчыют фхЁхтр }
  { Массив ссылок на базовые узлы динамического дерева Хаффмана в массиве узлов дерева }
  tByteRef=packed array[tBaseNodeIndex] of tIndex;

  { ёё√ыюўэ√х фрээ√х фхЁхтр }
  tReferencies=packed record
    case byte of
      { ╬с·хфшэхээ√щ ьрёёшт ёё√ыюъ }
    0:(NextNode:tNextNodesEx);

    1:(
      { ёё√ыър эр єчхы, ъюЄюЁ√щ юсЁрчєхЄё  шч єчыр i ш i+1.
       ╟ряшё√трхЄё  ╬─═└ ёё√ыър фы  фтєї єчыют i ш i+1:
       ёыхфє■∙шщ_єчхы(i шыш i+1)=NextNode[i shr 1]=NextNode[(i+1) shr 1]}
      { ссылка на узел, который образуется из узла i и i+1.
       Записывается ОДНА ссылка для двух узлов i и i+1:
       следующий_узел(i или i+1)=NextNode[i shr 1]=NextNode[(i+1) shr 1]}
        NextNode0:tNextNodes;
       { ёё√ыър фы  срчют√ї єчыют [0..255] эр ¤ыхьхэЄ Nodes }
       { ссылка для базовых узлов [0..255] на элемент Nodes }
        Byte: tByteRef
    );
  end;

  { ╧юыэ√щ эрсюЁ фрээ√ї фшэрьшўхёъюую фхЁхтр ╒рЇЇьрэр }
  { Полный набор данных динамического дерева Хаффмана }
  tDynHuffmanFullTreeData=record
    { фрээ√х єчыют (╤ўхЄўшъ, ╤ё√ыър эр яЁхф. ) }
    { данные узлов (Счетчик, Ссылка на пред. ) }
    Nodes:tNodesData;

    { ёё√ыъш єчыют }
    Refs:tReferencies;

    { юс∙р  ёєььр ёўхЄўшъют фы  ъюэЄЁюы  ёсЁюёр }
    { общая сумма счетчиков для контроля сброса }
    MaxTotalCounter:tFriquency;

    { ╚эЇюЁьрЎшюээ√х фрээ√х }
    { Информационные данные }
	{ ўшёыю ёсЁюёют ёўхЄўшъют } { число сбросов счетчиков }
    TotalHalfCounterCount:tVeryLongCounter;
	{ ўшёыю срщЄют т шёїюфэюь яюЄюъх (Їрщых)}
	{ число байтов в исходном потоке (файле)}
    TotalByteCount:tVeryLongCounter;
	{ ўшёыю сшЄют т єяръютрээюь яюЄюъх (Їрщых )}
	{ число битов в упакованном потоке (файле )}
    TotalBitCount:tVeryLongBitCounter;

  end;
{ ╥шя√ фрээ√ї фы  їЁрэхэш  └─└╧╥╚┬═╬├╬  фхЁхтр ---END---------------- }
{ Типы данных для хранения АДАПТИВНОГО  дерева ---END---------------- }

  tDecodingRecord=record
    CodeBits:tCodeMaxPortion;
    CodeBitCount:tCodeMaxPortionLength;
    Node:tNodeIndex;
  end;

  tCodeByteIndexEx=0..cMaxCodeLengthInBytes;
  tCodeByteIndexEx1=0..cMaxCodeLengthInBytes+1;
  tCodeBytesEx=packed array[tCodeByteIndexEx] of byte;
  tCodeBytesEx1=packed array[tCodeByteIndexEx1] of byte;

  tCodeDataEx=packed record
    case byte of
      0:(Bytes:tCodeBytesEx; AdditionalByte:byte); {последовательность байт кода}
      1:(AllBytes:tCodeBytesEx1); {последовательность байт кода}
  end;
  tPCodeDataEx=^tCodeDataEx;

  { Данные по двоичной кодировке }
  tCodeEx=packed record
     Code:tCodeDataEx;     { битовый код }
     Length:tCodeLength; { длина битового кода в битах}
  end;
 tPCodeEx=^tCodeEx;


{ Win Text

  ╘╬╨╠└╥ ─└══█╒ фы  фтюшўэюую фхЁхтр ─╚═└╠╚╫┼╤╩╬├╬ ьхЄюфр ╒рЇЇьрэр:

─тюшўэюх фхЁхтю ьхЄюфр ╒рЇЇьрэр (фрыхх фхЁхтю) ёюёЄюшЄ шч єчыют.
  ╠ръёшьры№эюх тючьюцэюх ўшёыю єчыют фхЁхтр Ёртэю єфтюхээющ фышэх ╧╬╦═╬╔
шёїюфэющ ЄрсышЎ√ ёшьтюыют ьшэєё 1. ─ы  срщЄр (0..255 - тёхую 256 Ёрчышўэ√ї
чэрўхэшщ) ьръёшьры№эюх ўшёыю єчыют фхЁхтр Ёртэю 2*256-1 = 511 єчыют.

  ╞хырЄхы№эю ьръёшьры№эюх с√ёЄЁюфхщёЄтшх яЁш яхЁхёЄЁющъх фхЁхтр,
р яхЁхёЄЁющър т ─╚═└╠╚╫┼╤╩╬╠ ьхЄюфх ╒рЇЇьрэр яЁюшёїюфшЄ ърцф√щ Ёрч, ъръ эют√щ
срщЄ фрээ√ї яюёЄєярхЄ эр тїюф.

  ╥.ъ.ЁрчьхЁ ьръёшьры№эюую фхЁхтр эхтхышъ, Єю яЁюуЁрььр Ёрчьх∙рхЄ ёЄрЄшўхёъшщ
ьрёёшт фрээ√ї ьръёшьры№эюую ЁрчьхЁр. ▌ыхьхэЄ√ ьрёёштр шёяюы№чє■Єё  фы 
яюёЄЁюхэш  фхЁхтр.

  ─ы  фхъюфшЁютъш т ─╚═└╠╚╫┼╤╩╬╠ ьхЄюфх ╒рЇЇьрэр эх эєцэр шэЇюЁьрЎш  ю фхЁхтх
т ъюфшЁютрээ√ї фрээ√ї - фхЁхтю тюёёЄрэртыштрхЄё  фшэрьшўхёъш, яю ьхЁх фхъюфшЁютъш.

  ─ы  їЁрэхэш  ш яхЁхёЄЁюхэш  фхЁхтр шёяюы№чє■Єё  ёыхфє■∙шх фрээ√х

    Nodes:tNodesData; -  фрээ√х єчыют (═юьхЁ, ╤ўхЄўшъ, ╤ё√ыър эр яЁхф. ).
    NodeRef: tNodeRef; - ёё√ыър фы  срчют√ї єчыют Number in [0..255] эр ¤ыхьхэЄ Nodes.
    NextNode0:tNextNodes; - ёё√ыър эр эют√щ єчхы, ъюЄюЁ√щ юсЁрчєхЄё  шч фтєї єчыют i ш i+1,
		           уфх i - ўхЄэюх. ╟ряшё√трхЄё  ╬─═└ ёё√ыър фы  фтєї єчыют i ш i+1.
    MaxTotalCounter:tFriquency; - юс∙р  ёєььр ёўхЄўшъют фы  ъюэЄЁюы  ёсЁюёр.

╠рёёшт Nodes ёюёЄюшЄ шч чряшёхщ tNodeData
   Nodes
N:  0       1       2                                         510
  --------T-------T-------T------------     ----------------T---------м
  ж       ж       ж       ж                                 ж         ж
  L-------+-------+-------+------------      ---------------+----------

╩рцфр  чряшё№ ьрёёштр Nodes ёюфхЁцшЄ фтр яюы 

  tNodeData
  ----------------------------------------м
  жCounter - ёўхЄўшъ єчыр                 ж
  +---------------------------------------+
  жUpperNode - ёё√ыър эр яЁхф√фє∙шх єчы√  ж
  L----------------------------------------

╠рёёшт Nodes яюффхЁцштрхЄё  яЁюуЁрььющ т єяюЁ фюўхээюь яю тючЁрёЄрэш■ Counter
ёюёЄю эшш. ╙яюЁ фюўхээ√щ ьрёёшт Nodes ш хёЄ№ фхЁхтю ╒рЇЇьрэр.

  ┬ючьюцэюёЄ№ єяюЁ фюўшЄ№ єчы√ фхЁхтр т ышэхщэє■ яюёыхфютрЄхы№эюёЄ№ яю тючЁрёЄрэш■
ёўхЄўшъют Єръ, ўЄю єчы√, юс·хфшэ хь√х т эют√щ єчхы, тёхуфр Ёрёяюыюцхэ√ 1-щ эр ўхЄэющ,
р 2-щ эр эхўхЄэющ яючшЎшш т єяюЁ фюўхээюь ьрёёштх єчыют - трцэюх ётющёЄтю фхЁхтр ╒рЇЇьрэр.
▌Єю ётющёЄтю шёяюы№чєхЄё  фы  "с√ёЄЁюую" яхЁхёЄЁюхэш  фхЁхтр.

  ┬ ьрёёштх Nodes ёє∙хёЄтє■Є 256 "срчют√ї єчыют". ▌Єш єчы√ ёшьтюышчшЁє■Є
"шёїюфэ√х срщЄ√". ╧юых UpperNode "срчют√ї єчыют" шьххЄ чэрўхэшх Byte+256, уфх
Byte in [0..255] ш ёыєцшЄ ёё√ыъющ эр ьрёёшт NodeRef (яюёЁхфёЄтюь ьрёёштр NextNode).

  ┬ ьрёёштх Nodes ёє∙хёЄтє■Є 254 "яЁюьхцєЄюўэ√ї єчыр". ▌Єш єчы√  ты ■Єё 
юс·хфшэхэшхь ъръшї-Єю фтєї фЁєушї єчыют, эрч√трхь√ї "яЁхф√фє∙шх єчы√".
"╧Ёхф√фє∙шх єчы√" тёхуфр яЁхфёЄрты ■Є ёюсющ ярЁє (ўхЄэ√щ єчхы/i/, эхўхЄэ√щ єчхы/i+1/).
╧юых UpperNode "яЁюьхцєЄюўэ√ї єчыют" чряюыэ хЄё  ёё√ыъющ эр ўхЄэ√щ "яЁхф√фє∙шщ єчхы".
╟эрўхэшх ёё√ыъш Ёртэю эюьхЁє єчыр т ьрёёштх Nodes.

  ┬ яЁюЎхёёх яхЁхёЄЁюхэш  фхЁхтр "срчют√х єчы√" ш "яЁюьхцєЄюўэ√х єчы√" т ьрёёштх
Nodes шчьхэ ■Є ётюх яюыюцхэшх - яхЁхьх∙р■Єё .

  ╙чхы 510  ты хЄё  "ъюЁэхь фхЁхтр" ш эшъюуфр эх яхЁхьх∙рхЄё  т ьрёёштх яЁш
яхЁхёЄЁюхэшш фхЁхтр. ╧юых UpperNode фы  "ъюЁэ  фхЁхтр" тёхуфр шьххЄ чэрўхэшх 508.
╧юёъюы№ъє UpperNode тёхуфр ўхЄэюх, Єю ёё√ыър їЁрэшЄё  т тшфх ўшёыр
(эюьхЁ єчыр т Nodes, фхыхээ√щ эр 2).


╠рёёшт NodeRef ёюфхЁцшЄ ёё√ыъш эр "срчют√х єчы√" т ьрёёштх Nodes
   NodeRef
N:  0       1       2                                         255
  --------T-------T-------T------------     ----------------T---------м
  ж       ж       ж       ж                                 ж         ж
  L-------+-------+-------+------------      ---------------+----------
═ряЁшьхЁ ёё√ыър эр "срчют√щ єчхы 100" ёюфхЁцшЄё  т  ўхщъх 100 ьрёёштр NodeRef.
╤ё√ыъш эр "срчют√х єчы√" юсэюты ■Єё  яЁш яхЁхьх∙хэшш єчыют т ьрёёштх Nodes.

╠рёёшт NextNode0 ёюфхЁцшЄ ёё√ыъє эр эют√щ єчхы, ъюЄюЁ√щ юсЁрчєхЄё  шч фтєї єчыют
i ш i+1,
   NextNode0
N:  0       1       2                                         255
  --------T-------T-------T------------     ----------------T---------м
  ж       ж       ж       ж                                 ж         ж
  L-------+-------+-------+------------      ---------------+----------
уфх i - ўхЄэюх. ╟ряшё√трхЄё  ╬─═└ ёё√ыър фы  фтєї єчыют i ш i+1.
╟эрўхэшх ёё√ыъш = эюьхЁ єчыр т ьрёёштх Nodes.

╠рёёшт√ NextNode0 ш NodeRef Ёрчьх∙хэ√ т ярь Єш юфшэ чр фЁєушь Єръ, ўЄю тючьюцэр
рфЁхёрЎшш юсюшї ьрёёштют ўхЁхч ьрёёшт NextNode, уфх ¤ыхьхэ√ 0..255 ёююЄтхЄёЄтє■Є
ьрёёштє NextNode0, р 256..511 - ьрёёштє NodeRef. ▌Єю яючтюы хЄ т рфЁхёютрЄ№ ёЁрчє
юср ьрёёштр NextNode0 ш NodeRef ўхЁхч яюых UpperNode.


  ╚═╚╓╚└╦╚╟└╓╚▀ ─┼╨┼┬└

╚ёїюфэюх фхЁхтю ёЄЁюшЄё  т яЁхфяюыюцхэшш ЁртэютхЁю ЄэюёЄш ърцфюую срщЄр

  1) ╠рёёшт єчыют чряюыэ хЄё  эрўры№э√ьш чэрўхэш ьш
   Nodes
N:  0        1        2           256      257         384      385         448      449                     510
  --------м--------м--------м   --------м--------м   --------м--------м   --------м--------м              --------м
  ж   1   жж   1   жж   1   ж...ж   2   жж   2   ж...ж   4   жж   4   ж...ж   8   жж   8   ж...           ж  256  ж
  +-------++-------++-------+   +-------++-------+   +-------++-------+   +-------++-------+              +-------+
  ж 0+256 жж 1+256 жж 2+256 ж...ж   0   жж   2   ж...ж  256  жж  258  ж...ж  384  жж  386  ж...           ж  508  ж
  L--------L--------L--------   L--------L--------   L--------L--------   L--------L--------              L--------
╥ръюх чряюыэхэшх ёююЄтхЄёЄтєхЄ ёыєўр■ ЁртэютхЁю Єэ√ї ўрёЄюЄ ърцфюую срщЄр
ш ърцф√щ срщЄ ъюфшЁєхЄё  8 сшЄрьш.

  2) ╠рёёшт ёё√ыюъ эр "срчют√х єчы√" чряюыэ хЄё  эрўры№э√ьш чэрўхэш ьш
   NodeRef
N:  0       1       2                                         255
  --------T-------T-------T------------     ----------------T---------м
  ж  0    ж 1     ж 2     ж                                 ж 255     ж
  L-------+-------+-------+------------      ---------------+----------

  3) ╠рёёшт ёё√ыюъ эр эют√щ єчхы, ъюЄюЁ√щ юсЁрчєхЄё  шч фтєї єчыют i ш i+1, уфх N=(i div 2)
   NextNode0
N:  0       1       2                                254
  --------T-------T-------T------------     -----T---------м
  ж 256   ж257    ж 258   ж                      ж  510    ж
  L-------+-------+-------+------------     -----+----------


  ╩╬─╚╨╬┬└═╚┼

╧Ёш яюёЄєяыхэшш эр тїюф ъюфшЁют∙шър юўхЁхфэюую срщЄр B

1) ┴рщЄ B ъюфшЁєхЄё  яю Єхъє∙хьє фхЁхтє т ъюф C.
2) ┬ єчых, ёююЄтхЄёЄтє■∙хь ¤Єюьє срщЄє чэрўхэшх ёўхЄўшър єтхышўштрхЄё  эр 1.
3) ─хЁхтю яхЁхёЄЁрштрхЄё  т ёююЄтхЄёЄтшш ё эют√ь чэрўхэшхь ёўхЄўшър.
4) ╩юф срщЄр C чряшё√трхЄё  т Їрщы.


  ╧┼╨┼╤╥╨╬┼═╚┼ ─┼╨┼┬└

╧хЁхёЄЁюхэшх фхЁхтр юёє∙хёЄты хЄё  Єръ

0) ╙тхышўштрхЄё  эр 1 чэрўхэшх ёўхЄўшър ъюЁэхтюую (510) єчыр ьрёёштр Nodes.
1) ╧ю ьрёёштє ёё√ыюъ эр "срчют√х єчы√" NodeRef юяЁхфхы хЄё  Єхъє∙хх яюыюцхэшх єчыр i т
   ьрёёштх Nodes фы  срщЄр B.
2) ╙тхышўштрхЄё  эр 1 чэрўхэшх ёўхЄўшър єчыр i ьрёёштр Nodes.
3) ┬ ьрёёштх Nodes чэрўхэшх ёўхЄўшър єчыр i ёЁртэштрхЄё  ёю чэрўхэшхь ёўхЄўшър єчыр i+1.
   ┼ёыш ╤ўхЄўшъ(i) сюы№°х ╤ўхЄўшъ(i+1), Єю ьрёёшт Nodes яЁюёьрЄЁштрхЄё  т ёЄюЁюэє сюы№°шї эюьхЁют
   єчыют (i+2, i+3...) яюър эх сєфхЄ эрщфхэ єчхы j, ёўхЄўшъ ъюЄюЁюую сюы№°х шыш Ёртхэ ╤ўхЄўшъ(i).
4) ╙чы√ i ш (j-1) юсьхэштр■Єё  ьхёЄрьш т ьрёёштх Nodes.
5) ╧юяЁрты хЄё  ёё√ыър т ьрёёштх NodeRef фы  срщЄр B ш фы  UpperNode с√т°шї єчыют i ш (j-1) яюяЁрты ■Єё  ёё√ыъш
   т ьрёёштх NextNode.
6) ┬ ърўхёЄтх эютюую чэрўхэш  i яЁшэшьрхЄё  тхышўшэр i=NextNode(i).
7) ╧ЁютхЁ хЄё , ўЄю эютюх чэрўхэшх i<510, хёыш фр Єю яютЄюЁ хь ё я 2), шэрўх чрърэўштрхь яхЁхёЄЁюхэшх.


  ╤┴╨╬╤ ╤╫┼╥╫╚╩╬┬

╧Ёш фюёЄшцхэшш ёўхЄўшъюь ъюЁэхтюую єчыр чэрўхэш  сюы№°хую, ўхь чрфрэю т MaxTotalCounter яЁюшчтюфшЄё 
єьхэ№°хэшх тёхї ёўхЄўшъют "срчют√ї єчыют" т фтр Ёрчр. ╫Єюс√ чэрўхэшх ёўхЄўшър эх ьюуыю ёЄрЄ№ Ёртэ√ь эєы■ -
эютюх чэрўхэшх ёўхЄўшър т√ўшёы хЄё  ъръ (ёўхЄўшъ div 2)+1. ╧юёых Єръюую шчьхэхэш  фхЁхтю ёЄрэютшЄ№ё  эхъюЁЁхъЄэ√ь -
эрЁє°рхЄё  єяюЁ фюўхээюёЄ№ єчыют т Nodes яю тючЁрёЄрэш■ ёўхЄўшъют (эх яюьюцхЄ фрцх яЁхт√ўшёыхэшх ёўхЄўшъют
"яЁюьхцєЄюўэ√ї єчыют" яю рыуюЁшЄьє (ёўхЄўшъ div 2)+1 шыш ёєььшЁютрэшхь ёўхЄўшъют-яЁхф°хёЄтхээшъют).
  ╧юёых єьхэ№°хэш  тёхї ёўхЄўшъют "срчют√ї єчыют" т фтр Ёрчр фхЁхтю ╧╬╦═╬╤╥▄▐ яхЁхёЄЁрштрхЄё . └ыуюЁшЄь ёь.
т ьхЄюф. єърчрэш ї ъ ьхЄюфє ╒рЇЇьрэр (ёЄрЄшўхёъюьє). ┼фшэёЄтхээюх, ўЄю ьюцхЄ с√Є№ єыєў°хэю - єфрхЄё  шчсхцрЄ№
ёюЁЄшЁютъш "срчют√ї єчыют", Є.ъ. фрцх яюёых єьхэ№°хэш  тёхї ёўхЄўшъют "срчют√ї єчыют" т фтр Ёрчр ¤Єш єчы√
єяюЁ фюўхэ√ яю тючЁрёЄрэш■ т ьрёёштх Nodes.


  ─┼╩╬─╚╨╬┬└═╚┼

╧Ёш фхъюфшЁютрэшш фхЁхтю шэшЎшрышчшЁєхЄё  Єръцх ъръ ш яЁш ъюфшЁютрэшш.

1) ╤ўшЄ√трхЄё  юўхЁхфэющ сшЄ шч ъюфшЁютрээюую Їрщыр ш фхъюфшЁєхЄё  яЁюїюфюь яю Єхъє∙хьє фхЁхтє. └ыуюЁшЄь ёь.
   т ьхЄюф. єърчрэш ї ъ ьхЄюфє ╒рЇЇьрэр (ёЄрЄшўхёъюьє).
2) ╩юуфр фхъюфшЁютрэ срщЄ B - юэ чряшё√трхЄё  т Їрщы.
3) ╬ёє∙хёЄты хЄё  яхЁхёЄЁюхэшх фхЁхтр фы  срщЄр B, ёь. ╧┼╨┼╤╥╨╬┼═╚┼ ─┼╨┼┬└.


─хЄры№эюх юяшёрэшх яЁюЎхфєЁ ёь. ЄхъёЄ яЁюуЁрь√.
}

{ DOS Text

  ФОРМАТ ДАННЫХ для двоичного дерева ДИНАМИЧЕСКОГО метода Хаффмана:

Двоичное дерево метода Хаффмана (далее дерево) состоит из узлов.
  Максимальное возможное число узлов дерева равно удвоенной длине ПОЛНОЙ
исходной таблицы символов минус 1. Для байта (0..255 - всего 256 различных
значений) максимальное число узлов дерева равно 2*256-1 = 511 узлов.

  Желательно максимальное быстродействие при перестройке дерева,
а перестройка в ДИНАМИЧЕСКОМ методе Хаффмана происходит каждый раз, как новый
байт данных поступает на вход.

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

  Для декодировки в ДИНАМИЧЕСКОМ методе Хаффмана не нужна информация о дереве
в кодированных данных - дерево восстанавливается динамически, по мере декодировки.

  Для хранения и перестроения дерева используются следующие данные

    Nodes:tNodesData; -  данные узлов (Номер, Счетчик, Ссылка на пред. ).
    NodeRef: tNodeRef; - ссылка для базовых узлов Number in [0..255] на элемент Nodes.
    NextNode0:tNextNodes; - ссылка на новый узел, который образуется из двух узлов i и i+1,
		           где i - четное. Записывается ОДНА ссылка для двух узлов i и i+1.
    MaxTotalCounter:tFriquency; - общая сумма счетчиков для контроля сброса.

Массив Nodes состоит из записей tNodeData
   Nodes
N:  0       1       2                                         510
  ┌───────┬───────┬───────┬────────────     ────────────────┬─────────┐
  │       │       │       │                                 │         │
  └───────┴───────┴───────┴────────────      ───────────────┴─────────┘

Каждая запись массива Nodes содержит три поля

  tNodeData
  ┌───────────────────────────────────────┐
  │Counter - счетчик узла                 │
  ├───────────────────────────────────────┤
  │UpperNode - ссылка на предыдущие узлы  │
  └───────────────────────────────────────┘

Массив Nodes поддерживается программой в упорядоченном по возрастанию Counter
состоянии. Упорядоченный массив Nodes и есть дерево Хаффмана.

  Возможность упорядочить узлы дерева в линейную последовательность по возрастанию
счетчиков так, что узлы, объединяемые в новый узел, всегда расположены 1-й на четной,
а 2-й на нечетной позиции в упорядоченном массиве узлов - важное свойство дерева Хаффмана.
Это свойство используется для "быстрого" перестроения дерева.

  В массиве Nodes существуют 256 "базовых узлов", для которых Number принимает
значение от 0 до 255. Эти узлы символизируют "исходные байты". Поле UpperNode
"базовых узлов" не имеет смысла (эти узлы не имеют предшественников).

  В массиве Nodes существуют 254 "промежуточных узлов", для которых Number принимает
значение от 256 до 510. Эти узлы являются объединением каких-то двух других узлов, называемых
"предыдущие узлы". "Предыдущие узлы" всегда представляют собой пару (четный узел/i/, нечетный узел/i+1/).
Поле UpperNode "промежуточных узлов" заполняется ссылкой на четный "предыдущий узел".
Значение ссылки равно номеру узла в массиве Nodes.

  В процессе перестроения дерева "базовые узлы" и "промежуточные узлы" в массиве Nodes
изменяют свое положение - перемещаются.

  Узел 510 является "корнем дерева" и никогда не перемещается в массиве при
перестроении дерева. Поле UpperNode для "корня дерева" всегда имеет значение 508.
Поскольку UpperNode всегда четное, то ссылка хранится в виде числа
(номер узла в Nodes, деленный на 2).


Массив NodeRef содержит ссылки на "базовые узлы" в массиве Nodes
   NodeRef
N:  0       1       2                                         255
  ┌───────┬───────┬───────┬────────────     ────────────────┬─────────┐
  │       │       │       │                                 │         │
  └───────┴───────┴───────┴────────────      ───────────────┴─────────┘
Например ссылка на "базовый узел Number=100" содержится в ячейке 100 массива NodeRef.
Ссылки на "базовые узлы" обновляются при перемещении узлов в массиве Nodes.

Массив NextNode0 содержит ссылку на новый узел, который образуется из двух узлов i и i+1,
   NextNode0
N:  0       1       2                                         255
  ┌───────┬───────┬───────┬────────────     ────────────────┬─────────┐
  │       │       │       │                                 │         │
  └───────┴───────┴───────┴────────────      ───────────────┴─────────┘
где i - четное. Записывается ОДНА ссылка для двух узлов i и i+1. 
Значение ссылки = номер узла в массиве Nodes.


  ИНИЦИАЛИЗАЦИЯ ДЕРЕВА

Исходное дерево строится в предположении равновероятности каждого байта

  1) Массив узлов заполняется начальными значениями
   Nodes
N:  0        1        2           256      257         384      385         448      449                     510
  ┌───────┐┌───────┐┌───────┐   ┌───────┐┌───────┐   ┌───────┐┌───────┐   ┌───────┐┌───────┐              ┌───────┐
  │   1   ││   1   ││   1   │...│   2   ││   2   │...│   4   ││   4   │...│   8   ││   8   │...           │  256  │
  ├───────┤├───────┤├───────┤   ├───────┤├───────┤   ├───────┤├───────┤   ├───────┤├───────┤              ├───────┤
  │ 0+256 ││ 1+256 ││ 2+256 │...│   0   ││   2   │...│  256  ││  258  │...│  384  ││  386  │...           │  508  │
  └───────┘└───────┘└───────┘   └───────┘└───────┘   └───────┘└───────┘   └───────┘└───────┘              └───────┘
Такое заполнение соответствует случаю равновероятных частот каждого байта
и каждый байт кодируется 8 битами.

  2) Массив ссылок на "базовые узлы" заполняется начальными значениями
   NodeRef
N:  0       1       2                                         255
  ┌───────┬───────┬───────┬────────────     ────────────────┬─────────┐
  │  0    │ 1     │ 2     │                                 │ 255     │
  └───────┴───────┴───────┴────────────      ───────────────┴─────────┘

  3) Массив ссылок на новый узел, который образуется из двух узлов i и i+1, где N=(i div 2)
   NextNode
N:  0       1       2                                 254
  ┌───────┬───────┬───────┬────────────     ──────┬─────────┐
  │ 256   │257    │ 258   │                       │  510    │
  └───────┴───────┴───────┴────────────      ─────┴─────────┘


  КОДИРОВАНИЕ

При поступлении на вход кодировщика очередного байта B

1) Байт B кодируется по текущему дереву в код C.
2) В узле, соответствующем этому байту значение счетчика увеличивается на 1.
3) Дерево перестраивается в соответствии с новым значением счетчика.
4) Код байта C записывается в файл.


  ПЕРЕСТРОЕНИЕ ДЕРЕВА

Перестроение дерева осуществляется так

0) Увеличивается на 1 значение счетчика корневого (510) узла массива Nodes.
1) По массиву ссылок на "базовые узлы" NodeRef определяется текущее положение узла i в
   массиве Nodes для байта B.
2) Увеличивается на 1 значение счетчика узла i массива Nodes.
3) Массив Nodes значение счетчика узла i сравнивается со значением счетчика узла i+1.
   Если Счетчик(i) больше Счетчик(i+1), то массив Nodes просматривается в сторону больших номеров
   узлов (i+2, i+3...) пока не будет найден узел j, счетчик которого больше или равен Счетчик(i).
4) Узлы i и (j-1) обмениваются местами в массиве Nodes. 
5) Поправляется ссылка в массиве NodeRef для байта B и для UpperNode бывших узлов i и (j-1) поправляются ссылки 
   в массиве NextNode.
6) В качестве нового значения i принимается величина i=NextNode(i).
7) Проверяется, что новое значение i<510, если да то повторяем с п 2), иначе заканчиваем перестроение.


  СБРОС СЧЕТЧИКОВ

При достижении счетчиком корневого узла значения большего, чем задано в MaxTotalCounter производится 
уменьшение всех счетчиков "базовых узлов" в два раза. Чтобы значение счетчика не могло стать равным нулю - 
новое значение счетчика вычисляется как (счетчик div 2)+1. После такого изменения дерево становиться некорректным - 
нарушается упорядоченность узлов в Nodes по возрастанию счетчиков (не поможет даже превычисление счетчиков
"промежуточных узлов" по алгоритму (счетчик div 2)+1 или суммированием счетчиков-предшественников). 
  После уменьшения всех счетчиков "базовых узлов" в два раза дерево ПОЛНОСТЬЮ перестраивается. Алгоритм см. 
в метод. указаниях к методу Хаффмана (статическому). Единственное, что может быть улучшено - удается избежать
сортировки "базовых узлов", т.к. даже после уменьшения всех счетчиков "базовых узлов" в два раза эти узлы
упорядочены по возрастанию в массиве Nodes.


  ДЕКОДИРОВАНИЕ

При декодировании дерево инициализируется также как и при кодировании.

1) Считывается очередной бит из кодированного файла и декодируется проходом по текущему дереву. Алгоритм см. 
   в метод. указаниях к методу Хаффмана (статическому).
2) Когда декодирован байт B - он записывается в файл.
3) Осуществляется перестроение дерева для байта B, см. ПЕРЕСТРОЕНИЕ ДЕРЕВА.


Детальное описание процедур см. текст програмы.
}

IMPLEMENTATION

END.