V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
ldm0
V2EX  ›  奇思妙想

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

  •  
  •   ldm0 · 2021-09-24 01:21:59 +08:00 · 2017 次点击
    这是一个创建于 917 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    13 条回复    2021-09-24 14:55:01 +08:00
    zagfai
        1
    zagfai  
       2021-09-24 01:34:19 +08:00
    条件没说清楚。
    另外,单顺序接龙的时间复杂度都是 O(nm)了,n 个字符串,每个 m 大小。
    然后接龙了再找自串,又是一个 O(nm)了。
    快不了吧?
    also24
        3
    also24  
       2021-09-24 01:35:31 +08:00
    可以看一下 LZ77
    nvkou
        4
    nvkou  
       2021-09-24 02:16:17 +08:00 via Android
    稍微想了下可以几个手段入手
    编码和字符集。压缩字符集使数据重新映射,每个字符少 2 个 bit ?
    词频字典重映射。就是看值不值得替换长词语

    以上都没有回答你问题,只是突然想到
    至于你的问题,是找子串吧
    ldm0
        5
    ldm0  
    OP
       2021-09-24 02:34:30 +08:00
    @zagfai 条件是把多个字符串结合成一个字符串,操作之后每一个原字符串都能在最后的大长字符串中以连续子串的形式找到。
    @also24 粗浅的看了一下,用了字典之后应该就无法满足连续子串的要求了。
    @nvkou 压缩的确有不少已知办法,字典什么的都很高效,但是某些情况就是需要尽可能的压缩字符串,同时也保证能够在内存里面连续出现(比如说如果不连续就经常不能被直接放进语言内置的字符串类型中了)。
    also24
        6
    also24  
       2021-09-24 02:53:02 +08:00
    @ldm0 #5
    你的样例用 LZ77 的思路可以得到几乎一致的结果(循环越界部分其实也很容易变通)。
    我觉得你选择的这个样例,很难完全表达出你的思想。

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

    另:我不太能理解你说的 "在内存里面连续出现" 这一条,这似乎和压缩关联不大;
    elfive
        7
    elfive  
       2021-09-24 07:19:07 +08:00 via iPhone
    lzma 压缩算法
    Building
        8
    Building  
       2021-09-24 08:55:42 +08:00 via iPhone
    转成 Data 再 gzip 一下不就好了。
    zagfai
        9
    zagfai  
       2021-09-24 11:58:25 +08:00
    @ldm0 你这个条件。。直接把前面的字符串拼接起来就可以了,但那就算不上压缩了。这个压缩本质上是你要确认这些字串有多大比例的重叠,是大比例重叠才有有效的算法。
    2i2Re2PLMaDnghL
        10
    2i2Re2PLMaDnghL  
       2021-09-24 14:01:27 +08:00
    你是要压缩常量字符串到 .data ?
    其实还是正常压缩运行时解压方便

    你在寻求一种排列,使得其顺次合并后的字符串最短?
    朴素算法 O(n!) ,估计是 NP 问题
    你还是搞个退火算法吧(
    islandempty
        11
    islandempty  
       2021-09-24 14:29:54 +08:00
    lz77 或 lz78 吧,
    ldm0
        12
    ldm0  
    OP
       2021-09-24 14:39:45 +08:00
    @2i2Re2PLMaDnghL 完全是这样(
    @zagfai 是的,就是在认为这些字串有很大比例重叠的情况下考虑有没有这种压缩算法。
    zagfai
        13
    zagfai  
       2021-09-24 14:55:01 +08:00
    @ldm0 没有这种压缩算法。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4639 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 05:35 · PVG 13:35 · LAX 22:35 · JFK 01:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.