Комментарии
А можно просто сравнительную таблицу? Например, сжатие файла, содержащего случайные данные (dd if=/dev/random of=./datafile bs=4096 count=1024), вашим архиватором и архиваторами ZIP, RAR, 7Zip с максимальной степенью сжатия?
Предоставьте файл.
На предоставленном файле, сжатие происходит каждый мегабайт на 1 — Один бит, при файле 4 мегабайта сжатие будет 4 бита плюс словарь + 256 бит, что значит сжатия данных не происходит. при генерации файла таким же методом в 257 мегабайт будет выигрыш в 1 бит.
Попробуйте этот файл: http://test.nizarium.com/udatafile. 8 мегабайт случайных символов (32-127). ZIP при максимальной степени сжатия выдает файл размером 6,6 мегабайт (6978032 байт).
7826246 байт + 256 бит словарь. Чуда конечно не случилось. Хотя цель этого алгоритма другая.
Второй алгоритм (который на видео) при параметрах по умолчанию давал схожий результат (6,6 мегабайт) но при некоторой оптимизации, возможно, удастся ужать на пару байт лучше, но это займет значительно время для подбора удачной комбинации.
Второй алгоритм (который на видео) при параметрах по умолчанию давал схожий результат (6,6 мегабайт) но при некоторой оптимизации, возможно, удастся ужать на пару байт лучше, но это займет значительно время для подбора удачной комбинации.
Кстати если взять основание системы счисления 96 (128-32 символа) то получиться 6904834 байт что на 73198 байта лучше сжимается, тут конечно не учитываются служебные данные, но они не настолько большие.
в конце видео есть вполне наглядная сравнительная таблица, посмотрели бы сначала…
Какой смысл в тесте на случайных данных?
Плохо, что в Вашей статье нет никаких количественных данных о результатах работы алгоритмов. Взяли бы стандартный Calgary Corpus и привели бы свои результаты сжатия.
Иными словами вы уменьшаете значения байтов.
Перенумеровывая, только встречающиеся, так?
Перенумеровывая, только встречающиеся, так?
1. А смысл в таких «практических» изысканиях, если всё уже разжёвано в теоретических исследованиях? Это же не физика, а математика. Новых открытий от таких экспериментов ждать не приходится.
2. Помнится в компьютерре (кажется) была первоапрельская заметка о новейшей разработке — алгоритме сжатия без потерь, сжимающем любые файлы в 100-200 раз :)
2. Помнится в компьютерре (кажется) была первоапрельская заметка о новейшей разработке — алгоритме сжатия без потерь, сжимающем любые файлы в 100-200 раз :)
Во все возможных википедиях черным по белому сказано, что нельзя сжимать уже сжатые данные или шифрованные. Данная статья доказывает что можно (при больших файлах более гигабайта). Хочу заметить, что это достаточно новый виток в этой области и данные алгоритмы далеки от совершенства.
Эффективнее не повторно сжимать уже сжатые данные, а сначала декодировать, а потом повторно сжать другим более эффективным алгоритмом. Это справедливо конечно только в случае сжатия без потерь
Представим, что у вас имеется большое хранилище данных. В него поступают только архивы с паролем или шифрованные данные (это одно и то же в рассматриваемом случае). У вас нет никакой возможности перекодировать данные в исходный вариант и закодировать более удобным для вас методом. Тогда можно применить данный алгоритм.
Я не понимаю, вы что претендуете на построение биекции из 1..2^n в 1..K, где K < 2^n? Или это эмпиричсекий результат? Если эмпирический, то интересны исследования становится с выборок в >>500 примеров, причем с жестким контролем за источником этих примеров.
В корне не верно. Суть всего происходящего не в преобразовании всех чисел в меньшее значение, а взять только определенную группу.
Вы не поняли что я спрашиваю. Если средний размер сжатой последовательности для всех положим мегабайтных последовательностей (а их 2^20) меньше мегабайта, то это эквивателнтно введению более компактной нумерации на множестве 1..2^20, что невозможно. Именно из этого простого соображения вытекает бесполезность попыток сжать случайную последовательеность.
Сжать результат ZIP или 7Z для типовых файлов может и возможно, но это надо исследовать на очень больших выборках.
Сжать результат ZIP или 7Z для типовых файлов может и возможно, но это надо исследовать на очень больших выборках.
Это рассуждение для линейного алгоритма, не имеющего ветвления.
Практический пример:
0 0 0 0 0 0 0 0 у нас есть 8 байт с нулевыми значениями, сожмем эти 8 байт методом RLE
8,0 получиться 2 байта первый байт количество повторений байта, значением второго байта заполняем цепочку.
второй случай
0 1 2 3 4 5 6 7 у нас есть также 8 байт. Кодируем тем же алгоритмом.
1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 получаем 16 байт
но что если применить другой алгоритм на тех же исходных данных
8,0,1 получиться 3 байта первый байт длина цепочки, второй байт стартовое значение, третий байт команда алгоритму инкрементировать стартовое значение при каждом шаге.
данный практический опыт показывает что, умея выбирать алгоритм можно сжимать определенные данные в меньший размер, а также видно, что на всех комбинациях данных один и тот же алгоритм работать не будет.
P.S. Это уже вольное начало другой моей статьи которая будет немного позже.
Практический пример:
0 0 0 0 0 0 0 0 у нас есть 8 байт с нулевыми значениями, сожмем эти 8 байт методом RLE
8,0 получиться 2 байта первый байт количество повторений байта, значением второго байта заполняем цепочку.
второй случай
0 1 2 3 4 5 6 7 у нас есть также 8 байт. Кодируем тем же алгоритмом.
1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 получаем 16 байт
но что если применить другой алгоритм на тех же исходных данных
8,0,1 получиться 3 байта первый байт длина цепочки, второй байт стартовое значение, третий байт команда алгоритму инкрементировать стартовое значение при каждом шаге.
данный практический опыт показывает что, умея выбирать алгоритм можно сжимать определенные данные в меньший размер, а также видно, что на всех комбинациях данных один и тот же алгоритм работать не будет.
P.S. Это уже вольное начало другой моей статьи которая будет немного позже.
Мое рассуждение нигде не использует факта наличия или ветвления в алгоритме сжатия. Я говорю о результате в виде битовой последовательности, а что у нее внутри — биты выбора алгоритма и потом данные, мета-код для порождения сжатой последовательности на машине Тьюринга или даже url со сжатым файлом в интернете совершенно неважно.
Но следующей статьи с интересом подожду.
Но следующей статьи с интересом подожду.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сжатие данных