Automatic recognition of correct solutions as a result of a ciphertext only attack of simple ciphers is not a trivial issue and still remains a taxing problem. A new compression based method for the automatic cryptanalysis of simple substitution ciphers is introduced in this paper. In particular, this paper presents how a Prediction by Partial Matching (PPM) text compression scheme, a method that shows a high level of performance when applied to different natural language processing tasks, can also be used for the automatic decryption of simple substitution ciphers. Experimental results showed that approximately 92% of the cryptograms were decrypted correctly without any errors and 100% with just three errors or less. Extensive investigations are described in this paper, in order to determine which is the most appropriate type of PPM scheme that can be applied to the problem of automatically breaking substitution ciphers. This paper shows how a new character-based PPM variant significantly outperforms other schemes including the standard Gzip and Bzip2 compression schemes. We also apply a word-based variant which when combined with the character-based method leads to further improved results.