NCD ( x, y ) = C ( x, y ) − min C ( x ) , C ( y ) max C ( x ) , C ( y ) (1) 4 2. Fast Compression Distance 60 of experiments reported in Section 3. We conclude in Section 4. 59 Compression-based similarity measures exploit general off-the-shelf com- 61 pressors to estimate the amount of information shared by any two objects. 62 They have been employed for clustering and classification on diverse data 63 types such as texts and images (Watanabe et al., 2002), with Keogh et al. 64 (2004) reporting that they outperform general distance measures. The most 65 widely known and used of such notions is the Normalized Compression Dis- 66 tance (NCD), defined for any two objects x and y as: 67 where C ( x ) represents the size of x after being compressed by a com- 68 pressor (such as Gzip), and C ( x, y ) is the size of the compressed version 69 of x appended to y . If x = y , the NCD is approximately 0, as the full 70 string y can be described in terms of previous strings found in x ; if x and y 71 share no common information the NCD is 1 + e , where e is a small quantity 72 (usually e < 0 . 1) due to imperfections characterizing real compressors. The 73 idea is that if x and y share common information they will compress better 74 together than separately, as the compressor will be able to reuse recurring 75 patterns found in one of them to more efficiently compress the other. The 76 generality of NCD allows applying it to diverse datatypes, including natu- 77 ral texts. Applications to authorship categorization have been presented by 78