Лучшие алгоритмы сжатия текста

#алгоритм #сжатие

С каждым годом алгоритмы сжатия совершенствуются, появляется что-то новое, или модификация
существующих.

Вопрос: 

Какие из ныне существующих, на 2016 год, алгоритмов сжатия текстовой информации дают
лучший результат (естественно, без потерь)?

Дополнительно:


текст будет представлять себя наборы символов латиницы, кириллицы, знаков препинания
- из ASCII (cp866 или win-1251), возможно еще псевдографика будет
те же наборы символов, но представленные в кодировке ru_RU.UTF-8


Пока на слуху, но это уже относительно давно, алгоритм PPMd, PPMz. Есть что-то более
совершенное?
    

Ответы

Ответ 1

Лучший ответ на этот вопрос - спросите на форуме encode.ru. Я лично не слежу за этим
совсем уж пристально, поэтому навскидку: paq8px, emma, cmix (у каждого есть своя ветка
на форуме). Кроме этого, препроцессинг - словарная замена (xml-wrt), трюки Grabowski.
Имейте в виду, что тексты должны быть достаточно велики (ну хотя бы сотни килобайт)
и скорость сжатия/распаковки может быть в районе нескольких кб/с, а многопоточность
невозможна без ухудшения сжатия.

Собственно приведённая вами же ссылка http://mattmahoney.net/dc/text.html даёт достаточно
исчерпывающий ответ на ваш вопрос. Все алгоритмы такого уровня получают ветки на форуме
encode.ru и тестируются Маттом на тексте английской википедии.

Да, язык/кодировка (при условии что она 8-битная) имеют значение только для словарных
препроцессоров - они обычно работают только с латиницей. Остальные алгоритмы хорошо
работают с любыми языками.

Если же вам на самом деле нужно не максимальное сжатие, а оптимальное сочетание скорости
и степени сжатия, то для текстов я предпочитаю bsc, тем более что это единственная
библиотека сжатия общего назначения, способная использовать GPU.


Ответ 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.



Попробовал cmix. Он действительно жрет 36 Гб памяти и сжимал 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 тыс. английских слов.



Впрочем это довольно старые и широко известные алгоримы. Возможно существует что-то
другое, более подходящее для текстов которые надо сживать автору вопроса.



Мне нечего было делать, и я разбил "Войну и Мир" по словам и закодировал их Хаффманом.
Получилось 444Кб не считая таблицу. Т.е. это была плохая идея.

>>> 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