1.12.2009, 18:22
PPMd - Prediction by Partial Matching (dynamic) - предсказание по частичному совпадению, алгоритм сжатия данных без потерь. За подробностями посылаю в Википедию, а знающих английский - в англоязычную Википедию
Алгоритм сжатия PPMd поддерживается архиватором 7-zip, по крайней мере, 4.65 (вероятно, и более ранними), и на текстовых файлах показывает существенно более высокий коэффициент сжатия, чем, например, LZMA, на котором архиватор 7-zip основан изначально.
Для алгоритма сжатия LZMA существует библиотека - LZMA SDK, предоставляющая разработчикам сторонних программ использовать алгоритм сжатия LZMA в своих целях. На её основе была создана утилита LZMA_Alone, которая позволяла сжимать и разжимать данные не только из файла в файл, но и со стандартного ввода на стандартный вывод. С этим был связан рост популярности LZMA среди пользователей UNIX-подобных операционных систем - в силу традиции процессы архивации (объединения нескольких файлов в один) и сжатия (уменьшения объёма информации) выполнялись разными утилитами - архиватором и компрессором, и нужно было со стандартного вывода архиватора передавать сигнал на стандартный ввод компрессора. В роли архиватора до сих пор используется tar, а в роли компрессора - в историческом порядке compress, gzip, bzip2. Чтобы было удобно поставить на это место LZMA, потребовалось изменить интерфейс командной строки и сделать его похожим на остальные компрессоры. Следствием этого стала gzip-подобная версия компрессора LZMA, доступная в репозитариях многих GNU/Linux систем, в FreeBSD как порт archivers/lzma и во многих других.
Как развитие поддержки поточного компрессора LZMA программами, у GNU tar появился параметр командной строки --lzma (наряду с --compress, --gzip и --bzip2). Инсталлятор пакетов dpkg на настоящий момент поддерживает tar.lzma архив в качестве представления файлов пакета. Постепенно исходные тексты программ, наряду с .tar.gz и tar.bz2 архивами, начинают распространяться в .tar.lzma архивах...
Алгоритм сжатия PPMd не получил, однако, столь широкого распространения. Его файловая версия, написанная с 1997 по 2001 г. Дмитрием Шкариным (Dmitriy Shkarin), доступна как общественное достояние и имеет весь потенциал к использованию в качестве поточного компрессора, но в самой утилите такой режим не предусмотрен.
Результаты его работы были подхвачены проектом 7zip. Так в 7-zip появилась реализация PPMd, по интерфейсу подобная реализации LZMA в нём же. Более того, интерфейс командной строки 7zip поддерживает приём данных из потока стандартного ввода и их вывод на поток стандартного вывода. Единственный недостаток такого подхода - создаётся архив формата 7zip, рассчитанный всё же на хранение нескольких файлов.
Дальнейшим развитием поддержки PPMd в 7-zip стало появление порта FreeBSD ppmd-7z (и, возможно, других аналогичных утилит), с синтаксисом командной строки, подобным 7zip, но создающих файл, непосредственно представляющий поток сжатых данных PPMd. Большим недостатком оказалась заблокированная в ней поддержка сжатия данных со стандартного ввода (хотя разжатие данных со стандартного ввода поддерживается в полной мере).
Мной были приложены усилия к созданию gzip-подобного поточного компрессора, основанного на методе PPMd. Для этого были переработаны исходные тексты P7zip 4.65, LZMA SDK 4.65 и главной функции gzip-подобной версии утилиты lzma. Результатом стала заготовка PPMd SDK, подобной LZMA SDK, и gzip-подобная утилита потокового сжатия ppmd.
Исходные тексты заготовки доступны по адресу: ftp://motoprogger.gotdns.org/ppmd-sdk/src/ . Из неё можно собрать работоспособную версию компрессора PPMd (протестировано под FreeBSD 7.2 и Debian GNU/Linux 5.0.3 `Lenny`), с некоторыми недостатками и недоработками, несколько ограничивающими её использование, но не приводящими к потере данных. Все найденные проблемы описаны в файле BUGS.txt в архиве.
В качестве перспективы использования PPMd я вижу:
1) Включение поточной версии PPMd во все распространённые UNIX-подобные операционные системы
2) Повсеместное использование PPMd для сжатия исходных текстов
3) Использование PPMd для сжатия дампов проектом Wikimedia
Тема на sourceforge.net
Приглашаю всех заинтересованных к публичному тестированию и доработке PPMd SDK и утилиты сжатия PPMd, а также к использованию алгоритма сжатия PPMd (неважно, в составе какого инструмента) для сжатия текстовых и преимущественно текстовых файлов с целью получения максимальной степени сжатия.
Результат тестирования gzip, bzip2, lzma и ppmd на сжатие исходных текстов ядра Linux версии 2.6.31.3
Довольно грязное сравнение по времени сжатия (Intel Celeron M 1,6 GHz/2GB RAM):
Сравнение степени сжатия:
Такое же "грязное" сравнение по времени разжатия:
Степень сжатия и скорость работы PPMd сильно зависят от используемой модели предсказания. Использованная в тесте (и включенная в PPMd SDK) модель оптимизирована под естественные тексты.
Алгоритм сжатия PPMd поддерживается архиватором 7-zip, по крайней мере, 4.65 (вероятно, и более ранними), и на текстовых файлах показывает существенно более высокий коэффициент сжатия, чем, например, LZMA, на котором архиватор 7-zip основан изначально.
Для алгоритма сжатия LZMA существует библиотека - LZMA SDK, предоставляющая разработчикам сторонних программ использовать алгоритм сжатия LZMA в своих целях. На её основе была создана утилита LZMA_Alone, которая позволяла сжимать и разжимать данные не только из файла в файл, но и со стандартного ввода на стандартный вывод. С этим был связан рост популярности LZMA среди пользователей UNIX-подобных операционных систем - в силу традиции процессы архивации (объединения нескольких файлов в один) и сжатия (уменьшения объёма информации) выполнялись разными утилитами - архиватором и компрессором, и нужно было со стандартного вывода архиватора передавать сигнал на стандартный ввод компрессора. В роли архиватора до сих пор используется tar, а в роли компрессора - в историческом порядке compress, gzip, bzip2. Чтобы было удобно поставить на это место LZMA, потребовалось изменить интерфейс командной строки и сделать его похожим на остальные компрессоры. Следствием этого стала gzip-подобная версия компрессора LZMA, доступная в репозитариях многих GNU/Linux систем, в FreeBSD как порт archivers/lzma и во многих других.
Как развитие поддержки поточного компрессора LZMA программами, у GNU tar появился параметр командной строки --lzma (наряду с --compress, --gzip и --bzip2). Инсталлятор пакетов dpkg на настоящий момент поддерживает tar.lzma архив в качестве представления файлов пакета. Постепенно исходные тексты программ, наряду с .tar.gz и tar.bz2 архивами, начинают распространяться в .tar.lzma архивах...
Алгоритм сжатия PPMd не получил, однако, столь широкого распространения. Его файловая версия, написанная с 1997 по 2001 г. Дмитрием Шкариным (Dmitriy Shkarin), доступна как общественное достояние и имеет весь потенциал к использованию в качестве поточного компрессора, но в самой утилите такой режим не предусмотрен.
Результаты его работы были подхвачены проектом 7zip. Так в 7-zip появилась реализация PPMd, по интерфейсу подобная реализации LZMA в нём же. Более того, интерфейс командной строки 7zip поддерживает приём данных из потока стандартного ввода и их вывод на поток стандартного вывода. Единственный недостаток такого подхода - создаётся архив формата 7zip, рассчитанный всё же на хранение нескольких файлов.
Дальнейшим развитием поддержки PPMd в 7-zip стало появление порта FreeBSD ppmd-7z (и, возможно, других аналогичных утилит), с синтаксисом командной строки, подобным 7zip, но создающих файл, непосредственно представляющий поток сжатых данных PPMd. Большим недостатком оказалась заблокированная в ней поддержка сжатия данных со стандартного ввода (хотя разжатие данных со стандартного ввода поддерживается в полной мере).
Мной были приложены усилия к созданию gzip-подобного поточного компрессора, основанного на методе PPMd. Для этого были переработаны исходные тексты P7zip 4.65, LZMA SDK 4.65 и главной функции gzip-подобной версии утилиты lzma. Результатом стала заготовка PPMd SDK, подобной LZMA SDK, и gzip-подобная утилита потокового сжатия ppmd.
Исходные тексты заготовки доступны по адресу: ftp://motoprogger.gotdns.org/ppmd-sdk/src/ . Из неё можно собрать работоспособную версию компрессора PPMd (протестировано под FreeBSD 7.2 и Debian GNU/Linux 5.0.3 `Lenny`), с некоторыми недостатками и недоработками, несколько ограничивающими её использование, но не приводящими к потере данных. Все найденные проблемы описаны в файле BUGS.txt в архиве.
В качестве перспективы использования PPMd я вижу:
1) Включение поточной версии PPMd во все распространённые UNIX-подобные операционные системы
2) Повсеместное использование PPMd для сжатия исходных текстов
3) Использование PPMd для сжатия дампов проектом Wikimedia
Тема на sourceforge.net
Приглашаю всех заинтересованных к публичному тестированию и доработке PPMd SDK и утилиты сжатия PPMd, а также к использованию алгоритма сжатия PPMd (неважно, в составе какого инструмента) для сжатия текстовых и преимущественно текстовых файлов с целью получения максимальной степени сжатия.
Результат тестирования gzip, bzip2, lzma и ppmd на сжатие исходных текстов ядра Linux версии 2.6.31.3
Spoiler:
Довольно грязное сравнение по времени сжатия (Intel Celeron M 1,6 GHz/2GB RAM):
Код
laptop:/usr/src# time gzip -9 < linux-2.6.31.3.tar > linux-2.6.31.3.tar.gz
real 1m15.344s
user 0m59.008s
sys 0m0.448s
laptop:/usr/src# time bzip2 -9 < linux-2.6.31.3.tar > linux-2.6.31.3.tar.bz2
real 3m26.029s
user 2m36.426s
sys 0m0.696s
laptop:/usr/src# time lzma -9 < linux-2.6.31.3.tar > linux-2.6.31.3.tar.lzma
real 18m20.163s
user 14m2.785s
sys 0m2.756s
laptop:/usr/src# time ppmd -9 < linux-2.6.31.3.tar > linux-2.6.31.3.tar.ppmd
real 9m28.997s
user 7m19.803s
sys 0m1.804s
real 1m15.344s
user 0m59.008s
sys 0m0.448s
laptop:/usr/src# time bzip2 -9 < linux-2.6.31.3.tar > linux-2.6.31.3.tar.bz2
real 3m26.029s
user 2m36.426s
sys 0m0.696s
laptop:/usr/src# time lzma -9 < linux-2.6.31.3.tar > linux-2.6.31.3.tar.lzma
real 18m20.163s
user 14m2.785s
sys 0m2.756s
laptop:/usr/src# time ppmd -9 < linux-2.6.31.3.tar > linux-2.6.31.3.tar.ppmd
real 9m28.997s
user 7m19.803s
sys 0m1.804s
Сравнение степени сжатия:
Код
laptop:/usr/src# ls -l linux-2.6.31.3.tar*
-rw-r--r-- 1 root root 365752320 2009-12-01 23:26 linux-2.6.31.3.tar
-rw-r--r-- 1 root root 61452332 2009-12-01 23:34 linux-2.6.31.3.tar.bz2
-rw-r--r-- 1 root root 78296603 2009-12-01 23:30 linux-2.6.31.3.tar.gz
-rw-r--r-- 1 root root 50817218 2009-12-01 23:54 linux-2.6.31.3.tar.lzma
-rw-r--r-- 1 root root 48246188 2009-12-02 00:04 linux-2.6.31.3.tar.ppmd
-rw-r--r-- 1 root root 365752320 2009-12-01 23:26 linux-2.6.31.3.tar
-rw-r--r-- 1 root root 61452332 2009-12-01 23:34 linux-2.6.31.3.tar.bz2
-rw-r--r-- 1 root root 78296603 2009-12-01 23:30 linux-2.6.31.3.tar.gz
-rw-r--r-- 1 root root 50817218 2009-12-01 23:54 linux-2.6.31.3.tar.lzma
-rw-r--r-- 1 root root 48246188 2009-12-02 00:04 linux-2.6.31.3.tar.ppmd
Такое же "грязное" сравнение по времени разжатия:
Код
laptop:/usr/src# time gzip -d < linux-2.6.31.3.tar.gz > /dev/null
real 0m6.306s
user 0m5.096s
sys 0m0.044s
laptop:/usr/src# time bzip2 -d < linux-2.6.31.3.tar.bz2 > /dev/null
real 0m49.637s
user 0m38.698s
sys 0m0.140s
laptop:/usr/src# time lzma -d < linux-2.6.31.3.tar.lzma > /dev/null
real 0m15.896s
user 0m11.885s
sys 0m0.104s
laptop:/usr/src# time ppmd -d < linux-2.6.31.3.tar.ppmd > /dev/null
real 9m59.326s
user 7m36.401s
sys 0m1.608s
real 0m6.306s
user 0m5.096s
sys 0m0.044s
laptop:/usr/src# time bzip2 -d < linux-2.6.31.3.tar.bz2 > /dev/null
real 0m49.637s
user 0m38.698s
sys 0m0.140s
laptop:/usr/src# time lzma -d < linux-2.6.31.3.tar.lzma > /dev/null
real 0m15.896s
user 0m11.885s
sys 0m0.104s
laptop:/usr/src# time ppmd -d < linux-2.6.31.3.tar.ppmd > /dev/null
real 9m59.326s
user 7m36.401s
sys 0m1.608s
Степень сжатия и скорость работы PPMd сильно зависят от используемой модели предсказания. Использованная в тесте (и включенная в PPMd SDK) модель оптимизирована под естественные тексты.
[close]
