循环滚动算法

Question

我想出了术语“循环滚动”，希望它不会与现有术语重叠。基本上，我正在尝试设计一种算法来查找印刷文本中的循环。

一些例子从简单到复杂

示例1

给定：

a a a a a b c d

我想说：

5x(a) b c d

或者通过算法：

for 1 .. 5
    print a
end
print b
print c
print d

示例2

假设：

a b a b a b a b c d

我想说：

4x(a b) c d

或者通过算法:

for 1 .. 4
    print a
    print b
end
print c
print d

示例3

已知：

a b c d b c d b c d b c e

我想说：

a 3x(b c d) b c e

或者通过算法：

print a
for 1 .. 3
    print b
    print c
    print d
end
print b
print c
print d

这并不让我想起我所知道的任何算法。我觉得有些问题可能会存在歧义，但是找到其中一个解决方案对我来说已经足够了。效率总是受欢迎的，但不是必须的。我该怎么做？

编辑

首先，感谢所有的讨论。我从rosetta中采用了一个LZW算法，并在我的输入上运行它：

abcdbcdbcdbcdef

这给了我：

a
b
c
d
8  => bc
10 => db
9  => cd
11 => bcd
e
f

我有一个字典，其中包含：

a a
c c
b b
e e
d d
f f
8 bc
9 cd
10 db
11 bcd
12 dbc
13 cdb
14 bcde
15 ef
7 ab

压缩效果不错，但不完全符合我的要求。我需要更像是从示例中算法表示的压缩，它应该有：

• 后续序列（如果一个序列重复，中间不会有其他序列）
• 没有字典，只有循环
• 不可简化
• 具有最大序列大小（这将最小化算法表示）
• 假设嵌套循环是允许的（与我之前在评论中说的相反）

- none

---

这非常类似于Lempel–Ziv–Welch算法。 - Evgeny Kluev

gokcehan - 嵌套循环允许吗？ - Ted Hopp

本质上，这是关于压缩和 Kolmogorov 复杂性边界的问题。 - phant0m

@TedHopp：我认为有趣的情况是那些无法通过贪心组合得到正确结果的情况，比如 a b a b a b a b c d e a b c d e，你真正想要的是 3(a b) 2(a b c d e) 而不是 4(a b) c d e a b c d e。 - rici

@icepack - 那个问题忽略了当前问题的核心难点：如何识别这些组。 （在您链接到的问题中，这些组已经确定。） - Ted Hopp

Answer 1

我从一个算法开始，它可以给出最大序列大小。虽然它并不总是能够最小化算法表示，但它可以用作近似算法。或者它可以扩展为最优算法。

开始构建后缀数组和LCP数组。

对LCP数组的索引数组进行排序，较大元素的索引先出现。这将相同长度的重复序列分组在一起，并允许以贪心的方式处理序列，从最大序列大小开始。

提取后缀数组条目，按LCP值（通过组我指的是选择的LCP值以及所有具有更大LCP值的条目）进行分组，并按文本中的位置进行排序。

过滤掉位置差异不等于LCP的条目。对于剩余的条目，获取长度为LCP的前缀。这给出了文本中所有可能的序列。

将序列按起始位置排序，添加到有序集合中（例如二叉搜索树）。序列按照排序后的LCP出现顺序添加，因此较长的序列首先添加。仅当它们是独立的或其中一个完全嵌套在另一个序列中时，才添加序列。交叉间隔被忽略。例如，在序列ab与coda相交，因此被忽略。但在cababa cababa babab中，ab的一个实例被删除，2个实例完全在较大序列中，2个实例完全在较大序列之外。

最后，这个有序集合包含了所有需要生成算法表示的信息。

Example:

Text          ababcabab

Suffix array  ab abab ababcabab abcabab b bab babcabab bcabab cabab
LCP array       2    4         2       0 1   3        1      0

Sorted LCP            4 3 2 2 1 1 0 0
Positional difference 5 5 2 2 2 2 - -
Filtered LCP          - - 2 2 - - - -
Filtered prefixes   (ab ab) (ab ab)

---

一个算法草图，生成最小的算法表示。

从先前算法的前4个步骤开始。第五步应该被修改。现在不可能忽略相交的区间，因此每个序列都添加到集合中。由于集合现在包含相交的区间，最好将其实现为一些高级数据结构，例如区间树。

然后递归确定包含任何嵌套序列的所有序列的算法表示长度，从最小的序列开始。当评估完每个序列时，计算整个文本的最优算法表示。处理序列或整个文本的算法使用动态规划：分配一个矩阵，列数等于文本/序列长度，行数等于算法表示的长度；按顺序遍历区间树，在每个文本位置更新此矩阵与所有可能的序列；当某个单元格有多个值可选时，选择其中任何一个，或者更喜欢较长或较短的子序列。

- Evgeny Kluev

---

这看起来差不多正确，但由于输入很小，我现在已经使用了正则表达式。如果我们需要更好的性能，我会尝试一下这个方法，谢谢。 - none