Очень простой и мощный алгоритм сжатия

Допустим у нас есть файл в 10 кб, после чтения его в бинарном режиме - мы получаем набор байтов, которые могут быть без проблем превращены в 16ричную запись. Итак, суть алгоритма:
1) Имеем на руках феерической длины 16-ричное число
2) Делим его на наименьший делитель из возможных (как минимум 2, как максимум - само число), допустим 2
3) В результате получаем 2 и это же число, сокращённое в два раза
4) Записываем в "стек" 2 и проделываем ту же самую операцию для оставшихся данных
5) повторяем до тех пор, пока делимое не будет соответствовать делителю.
6) Далее получаем просто набор множителей для воссоздания исходной записи
7) Сокращаем количество одинаковых множителей с помошью простых простых арифметических операторов и разделяем операции спец символами, получаем что-то вроде такого:
2x32;3x3;4;6;37FFAC

Для воссоздания исходных данных возводим 2 в степень 32, 3 в степень 3, умножаем на 4, затем на 6 и в конце на 37FFAC.

Плюсы:
+ Можно сократить несколько гигабайт данных до килобайт в идеальном варианте
+ Довольно простой алгоритм
Минусы:
- Требует дофига оперативной памяти и времени вычесления даже на небольших объёмах елси делать в лоб

Ваши идеи?

Вопрос. На каком языке ты это хотел бы реализовать?
Вопрос 2. Ты хоть знаешь что такое стек?)))) Недавно помню ты удивлялся что строка это массив байтов))))

Добавлено 25.02.13, 08:16

Цитата

2) Делим его на наименьший делитель из возможных (как минимум 2, как максимум - само число), допустим 2

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFAAAAAAAAAAAAAAAAAAAAAA124AAAAAAAAAAAAAAAAA456AAAAAAAAAAAAAAAAAAAAAAAFFFF1F25CCCCCCCCCCCCCCC5D6EEEE444EEE

Поделикося на 2..... Или на наименьший делитель....

Мелкое замечание: в списке могут быть только простые числа. 4 и 6 не являются простыми.
Улучшение алгоритма: вместо записывания 2,3,7,11 записывай порядковый номер простого числа: 1,2,3,4. Уже со второго простого числа (тройки) ето даёт выигрыш по краиней мере в один бит.
ИМХО: в обшем случае размер архива будет больше исходного файла.

шляпа

Цитата MIF @ 25.02.13, 08:25

ИМХО: в обшем случае размер архива будет больше исходного файла.

Допустим, что разделители "x" и ";" занимают в стриктуре М бит. М не может быть меньше 2. Примем идеальное допучение М=2 (я не знаю, как такого добиться!)
Протестируем все N-битные числа.
Проанализируем делимость на 2.
Половина чисел нечетные - нет изменения в размере архиве после приложения правила "делимость на 2"
Четверть чисел простые четные. Размер оставшегося числа уменьшается на 1 бит. Размер области хранения информации о делимости на два занимарт 4 бита(1x1;). Потери = 3 бита;
1/8 чисел дважды четные. Размер оставшегося числа уменьшается на 2 битс. Размер области хранения информации о делимости на два занимарт 5 бит(10x1;). Потери = 3 бита;
1/16 чисел дважды четные. Размер оставшегося числа уменьшается на 3 битс. Размер области хранения информации о делимости на два занимарт 5 бит(11x1;). Потери = 2 бита;
1/32 чисел дважды четные. Размер оставшегося числа уменьшается на 4 битс. Размер области хранения информации о делимости на два занимарт 6 бит(100x1;). Потери = 2 бита;

Начная с "К четности" будет некоторый выйгрых в конечном размере, но процент таких чисел очень низок.

Получается что-то типа геометрической прогресси. Геометричекие прогрессий шодятся.
Если посчтать ее предел при M стремяшемся к бесконечности, то думаю , получатся небольшие потери (0.5-1.0 бита).

И чем больше простое число, тем большие будут потери .

Сообщение отредактировано: MIF - 25.02.13, 09:04

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

С первого раза я не соображу с ходу в каких случаях может быть выигрыш. Опять же, чисто теоретически нужно брать не наименьший делитель, а наибольший в пределах одного байта.

Цитата

С первого раза я не соображу с ходу в каких случаях может быть выигрыш

Гм, вообще-то сначала анализируют данные, которые надо сжимать, определяют, какую избыточность они содержат, а уж затем придумывают, как эту избыточность отжать. А не наоборот.

Цитата AVA12 @ 25.02.13, 13:51

Гм, вообще-то сначала анализируют данные, которые надо сжимать, определяют, какую избыточность они содержат, а уж затем придумывают, как эту избыточность отжать. А не наоборот.

сам понимаешь, что избыточность нужно анализировать в случаях составления индексированного словаря, как это делает zip. В случае арифметического кодирования (именно этот случай энтропийного сжатия о котором я говорю в топике) - этот вариант не нужен, т.к. для всех данных будет использоваться одинаковое деление на целые и составление словаря множителей.

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

http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%...%BD%D0%B8%D1%8F

Цитата

N случайная переменная с энтропией H(X) может быть сжата в более чем NH(X) битов с незначительным риском потери данных если N стремится к бесконечности, но если сжатие происходит менее в чем NH(X)) бит, то данные скорее всего будут потеряны. (MacKay 2003).»

Цитата AVA12 @ 25.02.13, 15:08

А твой алгоритм для каких данных предназначен?

вообще походу это не мой алгоритм, его уже реализовывал практически каждый школьник. Сегодня на работе поделился - коллега сказал, что когда в Вузе учился - делал, есть оказывается ещё некий Бабушкин (ака Попов с БолгенОС), который мол тоже такое же предложил.

Про Бабушкина уже устроили срач в многошуме.

Цитата Serafim @ 25.02.13, 07:36

2) Делим его на наименьший делитель из возможных (как минимум 2, как максимум - само число), допустим 2

Как его найти?
Да и к тому же очень редко когда будут попадаться "хорошие" данные, в которых будет много одинаковых чисел. Поэтому сжатием это не будет почти во всех случаях.

та я уже проверил, набросал алогиртм на пыхе, данные jpg картинки увеличились со 136 килобайт до 157
думаю тема закрыта