想象一下我有一组字符串，例如：
"entrance",
"scent",
"transcend".
我想找到可用于构建初始字符串的子字符串的最佳“词典”。标准是存储词典和使用该词典的字符串所需的最小内存量。
例如，对于给定的字符串集，子字符串的最佳词典可能是：
"scen" = 1,
"tran" = 2,
"en" = 3,
"ce" = 4,
"t" = 5,
"d" = 6
使用以下方式编码的初始字符串集（每个\N表示对词典中字符串 N 的引用）：
\3\2\4
\1\5
\2\1\6
用于构建字符串的总共 8 个引用 + 存储词典所需的 14 个字符，而原始字符串中的 22 个字符 + 包含原始字母表的 8 个字符。如果您需要一个精确的足迹公式，假设sizeof( reference ) == sizeof( char )，并且单个字符串（编码和词典中）的足迹是length of string * sizeof( char or reference )，没有额外的开销。
解决这个问题的最佳算法是什么？这个算法有固定的名字吗？NP难吗？如果是这样，是否存在次优但多项式的解决方案？
编辑：我能想出的最佳解决方案如下：在初始字符串集中找到最长的公共子字符串。让该子字符串的分数为 ，说明(substring_length - 1) * total_occurrences_of_it_in_the_set - substring_length该替换保存的字符/引用的数量。现在找到所有较小的子字符串（直到长度为 2）并以相同的方式计算它们的分数。在以这种方式找到的所有子字符串中，得分最高的子字符串获胜并进入词典。然后子字符串在初始字符串集中被对它的引用替换，并且该过程重复，直到我们的字符串集仅包含单个字符和词典引用。之后，将所有剩余的单个字符引入词典，并用它们在集合中的引用替换它们。打分的解释如下：我们去掉substring_length每次出现的字符，添加一个引用（因此-1），并且需要substring_length字符来存储子字符串（因此-substring_length）。
你能想到什么更好的方法吗？