Language Trees and Zipping

自然界中的许多系统和现象通常以序列或字符串的形式表示。例如，在对物理过程进行实验研究时，人们通常只能通过测量设备来获取系统的信息，该设备会产生某种可观测量的时间记录，即一系列数据。另一方面，其他系统本质上由字符串描述，例如DNA和蛋白质序列，语言。

在分析一串字符时，主要问题是提取它所包含的信息。对于DNA序列来说，这将对应于识别编码基因及其特定功能的子序列。另一方面，对于书面文本，人们对于理解它感兴趣，即识别文本所使用的语言、作者、所讨论的主题以及可能的历史背景。

以这样的方式提出的问题，人们很容易从一个非常有趣的角度来解决它：信息论的香农和祖雷克的角度。在这个背景下，信息这个词具有非常明确的含义，即字符串的熵，它是源头发出的序列给我们带来的惊喜的度量。

正如明显的，"信息"一词在不同的语境中有不同的含义。现在假设我们能够测量给定序列（例如文本）的熵。我们能否从这个度量中获得我们试图从序列中提取的信息（在语义上）？这是我们在本文中要探讨的问题。

特别是我们以一种非常普遍的方式定义了一对序列之间的远近（或相似性）的概念，基于它们的相对信息内容。我们设计了一种方法来测量这种距离，不会因为字符串的性质而失去一般性，该方法基于数据压缩技术。我们要解决的具体问题是，序列之间的这种信息距离是否代表了序列之间的真实语义差异。结果表明，至少在我们实施该方法的示例框架中，答案是肯定的。我们选择了一些文本语料库进行测试，并根据在一些语言相关问题上获得的结果评估了我们的方法。是否可能自动识别给定文本所写的语言？是否可能自动猜测给定文本的作者？最后但同样重要的是，是否可能以一种方式识别文本中所处理的主题，以便将其自动分类到给定语料库中的许多其他文本之中？在所有这些情况下，答案都是肯定的，我们将在接下来提供证据。

在进入我们的方法细节之前，让我们简要回顾一下熵的定义，它与一个非常古老的问题密切相关，即在传输信息时不丢失信息的问题，也就是威尔士语的高效编码问题。

在过去的一个世纪里，对于文本（或图像或任何其他类型的信息）的最优编码问题进行了大量研究。特别是香农发现了对于给定序列进行编码的可能性存在一定的限制。这个限制就是序列的熵。熵有许多等价的定义，但在这个背景下，最好的定义可能是Chaitin-Kolmogorov熵K65；Ch66；Ch90；S64：字符串的熵是产生该字符串作为输出的最小程序的长度（以位为单位）。这个定义非常抽象。特别是，即使原则上也不可能找到这样的程序。尽管如此，还是有一些明确设计用来接近这个理论限制的算法。这些算法就是文件压缩器或者压缩软件。压缩软件会将一个文件尝试转换为尽可能短的文件。显然，这不是最佳的编码方式，但它代表了一个很好的近似。其中一个最早的压缩算法是Lempel-Ziv算法（LZ77），LZ77（例如被 $gzip$ ， $zip$ 和 $Stacker$ 使用）。简要回顾一下它的工作原理是很有趣的。 LZ77算法在输入数据中找到重复的字符串。更准确地说，它寻找与前瞻缓冲区开头的最长匹配，并输出由两个数字表示的指向该匹配的指针：一个距离，表示匹配开始的位置，和一个长度，表示匹配字符的数量。例如，序列 $\sigma_{1}\;...\;\sigma_{n}$ 的匹配将由指针 $(d,n)$ 表示，其中 $d$ 是匹配开始的距离。匹配的序列将使用与 $(\log_{2}(d)+\log_{2}(n))$ 相等的位数进行编码：即编码 $d$ 和 $n$ 所需的位数。粗略地说，两个连续 $\sigma_{1}\;...\;\sigma_{n}$ 之间的平均距离大致等于其出现概率的倒数。因此，压缩器将用少量字节编码更频繁的序列，并且只为罕见的序列花费更多字节。 LZ77拉链具有以下显著特性：如果它对由遍历源发出的长度为 $L$ 的序列进行编码，而该源的每个字符的熵为 $s$ ，那么当文本长度趋近于 $\infty$ 时，压缩文件的长度除以原始文件的长度趋近于 $s$ （参见LZ77、Shannon-LeC和相关参考文献）。换句话说，它并不是以最佳方式对文件进行编码，但随着文件长度的增加，它的编码效果越来越好。

