text-classification-with-gzip

该项目是对论文《Less is More: Parameter-Free Text Classification with Gzip》的复现。

论文核心是科尔莫格洛夫复杂度。

论文关键点是：

1. gzip 利用信息熵做了无损压缩，同时保留了位置编码。最后得到的压缩串长度作为科尔莫格洛夫复杂度的近似。
2. 然后利用信息距离计算两个串的相似度。信息距离在直觉上是将两个串互相之间转化所需要的最小信息量（也就是两个串的前述复杂度之差），差越小越相近。

柯尔莫哥洛夫复杂度、信息距离、归一化压缩距离

柯尔莫哥洛夫复杂度（Kolmogorov Complexity）、信息距离（Information Distance）、以及归一化压缩距离（Normalized Compression Distance, NCD）是信息论和计算理论中的重要概念。下面分别对它们进行说明，并给出相关公式。

柯尔莫哥洛夫复杂度（不可计算）

柯尔莫哥洛夫复杂度（Kolmogorov Complexity），也称为描述复杂度，是描述一个字符串长度的最短程序（在固定的计算模型中）的长度。对于任何给定的字符串 $s$，其柯尔莫哥洛夫复杂度表示为 $K(s)$。直观上， $K(s)$ 度量了以最简洁的方式描述字符串 $s$ 所需的信息量。

公式

$K(s) = \min_{p}{ |p| : U(p) = s}$

这里， $p$ 是生成字符串 $s$ 的程序， $|p|$ 是程序的长度， $U$ 是一个普适计算机（例如图灵机），意味着使用程序 $p$ 在 $U$ 上运行时输出 $s$ 。

不过，需要注意的是，柯尔莫哥洛夫复杂度是不可计算的，这意味着没有一种算法可以精确计算出任意给定对象的柯尔莫哥洛夫复杂度。

信息距离（不可计算）

信息距离是衡量两个字符串之间差异的最直接方式，定义为将一个字符串转换成另一个字符串所需的最小信息量。

公式

$E(x, y) = \max { K(x|y), K(y|x) }$

这里， $x$ 和 $y$ 是两个字符串， $K(x|y)$ 表示在已知 $y$ 的条件下，描述 $x$ 所需的最小程序长度。

在某些定义下，两个对象之间的信息距离可以被视为将一个对象转换为另一个对象所需的最短程序的长度。信息距离具有对称性和非负性的特点，但同样由于柯尔莫哥洛夫复杂度的不可计算性，直接计算两个对象之间的信息距离也是不可行的。

归一化压缩距离（NCD）

归一化压缩距离是基于实际压缩算法对信息距离概念的一种实用近似，用于衡量两个字符串的相似度。它不直接计算柯尔莫哥洛夫复杂度，而是使用实际的压缩算法（如ZIP、BZIP2等）的输出长度作为复杂度的近似。

公式

$NCD(x, y) = \frac{C(xy) - \min{C(x), C(y)}}{\max{C(x), C(y)}}$

这里， $C(x)$ 和 $C(y)$ 分别是字符串 $x$ 和 $y$ 压缩后的长度， $C(xy)$ 是将 $x$ 和 $y$ 串联起来后的字符串压缩的长度。NCD 的值介于 0 和 1 之间，0 表示两个字符串完全相同，1 表示两个字符串完全不同。

NCD 的优点在于它既能够应用于任何类型的数据，又不依赖于数据的具体内容，使得它在模式识别、分类等领域有着广泛的应用。

这三个概念共同构成了理解数据的复杂性、数据之间相似度或差异性的理论基础，特别是在数据分析、机器学习和其他计算领域中。