Методы сжатия данных

[@nvv]

это должен знать каждый

[@agorkov]

Практика показывает, что это далеко не всегда так.

[@nvv]

полностью согласен

[@MichaelBorisov]

Патентная защита методов арифметического кодирования не означает запрет на описание этих методов. Собственно описание является публично доступным (в тексте патента). Запрещается только реализация и использование.

[@horlon]

Если не ошибаюсь, то патент на момент написании этой статьи уже истёк...

[@MacIn]

О, в тему.
Релизовывал недавно для интереса сжатие по алгоритму LZW, полученные коды кодировал переменной длиной по Хаффману. Что меня удивило, так это то, что на примерах простых текстов с очень большим количеством повторений, сжатие не было таким уж эффективным по сравнению с другими алгоритмами. Например, файл лога, в котором очень много повторений (пути файлов и т.д.) при кодировании LZW+Huffman файл длиной 83729 байт ужался до 11568. Вроде, неплохой результат, но 7z или gzip (алгоритм deflate?) ужимают тот же файл до 3906 байт с учетом заголовка архива. Т.е. практически втрое сильнее.

При сжатии EXE файла, 45056 байт ужались моей реализацией до 27788, gzip'ом — до 21518.

Неужели может быть такой разброс? Хороших статей на тему сравнения эффективности алгоритмов именно для связки lzw+huffman не видел. Кто-лбио встречал такое сравнение? Имеет собственный опыт?

[@ZyXI]

Для текстов обычно лучше всего подходут PPMD. 7z умеет сжимать им (при явном указании и с контейнером .7z). Есть отдельная программа, умеющая только PPMD в свой формат, но она какая-то нестабильная (может не расжать).

В PPMD сжатие текстов происходит быстро и с хорошим коэффициентом (насколько я помню, на сжатии лога сборки OpenOffice PPMD превосходили по коэффициенту только PAQ8 и, возможно, xz -9; дойду до своего ПК, посмотрю).

[@ZyXI]

Нет. Лог файл сборки OpenOffice сжался 7z -m0=ppmd -mx=9 от 14 МиБ до 430 КиБ. Лучше только zpaq, методами 6, 8 и 8a, но он работает так доооолго (286, 286 и 389 КиБ соответственно, возможно, почитав справку, можно сделать лучше), а также «архиватор» от самих авторов PAQ (работает ещё дольше).

xz -9 выдал всего 564 КиБ (lzma -9 — 515 КиБ), при том был в четыре раза медленнее (на старой машине lzma -9 был на порядок медленнее 7z -m0=ppmd -mx=9). Если интересно, то вот все результаты: yadi.sk/d/YWOMe81KesS4A. Время и использованные команды смотреть в файле txt, но учтите, что сравнивать времена между дефисоминусами‐разделителями смысла нет, так как они от разных конфигураций (или не от разных, но наличие какого‐либо смысла в сравнении я не гарантирую).

[@kampaster]

MacIn Хороших статей на тему сравнения эффективности алгоритмов именно для связки lzw+huffman не видел. Кто-лбио встречал такое сравнение?>>

Что-то вроде этого?
www.ijser.org/onlineResearchPaperViewer.aspx?Data-Compression-using-Huffman-based-LZW-Encoding-Technique.pdf

[@MacIn]

Ссылка хорошая, спасибо. Но я имел в виду сравнение комбинации Huffman и LZW c другими алгоритмами.

[@impwx]

Искренне удивили примеры на паскале, в 2015 году не ожидал увидеть такое на хабре.
Статья же интересная и наглядная, спасибо.

[@rtzra]

Опять началось… Паскаль строгий язык с типизацией, даже если его кто-то не знает то легко сможет быстренько переписать приведенный код на любой язык. И потом, чем плох Паскаль? Тем что он нынче не мэйнстрим и стал немоден? Сейчас столько языков разной степени направленности что можно выбирать наиболее подходящий и не заводить холивары.

[@andymitrich]

Дык, никто ж не говорил, что Паскаль — плохой язык. У человека просто вызвало удивление его использование, только и всего.

[@MacIn]

А что, собственно, удивительно? Кого-то искренне удивляет использование его? Меня искренне удивляет такое удивление.

[@ForhaxeD]

Паскаль (и дальнейшие развитие в виде Delphi) — это мертвый язык, как латиница, например.
Сейчас же ведь существуют масса хороших языков для написания «быстрого» кода и для обучения.
P.S. не устраиваю холивар.

[@agorkov]

Мне кажется несколько преждевременно называть язык, который активно развивается и на котором создаётся множество новых проектов мёртвым.

[@MacIn]

Его до сих пор используют на первых курсах при обучении азам программирования. Язык как язык.
И что считать «мертвым»? Delphi выпускается, новые среды выходят регулярно, фреймворки под все что угодно, в том числе мобильные устройства, есть.

[@ForhaxeD]

Почему бы не использовать для обучения азам какой-нибудь Python? Почему выбор пал именно на Delphi (Pascal)?

[@MacIn]

Потому что он был еще тогда, когда питона не было в проекте. Есть программа, есть пособия. Все, что надо знать на первом курсе, Pascal дает с лихвой.

[@pkalinin]

Но на практике эффективность зависит от выбранного алгоритма сортировки. Тривиальные алгоритмы с квадратичной сложностью, очевидно, крайне негативно скажутся на быстродействии, поэтому рекомендуется использовать эффективные алгоритмы

Ну или вообще ничего не говорите про сложность (претендуя только на объяснение идеи, но не на объяснение эффективной реализации), либо уж честно скажите, что эффективные методы BWT работают слегка по-другому, не подразумевая выписывания матрицы сдвигов вообще. Насколько я понимаю, обратное преобразование тоже делается линейно, поэтому утверждение про "… но также сильно увеличивает время работы (особенно декодирования)" не очень понятно.