algorithm - 找到提供最佳压缩的前缀子字符串

Question

问题：

给定一个字符串列表，找到子字符串，如果从它匹配的所有字符串的开头减去它并用转义字节替换，则得到最短的总长度。

例子：

"foo", "fool","bar"

结果是： "foo" 作为带有字符串 、 和总长度为 9 个字节的"\0"基本"\0l"字符串"bar"。"\0"是转义字节。原始字符串的长度之和是 10，所以在这种情况下我们只保存了一个字节。

一个朴素的算法看起来像：

for string in list
  for i = 1, i < length of string
      calculate total length based on prefix of string[0..i]
      if better than last best, save it
return the best prefix

这会给我们答案，但它有点像 O((n*m)^2)，太贵了。

Answer 1

使用前缀树的森林（特里）...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

然后，我们可以通过最大化(depth * frequency)将替换为您的转义字符来找到最佳结果并保证它。您可以通过执行分支和绑定深度优先搜索最大值来优化搜索。

关于复杂性：O（C），如评论中所述，用于构建它并找到最优值，这取决于。如果您订购第一个元素的频率（O(A) - 其中 A 是语言字母表的大小），那么您将能够切出更多的分支，并且很有可能获得次线性时间。

我想这很清楚，我不会写出来——这是什么家庭作业？;)

Answer 2

我会尝试从对列表进行排序开始。然后，您只需从一个字符串到另一个字符串，将第一个字符与下一个字符串的第一个字符进行比较。一旦你有一个匹配，你会看下一个字符。您需要设计一种方法来跟踪迄今为止的最佳结果。

Answer 3

好吧，第一步是对列表进行排序。然后遍历列表，将每个元素与前一个元素进行比较，跟踪最长的 2 字符、3 字符、4 字符等运行。那么数字是 20 个 3 字符前缀优于 15 个 4 字符前缀。