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.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing