Loading ...
Sorry, an error occurred while loading the content.
 

Hu-Tucker Algorithm

Expand Messages
  • Roger Bagula
    ... http://www.cs.rit.edu/~std3246/thesis/node10.html -- Respectfully, Roger L. Bagula
    Message 1 of 1 , Apr 1, 2004

      Overview

      This chapter will present a detailed description of the Hu-Tucker algorithm as it appears in [Hu82] and [Knu73b].

      The Hu-Tucker algorithm consists of three phases: Combination, Level Assignment, and Reconstruction. During the first phase, Combination, the initial sequence of nodes is used to build an optimal tree, which is not necessary alphabetic. At this stage the minimality of the cost of the tree is achieved.

      During the second stage, Level Assignment, the tree obtained in step one is traversed and the levels of the terminal nodes are calculated, beginning at the root of the tree, which is at level 0. At the end of stage two, the tree obtained in stage one is disregarded.

      Stage three, Recombination, builds an optimal alphabetic binary tree bottom up, from the initial sequence of nodes and their corresponding level assignments produced at the end of stage two, by combining adjacent nodes which have the same levels (level by level construction). The resulting Hu-Tucker tree is an optimal alphabetic binary tree.


      http://www.cs.rit.edu/~std3246/thesis/node10.html

      -- 
      Respectfully, Roger L. Bagula
      tftn@..., 11759Waterhill Road, Lakeside,Ca 92040-2905,tel: 619-5610814 :
      URL :  http://home.earthlink.net/~tftn
      URL :  http://victorian.fortunecity.com/carmelita/435/ 
      
      

    Your message has been successfully submitted and would be delivered to recipients shortly.