这是一个专门讨论 idea 的地方。
每个人的时间，资源是有限的，有的时候你或许能够想到很多 idea，但是由于现实的限制，却并不是所有的 idea 都能够成为现实。
那这个时候，不妨可以把那些 idea 分享出来，启发别人。
每个人的时间，资源是有限的，有的时候你或许能够想到很多 idea，但是由于现实的限制，却并不是所有的 idea 都能够成为现实。
那这个时候，不妨可以把那些 idea 分享出来，启发别人。
这是一个创建于 1155 天前的主题，其中的信息可能已经有所发展或是发生改变。
有没有比较不暴力的算法，可以把一群字符串["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 |
Select Language