主页 / 问题 / 598621
Accepted
Majestio
Asked:2020-12-02 18:37:05 +0000 UTC2020-12-02 18:37:05 +0000 UTC

最佳文本压缩算法

  • 772

每年，压缩算法都会得到改进，出现一些新的东西，或者对现有的算法进行修改。

问题：

目前存在的 2016 年文本信息压缩算法中的哪一个给出了最好的结果（自然地，没有损失）？

此外：

  • 文本将自己表示为一组来自拉丁文、西里尔文、标点符号的字符 - 来自 ASCII（cp866 或 win-1251），也许伪图形也将是
  • 相同的字符集，但以 ru_RU.UTF-8 编码呈现

目前为止，听说过，但是时间比较长，PPMd，PPMz算法。还有更完美的东西吗？

алгоритм

3 个回答

  1. Best Answer

    这个问题的最佳答案是在encode.ru 论坛上提问。我个人并没有非常密切地关注它，所以随便：paq8px、emma、cmix（每个在论坛上都有自己的主题）。此外，预处理——字典替换（xml-wrt）、Grabowski tricks。请记住，文本必须足够大（好吧，至少数百 KB）并且压缩/解压缩速度可以在几 kb / s 的范围内，并且在不影响压缩的情况下不可能进行多线程处理。

    实际上，您提供的链接http://mattmahoney.net/dc/text.html对您的问题给出了相当详尽的答案。该级别的所有算法都在 encode.ru 论坛上收到分支，并由 Mutt 在英语维基百科的文本上进行测试。

    是的，语言/编码（假设它是 8 位）只对字典预处理器很重要——它们通常只适用于拉丁语。其余算法适用于任何语言。

    如果您真正想要的不是最大压缩率，而是速度和压缩率的最佳组合，那么对于文本我更喜欢bsc，尤其是因为它是唯一能够使用 GPU 的通用压缩库。

    • 9

  2. 我试图压缩“战争与和平”（从这里）

    $ 7za a -mm=deflate -mx9 -- war_and_peace.txt.deflate.7z 
$ 7za a -mm=bzip2 -mx9 -- war_and_peace.txt.bz2.7z war_and_peace.txt
$ 7za a -mm=lzma2 -mx9 -- war_and_peace.txt.lzma2.7z war_and_peace.txt
$ 7za a -mm=ppmd -mx9 -- war_and_peace.txt.ppmd.7z war_and_peace.txt
$ dir
1 473 547 war_and_peace.txt
  577 577 war_and_peace.txt.deflate.7z
  481 030 war_and_peace.txt.lzma2.7z
  445 240 war_and_peace.txt.bz2.7z
  391 270 war_and_peace.txt.ppmd.7z

    可以看出PPMd在战争与和平上最有效。
    接下来是 BZ2，然后是 LZMA2 和 Deflate。

    我试过 cmmix。他真的吃掉了36GB内存，压缩了43分钟。

    $ cmix -c war_and_peace.txt war_and_peace.txt.cmix
1473547 bytes -> 348461 bytes in 2633.81 s.
cross entropy: 1.892

    它也有带字典（拼写）的模式，但只包含约 45,000 个英语单词的字典。

    然而，这些都是相当古老且广为人知的算法。或许还有别的，更适合题主需要压榨的课文。

    闲来无事，就把《战争与和平》拆成文字，用霍夫曼编码。结果444Kb不算表。那些。这是个坏主意。

    >>> text = open(r'c:\_tmp\war_and_peace.txt', 'rb').read().decode('cp1251')
>>> import re
>>> words = re.findall(r'(\w+|.)', text)
>>> len(text), len(words)
(1473547, 534395)
>>> def huffman_table(symbols):
    import collections
    freq = collections.defaultdict(int)
    for s in symbols: freq[s] += 1
    roots = [(f,[(s,'')]) for s,f in freq.items()]
    while True:
        roots.sort()
        (f0,t0),(f1,t1),tail=roots[0],roots[1],roots[2:]
        table=[(s,'0'+c) for s,c in t0]+[(s,'1'+c) for s,c in t1]
        if len(tail) == 0:
            return dict(table)
        roots = tail+[(f0+f1,table)]


>>> table = huffman_table(words)
>>> len(table)
35421
>>> def huffman_encode(symbols, table):
    buffer = ''
    out = bytearray()
    for s in symbols:
        buffer += table[s]
        while len(buffer) >= 8:
            b, buffer = buffer[:8], buffer[8:]
            out.append(int(b, 2))
    size = len(out)*8+len(buffer)
    if len(buffer) != 0:
        out.append(int(buffer, 2))
    return out, size

>>> encoded, size_bits = huffman_encode(words, table)
>>> size_bits/8
454533.75
    • 8

  3. 一张图片的八位表示，通常这可以减少。（当然，我的意思是字符的八位表示）。如果文本是双语预处理：减少字母 - 使用字符匹配 t=t g=g L=L 等。并在文本中用拉丁语表示文本开始和结束的标记。另一种方法是不使用符号，而是使用音节作为文本编码的单位（以完成诗歌和文本）；如果我没记错的话，30% 的音节占文本的 70-75%。另外，朋友们，有点题外话的提醒——有“有损”压缩方法，恢复后可以提供很高的准确性！最后：为了最大程度地压缩文本，应使用与艺术类别的文件规范（文本片段的规范）相对应的算法。文学或技术 一位作者的文学或文本，

    • 0

相关问题