时间戳

首页 > 解决方案 > 在序列中对重复进行分组的算法

algorithm - 在序列中对重复进行分组的算法

问题描述

给定一个数字序列，例如：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）。

标签： algorithmcompression

解决方案

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

  • 始终如一地粘合：DP[i][j] = min(DP[i][k] + DP[k + 1][j])for all kfrom ito j - 1;

  • 重复：DP[i][j] = min(DP[i][k])对于所有这些k将子字符串划分i..j为相同的子字符串长度k - i + 1。我认为最小值将是可能的最低值k。

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

推荐阅读