压缩算法为熵的测量提供了强大的工具，应用领域广泛，涵盖了从动力系统理论到语言学和遗传学等众多领域。因此，我们可以得出的第一个结论是，通过对序列进行压缩，可以简单地测量其熵。在本文中，我们利用这种算法来定义序列对之间的远近概念。

理解我们定义的一种简单方法是回想一下相对熵的概念，其本质可以通过以下示例轻松理解。让我们考虑两个符合人体工程学的源 $\cal A$ 和 $\cal B$ ，它们发出 $0$ 和 $1$ 的序列： $\cal A$ 以概率 $p$ 发出 $0$ ，以概率 $1-p$ 发出 $1$ ，而 $\cal B$ 以概率 $q$ 发出 $0$ ，以概率 $1-q$ 发出 $1$ 。如前所述，应用于 $\cal A$ 发出的序列的压缩算法将能够几乎最优地编码该序列，即用 $-\log_{2}p$ 位编码一个 $0$ ，用 $-\log_{2}(1-p)$ 位编码一个 $1$ 。这种最优编码对于 $\cal B$ 发出的序列来说并不是最优的。特别是，在 $\cal A$ 的最优编码中，由 $\cal B$ 发出的序列的每个字符的熵为 $-q\,log_{2}p-(1-q)\,log_{2}(1-p)$ ，而在其最优编码中，由 $\cal B$ 发出的序列的每个字符的熵为 $-q\,log_{2}q-(1-q)\,log_{2}(1-q)$ 。 每个字符编码 $\cal B$ 发出的序列所浪费的比特数，使用最适合 $\cal A$ 的编码是 $\cal A$ 和 $\cal B$ 的相对熵（参见Kullback-Leibler KL）， $S_{{\cal A}{\cal B}}=-q\,log_{2}\frac{p}{q}-(1-q)\,log_{2}\frac{1-p}{1-q}$ 。

存在几种方法来衡量相对熵（参见shannon-lec; merhav-ziv）。当然，一种可能性是按照前面的示例所描述的方法：使用给定源的最佳编码来编码另一个源的消息。我们沿着这条路径前进。为了定义两个源 $\cal A$ 和 $\cal B$ 之间的相对熵，我们从源 $\cal A$ 中提取一个长序列 $A$ ，以及从源 $\cal B$ 中提取一个长序列 $B$ 和一个小序列 $b$ 。我们通过简单地将 $b$ 附加在 $A$ 之后来创建一个新序列 $A+b$ 。序列 $A+b$ 现在被压缩，例如使用 $gzip$ ，并且在为 $A$ 优化的编码中， $b$ 的长度测量值将为 $\Delta_{Ab}=L_{A+b}-L_{A}$ ，其中 $L_{X}$ 表示压缩文件 $X$ 的位数。字符 $\cal A$ 和 $\cal B$ 之间的相对熵每个字符将通过估计来确定。

$$S_{\cal{A}{\cal B}}=(\Delta_{Ab}-\Delta_{Bb})/|b|$$

(1)

其中 $|b|$ 是序列 $b$ 的字符数， $\Delta_{Bb}/|b|=(L_{B+b}-L_{B})/|b|$ 是源 $\cal B$ 的熵的估计值。

从语言学的角度来看，如果 $A$ 和 $B$ 是用不同语言书写的文本， $\Delta_{Ab}$ 是一个衡量母语为 $A$ 的普通人理解 $B$ 语言文本的难度的指标。让我们考虑一个具体的例子，其中 $A$ 和 $B$ 是用英语和意大利语等语言书写的两个文本。我们取一个较长的英语文本，并将一个意大利语文本附加到它上面。拉链开始从英语文本开始读取文件。因此，在一段时间后，它能够最优地编码英语文件。当意大利语部分开始时，拉链开始以对英语最优的方式对其进行编码，即在英语部分找到大部分匹配项。因此，意大利语文件的第一部分使用英语代码进行编码。过了一段时间，拉链“学会”了意大利语，即相对于英语部分，它逐渐倾向于在意大利语部分找到大部分匹配项，并改变其规则。因此，如果意大利语文件的长度足够小（即大部分匹配项出现在英语部分），表达式（1）将给出相对熵的度量。 我们已经在已知相对熵的序列上进行了此方法的检验，得到了理论相对熵值与计算值bcl之间的极好一致性。我们在语言语料库上的实验结果对于文件大小的大幅变化非常稳健（通常为 $1-15$ 千字节（Kb），而文件大小一般为 $A$ Kb数量级）。

