Dorst-Smeulders Coding for Arbitrary Binary Words

doi:10.1007/978-3-032-05228-5_5

2026-01-01

PRE

De Luca, Alessandro

Gabriele Fici *

DOI：10.1007/978-3-032-05228-5_5

原文链接

原文求助

摘要

En 中文

二元字是斯图尔米安的，如果每个字母的出现是平衡的，即在任意两个相同长度的因子中，相同字母出现次数的差值最多为1。在数字几何中，斯图尔米安字对应于欧几里得平面中直线段的离散近似。1984年引入的Dorst-Smeulders编码是一个四元整数组，能够唯一表示一个斯图尔米安字w，并可通过|w|次模运算实现其重构，使其在实践中具有很高的效率。在本文中，我们提出了一种线性时间算法，该算法给定一个二元输入字w，计算其最长斯图尔米安前缀的Dorst-Smeulders编码。这构成了计算任意二元字w的Dorst-Smeulders编码的基础，该编码是w分解为斯图尔米安字的最小分解（以因子数量为标准），每个斯图尔米安字由其Dorst-Smeulders编码表示。这种编码可用于压缩方案中，将输入转换为由长斯图尔米安段组成的二元字。尽管该算法概念上简单且仅需几行代码即可实现，但其基于对斯图尔米安字结构属性的深度分析。

Keyword:

Sturmian word

Factorization

Dorst-Smeulders coding