Content deleted Content added
Ira Leviton (talk | contribs) m Fixed a reference. Please see Category:CS1 errors: missing pipe. |
|||
Line 262:
=== {{anchor|Hu-Tucker coding|Alphabetic Huffman coding|Alphabetic Huffman tree}}Optimal alphabetic binary trees (Hu–Tucker coding) ===
In the standard Huffman coding problem, it is assumed that any codeword can correspond to any input symbol. In the alphabetic version, the alphabetic order of inputs and outputs must be identical. Thus, for example, <math>A = \left\{a,b,c\right\}</math> could not be assigned code <math>H\left(A,C\right) = \left\{00,1,01\right\}</math>, but instead should be assigned either <math>H\left(A,C\right) =\left\{00,01,1\right\}</math> or <math>H\left(A,C\right) = \left\{0,10,11\right\}</math>. This is also known as the '''Hu–Tucker''' problem, after [[T. C. Hu]] and [[Alan Tucker]], the authors of the paper presenting the first [[Time complexity#Quasilinear time|<math>O(n\log n)</math>-time]] solution to this optimal binary alphabetic problem,<ref>{{Cite journal | doi = 10.1137/0121057| title = Optimal Computer Search Trees and Variable-Length Alphabetical Codes| journal = SIAM Journal on Applied Mathematics| volume = 21| issue = 4| pages = 514| year = 1971| last1 = Hu | first1 = T. C.|author1-link=T. C. Hu |last2 = Tucker | first2 = A. C. | author2-link = Alan Tucker| jstor = 2099603}}</ref> which has some similarities to Huffman algorithm, but is not a variation of this algorithm. A later method, the [[Garsia–Wachs algorithm]] of [[Adriano Garsia]] and [[Michelle L. Wachs]] (1977), uses simpler logic to perform the same comparisons in the same total time bound. These optimal alphabetic binary trees are often used as [[binary search tree]]s.<ref>{{citation
| last = Knuth | first = Donald E. | author-link = Donald Knuth
| contribution = Algorithm G (Garsia–Wachs algorithm for optimum binary trees)
| |||