有没有比较不暴力的算法,可以把一群字符串["abcd", "bcde", "cdeab"]
压缩成(["abcdeab"], [(0, 4), (1, 5), (2, 7)])
呢。
1
zagfai 2021-09-24 01:34:19 +08:00
条件没说清楚。
另外,单顺序接龙的时间复杂度都是 O(nm)了,n 个字符串,每个 m 大小。 然后接龙了再找自串,又是一个 O(nm)了。 快不了吧? |
3
also24 2021-09-24 01:35:31 +08:00
可以看一下 LZ77
|
4
nvkou 2021-09-24 02:16:17 +08:00 via Android
稍微想了下可以几个手段入手
编码和字符集。压缩字符集使数据重新映射,每个字符少 2 个 bit ? 词频字典重映射。就是看值不值得替换长词语 以上都没有回答你问题,只是突然想到 至于你的问题,是找子串吧 |
5
ldm0 OP |
6
also24 2021-09-24 02:53:02 +08:00
@ldm0 #5
你的样例用 LZ77 的思路可以得到几乎一致的结果(循环越界部分其实也很容易变通)。 我觉得你选择的这个样例,很难完全表达出你的思想。 根据你后面的回复,我的猜测是,你想通过一些手段,让 LZ77 的字典能覆盖到最多的子串? 那这样,实际上就是 LZ77 + Huffman,也就是 DEFLATE 了。 另:我不太能理解你说的 "在内存里面连续出现" 这一条,这似乎和压缩关联不大; |
7
elfive 2021-09-24 07:19:07 +08:00 via iPhone
lzma 压缩算法
|
8
Building 2021-09-24 08:55:42 +08:00 via iPhone
转成 Data 再 gzip 一下不就好了。
|
9
zagfai 2021-09-24 11:58:25 +08:00
@ldm0 你这个条件。。直接把前面的字符串拼接起来就可以了,但那就算不上压缩了。这个压缩本质上是你要确认这些字串有多大比例的重叠,是大比例重叠才有有效的算法。
|
10
2i2Re2PLMaDnghL 2021-09-24 14:01:27 +08:00
你是要压缩常量字符串到 .data ?
其实还是正常压缩运行时解压方便 你在寻求一种排列,使得其顺次合并后的字符串最短? 朴素算法 O(n!) ,估计是 NP 问题 你还是搞个退火算法吧( |
11
islandempty 2021-09-24 14:29:54 +08:00
lz77 或 lz78 吧,
|
12
ldm0 OP |