Content deleted Content added
m →top: Copy edit ▸ Presentation ▸ On mobile the table appears first, then the image, making the image caption the very last thing to appear. In this context the image caption ending with a colon appears more than just a bit silly — this minor mod fixes that. Tags: Mobile edit Mobile app edit Android app edit |
|||
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)
| |||