这些考虑打开了许多可能的应用途径。尽管我们的方法非常通用，但在本文中我们特别关注代表文本的字符序列，并将重点讨论计算语言学中的两个问题：上下文识别和序列语料库的分类。

语言识别：假设我们对自动识别给定文本所使用的语言感兴趣。我们使用的程序考虑了尽可能多的不同（已知）语言的一系列长文本（语料库）：英语、法语、意大利语、塔加洛语……我们简单地考虑了将未知文件的一部分附加到所有可能的其他文件上，并测量它们之间的差异。差异最小的文件将选择与该文件最接近的语言，或者如果语言集合中包含该语言，则选择完全相同的语言。我们特别考虑了欧洲联盟（EU）官方语言的语料库：丹麦语、荷兰语、英语、芬兰语、法语、德语、意大利语、葡萄牙语、西班牙语和瑞典语。语料库中的每个文本依次扮演了文本的角色，而其他所有文本则扮演了参考文件的角色。 使用特定的 $10$ 个文本（总共 $100$ 个文本）进行研究，我们发现对于任何一个文本，该方法都能识别出其语言：这意味着对于任何一个文本 $X$ ，与其差异 $L_{A_{i}+x}-L_{A_{i}}$ 最小的文本 $A_{i}$ 就是同一语言的文本。此外，我们发现对于每个 $X$ ，根据差异 $L_{A_{i}+x}-L_{A_{i}}$ 对所有文本 $A_{i}$ 进行排名，同一语言的文本总是排在前面。对于长度为 $X$ 字符的文件，语言识别效果非常好，甚至可以更小到 $20$ 字符。

作者归属：假设在这种情况下，我们对于给定文本的作者的自动识别感兴趣。我们将考虑之前所述的一个尽可能大的、由几个（已知）作者撰写的相同语言的文本集合，并寻找差异最小的文本。为了收集一定的统计数据，我们使用了一个包含 $90$ 个不同文本的语料库进行了实验，每次运行时将语料库中的一个文本作为未知文本。结果显示在表1中，成功率为 $93.3\%$ 。该成功率是已识别出作者的文本数量（另一个同一作者的文本被排在第一位）与考虑的总文本数量之间的比率。

通过考虑更精细的程序（例如对给定文本的前 $m$ 个排名文本进行加权平均），成功率会增加。当然，每个作者的成功率会有波动，这是可以预料的，因为写作风格是一件难以把握和定义的事情；此外，它在一个作者的作品中可能会有很大的变化。

序列分类：假设有一组文本，例如一个包含不同语言版本的同一文本的语料库，并且假设对这个语料库的分类感兴趣。

毋庸置疑，对特定语言学特征进行仔细调查并不在我们的目的之内。在这个框架下，我们只关心展示该方法在多个学科中的潜力。

总结一下，我们在这里提出了一种通用的方法来自动识别和分类字符序列。我们特别讨论了在多种语言的文本语料库中的应用。我们展示了如何通过基于相对熵概念的文本间远离度的合适定义，从一个文本中提取出几个重要信息：它所使用的语言、所讨论的主题以及作者；另一方面，该方法允许根据语料库中元素之间的相对距离对序列集合（语料库）进行分类，并将它们组织成层次结构（图、树等）。该方法非常灵活和通用。它适用于任何类型的字符序列语料库，无论其背后的编码类型是什么：时间序列、语言、遗传序列（DNA、蛋白质等）。它不需要对所研究的语料库有任何先验知识（字母表、语法、句法）或统计信息。 这些特征在人类直觉可能会失败的领域非常重要：DNA和蛋白质序列、地质时间序列、股市数据、医疗监测等。致谢：作者感谢Piero Cammarano、Giuseppe Di Carlo和Anna Lo Piano进行了许多启发性的讨论。本工作得到了欧洲网络-分形项目（合同号FMRXCT980183）和GNFM（INDAM）的部分支持。