Очень простой и мощный алгоритм сжатия -> Форум на Исходниках.RU [Powered by Invision Power Board]

Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум на Исходниках.RU > Обсуждаем новые идеи > Очень простой и мощный алгоритм сжатия

Автор: Serafim 25.02.13, 07:36

Допустим у нас есть файл в 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.

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

Ваши идеи?

Автор: treeS 25.02.13, 08:13

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

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

Цитата

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

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFAAAAAAAAAAAAAAAAAAAAAA124AAAAAAAAAAAAAAAAA456AAAAAAAAAAAAAAAAAAAAAAAFFFF1F25CCCCCCCCCCCCCCC5D6EEEE444EEE

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

Автор: MIF 25.02.13, 08:25

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

Автор: Аэтерос 25.02.13, 08:53

шляпа

Автор: MIF 25.02.13, 09:03

Цитата 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 бита).

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

Автор: Serafim 25.02.13, 10:12

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

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

Автор: AVA12 25.02.13, 13:51

Цитата

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

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

Автор: Serafim 25.02.13, 13:55

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

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

Автор: AVA12 25.02.13, 15:08

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

Автор: Мяут-Настоящий 25.02.13, 16:56

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

Цитата

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

Автор: Serafim 25.02.13, 17:02

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

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

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

Автор: Kray74 25.02.13, 18:28

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

Автор: OpenGL 26.02.13, 05:29

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

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

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

Автор: Serafim 26.02.13, 06:26

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

думаю тема закрыта