string - 循环滚动算法

Question

我自己想出了loop rolling这个词，希望它能做到不与现有术语重叠。基本上我想想出一个在打印文本中查找循环的算法。

一些从简单到复杂的例子

例子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

它没有让我想起我所知道的任何算法。我觉得有些问题可能是模棱两可的，但找到一种解决方案对我来说就足够了现在。效率总是受欢迎的，但不是强制性的。我该怎么做？

编辑

首先，感谢大家的讨论。我采用了 LZW 算法来自 rosetta并在我的输入:

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

它看起来很适合压缩，但并不是我想要的。我需要的更像是我示例中算法表示中的压缩这将有:

• 后续序列(如果一个序列重复，则不会有其他序列之间的顺序)
• 没有字典，只有循环
• 不可约
• 具有最大序列大小(这将最小化算法代表)
• 假设嵌套循环是允许的(与我之前在评论)

Answer 1

我从一个算法开始，该算法给出了最大序列大小。虽然它不会总是最小化算法表示，但它可以用作近似算法。或者可以推广到最优算法。

1. 开始构建 Suffix array为您的文字连同 LCP array .
2. 对 LCP 数组的索引数组进行排序，LCP 数组中较大元素的索引在前。这将相同长度的重复序列组合在一起，并允许以贪婪的方式处理序列，从最大序列大小开始。
3. 提取后缀数组条目，按 LCP 值分组(分组是指具有选定 LCP 值的所有条目以及具有较大 LCP 值的所有条目)，并按文本中的位置对它们进行排序。
4. 过滤掉位置差异不等于 LCP 的条目。对于剩余条目，获取长度等于 LCP 的前缀。这给出了文本中所有可能的序列。
5. 将按起始位置排序的序列添加到有序集合(例如，二叉搜索树)。序列按排序的 LCP 中的出现顺序添加，因此首先添加较长的序列。仅当序列是独立的或其中一个完全嵌套在另一个中时才添加序列。相交的间隔将被忽略。例如，在 caba caba bab 序列 ab 与 caba 相交，因此它被忽略。但是在 cababa cababa babab 中，一个 ab 的实例被删除，2 个实例完全在更大的序列内，2 个实例完全在它之外。
6. 最后，这个有序集合包含生成算法表示所需的所有信息。

示例:

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 个步骤开始。第五步应该修改。现在不可能忽略相交的间隔，所以每个序列都被添加到集合中。由于集合现在包含相交区间，因此最好将其实现为某种高级数据结构，例如 Interval tree。 .

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