我自己想出了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
它看起来很适合压缩,但并不是我想要的。我需要的 更像是我示例中算法表示中的压缩 这将有:
- 后续序列(如果一个序列重复,则不会有其他序列 之间的顺序)
- 没有字典,只有循环
- 不可约
- 具有最大序列大小(这将最小化算法 代表)
- 假设嵌套循环是允许的(与我之前在 评论)
最佳答案
我从一个算法开始,该算法给出了最大序列大小。虽然它不会总是最小化算法表示,但它可以用作近似算法。或者可以推广到最优算法。
- 开始构建 Suffix array为您的文字连同 LCP array .
- 对 LCP 数组的索引数组进行排序,LCP 数组中较大元素的索引在前。这将相同长度的重复序列组合在一起,并允许以贪婪的方式处理序列,从最大序列大小开始。
- 提取后缀数组条目,按 LCP 值分组(分组是指具有选定 LCP 值的所有条目以及具有较大 LCP 值的所有条目),并按文本中的位置对它们进行排序。
- 过滤掉位置差异不等于 LCP 的条目。对于剩余条目,获取长度等于 LCP 的前缀。这给出了文本中所有可能的序列。
- 将按起始位置排序的序列添加到有序集合(例如,二叉搜索树)。序列按排序的 LCP 中的出现顺序添加,因此首先添加较长的序列。仅当序列是独立的或其中一个完全嵌套在另一个中时才添加序列。相交的间隔将被忽略。例如,在
caba caba bab
序列ab
与caba
相交,因此它被忽略。但是在cababa cababa babab
中,一个ab
的实例被删除,2 个实例完全在更大的序列内,2 个实例完全在它之外。 - 最后,这个有序集合包含生成算法表示所需的所有信息。
示例:
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。 .
然后从最小的序列开始,递归地确定包含任何嵌套序列的所有序列的算法表示长度。当评估每个序列时,计算整个文本的最佳算法表示。处理序列或整个文本的算法使用动态规划:分配列数等于文本/序列长度和行数的矩阵,等于算法表示的长度;对区间树进行有序遍历,用所有序列更新这个矩阵,可能对每个文本位置;当某些单元格可能有多个值时,选择其中任何一个,或者优先考虑更长或更短的子序列。
关于string - 循环滚动算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13182477/