THE LEMPEL ZIV ALGORITHM AND MESSAGE COMPLEXITY

Data compression has been suggested as a non-parametric way of discriminating between message sources (e.g., a complex noise message should compress less than a more redundant signal message). Compressions obtained from a Lempel-Ziv algorithm for relatively short messages, such as those encountered in practice, are examined. The intuitive notion of message complexity has less connection with compression than one might expect from known asymptotic results about infinite messages. Nevertheless, discrimination by compression remains an interesting possibility.