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