Scholarlink

Detecting and measuring repetitiveness of strings is a problem that has been extensively studied in data compression and text indexing. When the data are structured in a non-linear way, as in two-dimensional strings, inherent redundancy offers a rich source for compression, yet systematic studies on repetitiveness measures are still lacking. In this paper, we extend to two dimensions the measures \(\delta \) and \(\gamma \) , defined in terms of the submatrices of the input, as well as the measures g, \(g_{rl}\) , and b, which are based on copy-paste mechanisms. We study their properties and mutual relationships, and we show that the two classes of measures become incomparable when two-dimensional inputs are considered. We also compare our measures with the 2D Block Tree data structure [Brisaboa et al., Computer J., 2024], and provide some insights for the design of effective 2D compressors.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Generalization of Repetitiveness Measures for Two-Dimensional Strings

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Lorenzo Carfagna,
  • Giovanni Manzini,
  • Giuseppe Romana,
  • Marinella Sciortino,
  • Cristian Urbina

摘要

Detecting and measuring repetitiveness of strings is a problem that has been extensively studied in data compression and text indexing. When the data are structured in a non-linear way, as in two-dimensional strings, inherent redundancy offers a rich source for compression, yet systematic studies on repetitiveness measures are still lacking. In this paper, we extend to two dimensions the measures \(\delta \) and \(\gamma \) , defined in terms of the submatrices of the input, as well as the measures g, \(g_{rl}\) , and b, which are based on copy-paste mechanisms. We study their properties and mutual relationships, and we show that the two classes of measures become incomparable when two-dimensional inputs are considered. We also compare our measures with the 2D Block Tree data structure [Brisaboa et al., Computer J., 2024], and provide some insights for the design of effective 2D compressors.