将序列中的重复分组的算法

Question

给定一个数字序列，例如:1, 2, 1, 2。
是否有任何众所周知的算法来检测重复并将它们组合在一起，以便生成的序列具有尽可能短的大小？

例如，对于前面的序列，结果将是 (1, 2)x2。

更多例子:

Input: 1, 1, 1, 2, 1, 1, 1, 2
Output: ((1)x3, 2)x2

Input: 1, 2, 1, 2, 1, 2
Output: (1, 2)x3

Input: 1, 1, 1, 2, 1, 2
Output: (1)x2, (1, 2)x2

编辑:
结果的长度(例如 (1, 2)x2 )不包括任何关于分组和重复的辅助信息(即忽略 (),x 和后面的数字x).

比如(1, 2)x2的长度实际上是2。((1)x3, 2)x2 的长度仍然是 2，因为我们只考虑属于原始序列的元素数量(在本例中为 1 和 2)。

Answer 1

可以使用动态规划的方法。让我们将 n 定义为长度输入序列，并将 DP[i][j] 定义为子字符串将被压缩的最小可能长度，以索引 i< 开头 并以索引 j 结尾。那么有两种情况:

• 始终粘附:DP[i][j] = min(DP[i][k] + DP[k + 1][j]) 对于所有 k 从 i 到 j - 1;

• repetitions: DP[i][j] = min(DP[i][k]) 对于所有这样的 k 都是一个子串 i..j 到长度相同的子字符串 k - i + 1。我认为最小值将是 k 的最低可能值。

在两个选项中，选择最小值。字符串本身也可以恢复(它可以额外存储并重新计算)。从 1 到 n 的所有 i 的初始数据 DP[i][i] = 1。答案在 DP[1][n] 中(如果使用 1 索引数组)。