Huffman’s well-known coding method constructs a minimum redundancy code which minimizes the expected value of the word length. In this paper, we characterize the minimum redundancy code with the minimum variance of the word length. An algorithm is given to construct such a code. It is shown that the code is in a certain sense unique. Furthermore, the code is also shown to have a strong property in that it minimizes a general class of functions of the minimum redundancy codes as long as the functions are nondecreasing with respect to the path lengths from the root to the internal nodes of the corresponding decoding trees.

article Free Access Share on On Live-Dead Analysis for Global Data Flow Problems Author: Lawrence T. Kou IBM Thomas J Watson Research Center, P O Box 218, Yorktown Heights, NY IBM Thomas J Watson Research Center, P O Box 218, Yorktown Heights, NYView Profile Authors Info & Claims Journal of the ACMVolume 24Issue 3July 1977 pp 473–483https://doi.org/10.1145/322017.322027Published:01 July 1977Publication History 26citation464DownloadsMetricsTotal Citations26Total Downloads464Last 12 Months9Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A set of queries Q is said to have the consecutive retrieval property with respect to a set of records R if there exists an organization of the record set (without duplication of any record) such that for every $q_i \in Q$, all relevant records can be stored in consecutive storage locations [5]. In practice, this property does not appear very often. Hence, either duplication of records is allowed so that pertinent records corresponding to any query are always stored consecutively or storing the pertinent records corresponding to a query in several blocks of consecutive storage locations is necessary so that each record is stored only once. The former gives rise to the problem of minimizing the duplication of records and the latter gives rise to the problem of minimizing the number of blocks of consecutive storage of relevant records. The computational complexity of each of these two problems is studied in this paper and both of these problems are shown to be polynomial complete in the sense of Cook [2] and Karp [8].