page_title: Adaptive Huffman coding
section_title: Vitter algorithm
hierarchical_section_title: Adaptive Huffman coding / Algorithms / Vitter algorithm
caption_attribution_description: English: Step 2: Internal node
context_page_description: Adaptive Huffman coding is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to changing conditions in data.
  The benefit of one-pass procedure is that the source can be encoded in real time, though it becomes more sensitive to transmission errors, since just a single loss ruins the whole code.
context_section_description: Some important terminologies & constraints :-
  Implicit Numbering : It simply means that nodes are numbered in increasing order by level and from left to right. i.e. nodes at bottom level will have low implicit number as compared to upper level nodes and nodes on same level are numbered in increasing order from left to right.
  Invariant : For each weight w, all leaves of weight w precede all internal nodes having weight w.
  Blocks : Nodes of same weight and same type (i.e. either leaf node or internal node) form a Block.
  Leader : Highest numbered node in a block.
  Blocks are interlinked by increasing order of their weights.
  A leaf block always precedes internal block of same weight, thus maintaining the invariant.
  NYT (Not Yet Transferred) is special node and used to represents symbols which are 'not yet transferred'.
  algorithm for adding a symbol is
      leaf_to_increment := NULL
      p := pointer to the leaf node containing the next symbol
  
      if (p is NYT) then
            Extend p by adding two children
            Left child becomes new NYT and right child is the new symbol leaf node
            p := parent of new symbol leaf node
            leaf_to_increment := Right Child of p
      else
          Swap p with leader of its block
          if (new p is sibling to NYT) then
              leaf_to_increment := p
              p := parent of p
  
      while (p ≠ NULL) do
          Slide_And_Increment(p)
  
      if (leaf_to_increment != NULL) then
          Slide_And_Increment(leaf_to_increment)
  function Slide_And_Increment(p) is
      previous_p := parent of p
  
      if (p is an internal node) then
          Slide p in the tree higher than the leaf nodes of weight wt + 1
          increase weight of p by 1
          p := previous_p
      else
          Slide p in the tree higher than the internal nodes of weight wt
          increase weight of p by 1
          p := new parent of p.
  Encoder and decoder start with only the root node, which has the maximum number. In the beginning it is our initial NYT node.
  When we transmit an NYT symbol, we have to transmit code for the NYT node, then for its generic code.
  For every symbol that is already in the tree, we only have to transmit code for its leaf node.
caption: Slide_And_Increment(internal node) sliding step 2. Node P slides in front of next block of leaves nodes, with weight wt+1.
exif: {}