algorithm - 基于字典的压缩算法的最佳子串选择

Question

我有一个字符串需要用字典压缩算法进行压缩。如果在字典中找到了一个子串，它的编码成本为 2。如果没有找到匹配，成本将是该子串的大小。 给定一个固定的字典和一个字符串，我怎样才能在字典中选择最好的子字符串从而使成本最小？

例如，考虑字符串 ABBBBBCD 和以下字典:

• 条目 1 - ABBB
• 条目 2 - BBCD
• 条目 3 - BBBBB
• 条目 4 - ABBBB
• 条目 5 - CD

最佳方案是选择 ABBB 和 BBCD，成本为 2 + 2 = 4。

如果我选择 A、BBBBB、C 和 D，成本将是 1 + 2 + 1 + 1 = 5，这比第一个更差。

然而，如果我选择 ABBBB、B、CD，成本将为 2 + 1 + 2 = 5。

在解释之后，我的问题是:是否有解决此问题的已知算法？或者，是否有一些已知的算法可以修改，以便我可以不使用暴力方法解决问题？

请问我是否有不清楚的地方。

Answer 1

您可以将其表述为最短路径问题并加以解决。

创建一个以每个索引为顶点的图。现在添加一条从 i 到 j 的有向边(i

现在找到从索引 1 到 n 的最短路径。 (参见:http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/)