Text Distance from Nested and Hierarchical Repetitions: A Compression-Based Perspective

基于嵌套与分层重复的文本距离：一种基于压缩的视角

Abstract: We present a new method for structural sequence analysis grounded in Algorithmic Information Theory (AIT). At its core is the Ladderpath approach, which extracts nested and hierarchical relationships among repeated substructures in linguistic sequences — an instantiation of AIT’s principle of describing data through minimal generative programs.

摘要： 我们提出了一种基于算法信息论（AIT）的结构化序列分析新方法。其核心是“Ladderpath”方法，该方法能够提取语言序列中重复子结构之间的嵌套和分层关系——这是 AIT 关于通过最小生成程序描述数据这一原则的具体实现。

These structures are then used to define three distance measures: a normalized compression distance (NCD), and two alternative distances derived directly from the Ladderpath representation. Integrated with a $k$-nearest neighbor classifier, these distances achieve strong and consistent performance across in-distribution, out-of-distribution (OOD), and few-shot text classification tasks.

这些结构随后被用于定义三种距离度量：一种归一化压缩距离（NCD），以及两种直接从 Ladderpath 表示中导出的替代距离。结合 $k$-近邻分类器，这些距离在分布内（in-distribution）、分布外（OOD）以及少样本（few-shot）文本分类任务中均表现出强大且一致的性能。

In particular, all three methods outperform both gzip-based NCD and BERT under OOD and low-resource settings. These results demonstrate that the structured representations captured by Ladderpath preserve intrinsic properties of sequences and provide a lightweight, interpretable, and training-free alternative for text modeling.

特别是在 OOD 和低资源环境下，这三种方法均优于基于 gzip 的 NCD 和 BERT。这些结果表明，Ladderpath 捕获的结构化表示保留了序列的内在属性，并为文本建模提供了一种轻量级、可解释且无需训练的替代方案。

This work highlights the potential of AIT-based approaches for structural and domain-agnostic sequence understanding.

这项工作突显了基于 AIT 的方法在结构化和领域无关序列理解方面的潜力。