NORMALIZED COMPRESSION DISTANCE WITH TYPOGRAPHICAL ERRORS: A PRELIMINARY ASSESSMENT

Abstract

Rooted in the principles of KolmogorovComplexity, the Normalized Compression Distance (NCD)has emerged as a versatile similarity metric in problemdomains ranging from music to DNA analysis. Studies in theliterature have indicated that the NCD exhibits goodperformance in the face of large, randomly corrupted,documents. This work, as part of a larger effort to explorethe viability of the NCD as a similarity metric for analyzingand clustering medical documents, presents a preliminaryassessment of NCD performance on smaller, sub-document,samples subject to real-world style typographical errors.When applied to an encyclopedia of sewing and TheFederalist Papers the NCD exhibited graceful degradationwith increasing typographical error rates and decreasingminimum paragraph size.Index Terms ⎯ Document Analysis, Normalized Compression Distance, Text Analysis, Typographical ErrorAnalysis.