[问] 压缩一群字符串的算法

[ldm0]

有没有比较不暴力的算法，可以把一群字符串["abcd", "bcde", "cdeab"] 压缩成(["abcdeab"], [(0, 4), (1, 5), (2, 7)])呢。

[zagfai]

条件没说清楚。
另外，单顺序接龙的时间复杂度都是 O(nm)了，n 个字符串，每个 m 大小。
然后接龙了再找自串，又是一个 O(nm)了。
快不了吧？

[DoctorCat]

了解：哈夫曼编码的应用

[also24]

可以看一下 LZ77

[nvkou]

稍微想了下可以几个手段入手
编码和字符集。压缩字符集使数据重新映射，每个字符少 2 个 bit ？
词频字典重映射。就是看值不值得替换长词语

以上都没有回答你问题，只是突然想到
至于你的问题，是找子串吧

[ldm0]

@zagfai 条件是把多个字符串结合成一个字符串，操作之后每一个原字符串都能在最后的大长字符串中以连续子串的形式找到。
@also24 粗浅的看了一下，用了字典之后应该就无法满足连续子串的要求了。
@nvkou 压缩的确有不少已知办法，字典什么的都很高效，但是某些情况就是需要尽可能的压缩字符串，同时也保证能够在内存里面连续出现（比如说如果不连续就经常不能被直接放进语言内置的字符串类型中了）。

[also24]

@ldm0 #5
你的样例用 LZ77 的思路可以得到几乎一致的结果（循环越界部分其实也很容易变通）。
我觉得你选择的这个样例，很难完全表达出你的思想。

根据你后面的回复，我的猜测是，你想通过一些手段，让 LZ77 的字典能覆盖到最多的子串？
那这样，实际上就是 LZ77 + Huffman，也就是 DEFLATE 了。

另：我不太能理解你说的 "在内存里面连续出现" 这一条，这似乎和压缩关联不大；

[elfive]

lzma 压缩算法

[Building]

转成 Data 再 gzip 一下不就好了。

[zagfai]

@ldm0 你这个条件。。直接把前面的字符串拼接起来就可以了，但那就算不上压缩了。这个压缩本质上是你要确认这些字串有多大比例的重叠，是大比例重叠才有有效的算法。

[2i2Re2PLMaDnghL]

你是要压缩常量字符串到 .data ？
其实还是正常压缩运行时解压方便

你在寻求一种排列，使得其顺次合并后的字符串最短？
朴素算法 O(n!) ，估计是 NP 问题
你还是搞个退火算法吧（

[islandempty]

lz77 或 lz78 吧，

[ldm0]

@2i2Re2PLMaDnghL 完全是这样（
@zagfai 是的，就是在认为这些字串有很大比例重叠的情况下考虑有没有这种压缩算法。

[zagfai]

@ldm0 没有这种压缩算法。