Minimum Discrimination Variable Length Parsing and Coding Problems

Tuesday, November 12, 1996 - 11:00am - 12:00pm
Keller 3-180
Julia Abrahams (Office of Naval Research)
A common minimum-discrimination perspective unifies several variable-length parsing and coding problems along with joint parsing/coding problems or dual-tree coding. In particular, Stubley and Blake's minimum-discrimination parse tree problem corresponds to Karp's variable-length unequal-costs coding problem for arbitrary source distributions in the sense that, where Stubley and Blake minimize the discrimination D(P,Q), Karp minimizes D(Q,P). In the special case that Q is uniform, Stubley and Blake's problem is Tunstall parsing and Karp's problem is Varn coding. In the special case that P is dyadic, Stubley and Blake's problem is of interest because Karp's problem is Huffman coding.