4

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

从简单到复杂的一些例子

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

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

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

1 回答 1

2

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

  1. 首先为您的文本构建Suffix 数组以及LCP 数组。
  2. 对 LCP 数组的索引数组进行排序，LCP 数组中较大元素的索引排在最前面。这将相同长度的重复序列组合在一起，并允许以贪婪的方式处理序列，从最大序列大小开始。
  3. 提取后缀数组条目，按 LCP 值分组（分组是指具有选定 LCP 值的所有条目以及具有较大 LCP 值的所有条目），并按文本中的位置对它们进行排序。
  4. 过滤掉位置差不等于 LCP 的条目。对于剩余的条目，获取长度等于 LCP 的前缀。这给出了文本中所有可能的序列。
  5. 将按起始位置排序的序列添加到有序集合（例如，二叉搜索树）。序列是按排序后的 LCP 中出现的顺序添加的，因此首先添加较长的序列。只有当它们是独立的或其中一个完全嵌套在另一个中时，才会添加序列。相交区间被忽略。例如，in caba caba babsequenceab与 相交，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 个步骤开始。第五步应该修改。现在不可能忽略相交间隔，因此每个序列都添加到集合中。由于集合现在包含相交区间，因此最好将其实现为一些高级数据结构，例如区间树。

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

于 2012-11-04T17:41:13.923 回答