An extended similarity distance for use with computable information estimators
Ulrich Speidel · 2014
Computable complexity and information estimators such as those from the Lempel-Ziv family or Titchener's T-complexity and T-information may be used in similarity comparison in conjunction with the Normalized Compression Distance (NCD). The NCD is (almost) a metric and computes a similarity distance between two digitally encoded objects x and y based exclusively on their estimated individual and joint information content. In some similarity comparison applications, however, objects may also be distinguished by entropy rate rather than information content only. However, the NCD is not sensitive to entropy rate. This paper proposes an entropy rate sensitive extended version of the NCD, called ENCD, for use in such applications. It also shows that the T-information performs well in the context of both NCD and ENCD. Finally, the paper discusses the problem of added noise and scaling in input data to the NCD and ENCD, and demonstrates how appropriate encoding of the input data may mitigate the impact of these effects.